SHACAL

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
SHACAL
Создатель Хелена Хандшух, Давид Наккаш
Создан 2000
Опубликован 2001
Размер ключа 128—512 бит
Размер блока 160 бит / 256 бит
Число раундов 80/64
Тип Криптографическая хеш-функция

SHACAL — в криптографии симметричный блочный криптоалгоритм, разработанный для участия в конкурсе NESSIE группой авторов из компании Gemplus во главе с Хеленой Хандшух и Давидом Наккашем. Существует два варианта алгоритма — SHACAL-1 и SHACAL-2, который и стал одним из 17 финалистов NESSIE.

Алгоритм SHACAL существенно отличается от многих других алгоритмов. Он основан на функции компрессии хеш-алгоритма SHA-1, что возможно благодаря обратимости раундовой функции данного хеш-алгоритма, при условии что её внутреннее состояние известно. В данном случае ключ используется как подвергающиеся трансформации данные, а открытый текст подается как внутреннее состояние хеш-функции. Всего выполняется 80 раундов преобразования.[1]

Особенностью алгоритма является его простое ключевое расписание — ключ короче 512 бит дополняется до полного размера нулевыми битами. Ключи короче 128 бит не применяются. 512-битный исходный ключ шифрования делится на 16 фрагментов по 32 бита K0…K15. Остальные фрагменты расширенного ключа K16…K79 вычисляются из первых 16 фрагментов по формуле:

.

Данная особенность стала преградой для избрания алгоритма в качестве финалиста NESSIE, так как возникли сомнения в её криптостойкости.[2]

Размер блока равен размеру внутреннего состояния и хеша хеш-функции SHA1 — 160 бит. Блок обрабатывается как пять 32-битных подблоков: . Шифротекстом является конкатенация данных из переменных [3]

SHACAL-1 в настоящее время мало распространен. Его довольно быстро заменил алгоритм SHACAL-2, который часто именуется как просто SHACAL. Существовал так же теоретический SHACAL-0, который был основан на хеш-функции SHA-0 (ранней, позже исправленной версии SHA-1), но он не получил распространения, как собственно и сама хеш-функция SHA-0.[4]

Реализация алгоритма SHACAL-1

[править | править код]
  1. Представить шифруемое сообщение в виде 5 32-битных блоков данных: A, B, C, D, E.
  2. 80 раз проделать следующее:

где:

  •  — номер раунда (1-79)
  •  — фрагмент расширенного ключа для i-го раунда
  •  — функция для i-го раунда (см. табл. 1)
  • <<< — побитовый циклический сдвиг влево
  •  — модифицирующие константы (см. табл. 2)

Таблица 1

Раунды Функция
0-19
20-39
40-59
60-79

Таблица 2

Раунды Значения константы
0-19 5A827999
20-39 6ED9EBA1
40-59 8F1BBCDC
60-79 CA62C1D6

В 2001 году создатели алгоритма SHACAL-1, также в рамках конкурса NESSIE разработали aлгоритм SHACAL-2 основанный на 64 раундах хеш-функции SHA-256 с внутренним состоянием длиной 256 бит.[4]

Исходный ключ размером 512 бит по аналогии с SHACAL-1 делится на 16 частей по 32 бита каждая. Остальные 48 частей вычисляются следующим образом:

где и :

Реализация алгоритма SHACAL-2

[править | править код]

Алгоритм состоит из 64 раундов преобразований:

где:

  • >>> — побитовый циклический сдвиг
  •  — временная переменная
  •  — модифицирующие константы при i = 0 — 63 (см. Таблицу 3, константы расположены по порядку)

Таблица 3

428a2f98 71374491 b5c0fbcf e9b5dba5
3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3
72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240calcc
2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7
c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13
650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3
d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5
391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208
90befffa a4506ceb bef9a3f7 c67178f2

Прежде всего, как было отмечено[4], преимуществом алгоритмов семейства SHACAL была их производительность. Важным моментом является так же простота описания и реализации алгоритмов.

Одним из тезисов безопасности стала архитектура шифра. Теоретически, безопасность алгоритмов SHA-1 и SHA-2 должна обеспечить и устойчивость алгоритмов SHACAL к различным видам атак. В то же время, требования, предъявляемые к хеш-функциям при их разработке, концептуально иные и данный тезис не слишком обоснован. В своей работе Маркку-Юхани Сааринен описал возможные атаки с использованием связанных ключей на алгоритм SHACAL-1.[5]

Относительно устойчивости на конкурсе NESSIE было отмечено отсутствие каких-либо предложений по атаке на SHACAL. Однако, что касается SHACAL-1, ключевое расписание было подвержено критике. В 2002 году Ким Чонсон (Jongsung Kim) предложил дифференциальную атаку на 41 раундах SHACAL-1 с 512-битным ключом. В 2005 году О. Дункельман(O.Dunkelman) представил атаку на связанных ключах для всех 80 раундов SHACAL-1.[6] Годом позднее экспертами был сделан вывод, что в связи с обнаружением коллизий в SHA-1 будут появляться новые атаки на связанных ключах, а криптоаналитики из Кореи предложили атаку методом бумеранга.

После окончания конкурса NESSIE была предложена атака на 42 раунда алгоритма SHACAL-2 c 512-битным ключом, но полнораундовый алгоритм пока не взломан[7]. Следовательно, полнораундовые алгоритмы SHACAL на данный момент можно считать безопасными при условии использования в качестве ключа 512-битного хеша от какой-либо хеш-функции (SHA-512, Whirlpool).

Примечания

[править | править код]
  1. H. Handschuh, D. Naccache SHACAL
  2. Панасенко, 2009, с. 449.
  3. ndschuh, D. Naccache SHACAL
  4. 1 2 3 Панасенко, 2009.
  5. Markku-Juhani Olavi Saarinen (2003-02). «Cryptanalysis of Block Ciphers Based on SHA-1 and MD5»
  6. J. Lu, J. Kim, N. Keller, O. Dunkelman (2006). "Differential and Rectangle Attacks on Reduced-Round SHACAL-1
  7. Lu et al., 2006, p. 85–100.
  • H. Handschuh, D. Naccache. SHACAL (2000).
  • Панасенко С. П. Алгоритмы шифрования. Специальный справочникСПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8
  • Панасенко С.Алгоритмы шифрования. Специальный справочник — Санкт-Петербург: БХВ-Петербург, 2009. — С. 443—451. — 978-5-9775-0319-8.
  • J.Lu,J.Kim,N.Keller,O.Dunkelman (2006). Differential and Rectangle Attacks on Reduced-Round SHACAL-1.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  • Jiqiang Lu, Jongsung Kim, Nathan Keller, Orr Dunkelman (2006). Related-Key Rectangle Attack on 42-Round SHACAL-2 (PDF). Samos: Springer-Verlag. Архивировано из оригинала (PDF) 25 сентября 2006. Дата обращения: 14 ноября 2012.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Архивная копия от 25 сентября 2006 на Wayback Machine
  • Markku-Juhani Olavi Saarinen (2003-02). "Cryptanalysis of Block Ciphers Based on SHA-1 and MD5" (PDF). FSE '03. Lund: Springer-Verlag. pp. 36—44. Архивировано из оригинала (PDF) 24 декабря 2006. Дата обращения: 28 ноября 2012. Архивная копия от 24 декабря 2006 на Wayback Machine