SHACAL

Алгоритм 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]

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

В 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)}$

Алгоритм состоит из 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
• Панасенко С.Алгоритмы шифрования. Специальный справочник — Санкт-Петербург: БХВ-Петербург, 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. Архивная копия от 25 сентября 2006 на Wayback Machine
• 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. Архивная копия от 24 декабря 2006 на Wayback Machine