WikiSort.ru - Не сортированное

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

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

SHACAL-1

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

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

${\displaystyle K_{i}=(K_{i-3}\oplus K_{i-8}\oplus K_{i-14}\oplus K_{i-16})<<1}$ .

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

Размер блока равен размеру внутреннего состояния и хеша хеш-функции SHA1 — 160 бит. Блок обрабатывается как пять 32-битных подблоков: ${\displaystyle A,B,C,D,E}$ . Шифротекстом является конкатенация данных из переменных ${\displaystyle A_{80},B_{80},C_{80},D_{80},E_{80}}$ ^[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 раз проделать следующее:

${\displaystyle A_{i+1}=K_{i}+(A_{i}<<<5)+f_{i}(B{i},C{i},D{i})+E_{i}+M_{i}mod2^{32}}$

${\displaystyle B_{i+1}=A_{i}}$

${\displaystyle C_{i+1}=B_{i}<<<30}$

${\displaystyle D_{i+1}=C_{i}}$

${\displaystyle E_{i+1}=D_{i}}$

где:

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

Таблица 1

Раунды	Функция
0-19	${\displaystyle f(x,y,z)=(x\&y)\mid (x'\&z)}$
20-39	${\displaystyle f(x,y,z)=x\oplus y\oplus z}$
40-59	${\displaystyle f(x,y,z)=(x\oplus y)\mid (x\oplus z)\mid (y\oplus z)}$
60-79	${\displaystyle f(x,y,z)=x\oplus y\oplus z}$

Таблица 2

SHACAL-2

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

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

${\displaystyle K_{i}=O_{1}(K_{i-2}+K_{i-7}+O_{0}(K_{i-15})+K_{i-16}}$

где ${\displaystyle O_{0}}$ и ${\displaystyle O_{1}}$ :

• ${\displaystyle O_{0}(x)=(x>>>7)\oplus (x>>>18)\oplus (x>>3)}$
• ${\displaystyle O_{1}(x)=(x>>>17)\oplus (x>>>19)\oplus (x>>10)}$

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

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

${\displaystyle T=H_{i}+S_{1}(E_{i})+Ch(E_{i},F_{i},G_{i})+M_{i}+K_{i}mod2^{32}}$

${\displaystyle H_{i+1}=G_{i}}$

${\displaystyle G_{i+1}=F_{i}}$

${\displaystyle F_{i+1}=E_{i}}$

${\displaystyle E_{i+1}=D_{i}+T}$

${\displaystyle D_{i+1}=C_{i}}$

${\displaystyle C_{i+1}=B_{i}}$

${\displaystyle B_{i+1}=A_{i}}$

${\displaystyle A_{i+1}=T+S_{0}(A_{i})+Maj(A_{i},B_{i},C_{i})mod2^{32}}$

где:

• ${\displaystyle S_{0}(x)=(x>>>2)\oplus (x>>>13)\oplus (x>>>22)}$
• ${\displaystyle S_{1}(x)=(x>>>6)\oplus (x>>>11)\oplus (x>>>25)}$
• ${\displaystyle Ch(x,y,z)=(x\&y)\oplus (x'\&z)}$
• ${\displaystyle Maj(x,y,z)=(x\&y)\oplus (x\&z)\oplus (y\&z)}$
• >>> — побитовый циклический сдвиг
• ${\displaystyle T}$  — временная переменная
• ${\displaystyle M_{i}}$  — модифицирующие константы при i = 0 — 63 (см. Таблицу 3, константы расположены по порядку)

Таблица 3

Стойкость

Прежде всего, как было отмечено^[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).

Примечания

Ссылки

• H. Handschuh, D. Naccache. SHACAL (неопр.) (2000).
• Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8
  <a href='https://wikidata.org/wiki/Track:Q27942697'></a><a href='https://wikidata.org/wiki/Track:Q27942695'></a><a href='https://wikidata.org/wiki/Track:Q27942699'></a>
• Панасенко С.Алгоритмы шифрования. Специальный справочник — Санкт-Петербург: БХВ-Петербург, 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".. 
• Jiqiang Lu, Jongsung Kim, Nathan Keller, Orr Dunkelman (2006). "Related-Key Rectangle Attack on 42-Round SHACAL-2" (PDF)., Samos: Springer-Verlag. Проверено 2012-11-14. 
• Markku-Juhani Olavi Saarinen (2003-02). "Cryptanalysis of Block Ciphers Based on SHA-1 and MD5" (PDF). FSE '03: 36–44, Lund: Springer-Verlag. Проверено 2012-11-28.