SHACAL

SHACAL
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 фрагментов по формуле:

\text{[math]}

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

.

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

Размер блока равен размеру внутреннего состояния и хеша хеш-функции SHA1 — 160 бит. Блок обрабатывается как пять 32-битных подблоков: $\text{[math]}$ $\text{[math]}$ $A, B, C, D, E$ . Шифротекстом является конкатенация данных из переменных $\text{[math]}$ $\text{[math]}$ $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Править

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

\text{[math]}

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

\text{[math]}

B_{i+1}=A_{i}

\text{[math]}

C_{i+1}=B_{i}<<<30

\text{[math]}

D_{i+1}=C_{i}

\text{[math]}

E_{i+1}=D_{i}

где:

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

Таблица 1

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

Таблица 2

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

SHACAL-2Править

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

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

\text{[math]}

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

где $\text{[math]}$ $\text{[math]}$ $O_{0}$ и $\text{[math]}$ $\text{[math]}$ $O_{1}$ :

$\text{[math]}$ $\text{[math]}$ $O_{0}(x)=(x>>>7)\oplus (x>>>18)\oplus (x>>3)$
$\text{[math]}$ $\text{[math]}$ $O_{1}(x)=(x>>>17)\oplus (x>>>19)\oplus (x>>10)$

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

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

\text{[math]}

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

\text{[math]}

H_{i+1}=G_{i}

\text{[math]}

G_{i+1}=F_{i}

\text{[math]}

F_{i+1}=E_{i}

\text{[math]}

E_{i+1}=D_{i}+T

\text{[math]}

D_{i+1}=C_{i}

\text{[math]}

C_{i+1}=B_{i}

\text{[math]}

B_{i+1}=A_{i}

\text{[math]}

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

где:

$\text{[math]}$ $\text{[math]}$ $S_{0}(x)=(x>>>2)\oplus (x>>>13)\oplus (x>>>22)$
$\text{[math]}$ $\text{[math]}$ $S_{1}(x)=(x>>>6)\oplus (x>>>11)\oplus (x>>>25)$
$\text{[math]}$ $\text{[math]}$ $Ch(x,y,z)=(x\&y)\oplus (x'\&z)$
$\text{[math]}$ $\text{[math]}$ $Maj(x,y,z)=(x\&y)\oplus (x\&z)\oplus (y\&z)$
>>> — побитовый циклический сдвиг
$\text{[math]}$ $\text{[math]}$ $T$ — временная переменная
$\text{[math]}$ $\text{[math]}$ $M_{i}$ — модифицирующие константы при 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).

ПримечанияПравить

↑ H. Handschuh, D. Naccache SHACAL
↑ Панасенко, 2009, с. 449.
↑ ndschuh, D. Naccache SHACAL
↑ ¹ ² ³ Панасенко, 2009.
↑ Markku-Juhani Olavi Saarinen (2003-02). «Cryptanalysis of Block Ciphers Based on SHA-1 and MD5»
↑ J. Lu, J. Kim, N. Keller, O. Dunkelman (2006). "Diﬀerential and Rectangle Attacks on Reduced-Round SHACAL-1
↑ 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). Diﬀerential 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. Архивировано из оригинала (PDF) 2006-09-25. Дата обращения 2012-11-14. Используется устаревший параметр |deadlink= (справка) Архивная копия от 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) 2006-12-24. Дата обращения 2012-11-28. Используется устаревший параметр |deadlink= (справка); Проверьте дату в |date= (справка на английском) Архивная копия от 24 декабря 2006 на Wayback Machine

[1] H. Handschuh, D. Naccache SHACAL

[_f688d195992085a7-2] Панасенко, 2009, с. 449.

[3] schuh, D. Naccache SHACAL

[_444f6d82a2f109ea-4] ¹ ² ³ Панасенко, 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). "Diﬀerential and Rectangle Attacks on Reduced-Round SHACAL-1

[_738913744f47b73d-7] Lu et al., 2006, p. 85–100.

[1]

[2]

[3]

[4]

[5]

[6]

[7]