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

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

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

Размер блока равен размеру внутреннего состояния и хэша хэш-функции SHA1 — 160 бит. Блок обрабатывается как пять 32-битных подблоков: A, B, C, D, E. Шифротекстом является конкатенация данных из переменных 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 раз проделать следующее:
~A_{i+1} = K_{i} + (A_{i}<<<5) + f_{i}(B{i},C{i},D{i}) + E_{i} + M_{i} mod 2^{32}
~B_{i+1} = A_{i}
~C_{i+1} = B_{i}<<<30
D_{i+1} = C_{i}
E_{i+1} = D_{i}

где:

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

Таблица 1

Раунды Функция
0-19 f(x,y,z) = (x\&y)\mid(x'\&z)
20-39 f(x,y,z) = x  \oplus  y  \oplus  z
40-59 f(x,y,z) = (x \oplus y) \mid (x \oplus z) \mid (y \oplus z)
60-79 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 частей вычисляются следующим образом:

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

где O_{0} и O_{1}:

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

Реализация алгоритма SHACAL-2[править | править вики-текст]

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

T = H_{i} + S_{1}(E_{i}) + Ch(E_{i}, F_{i}, G_{i}) + M_{i} + K_{i} mod 2^{32}
H_{i+1} = G_{i}
 G_{i+1} = F_{i}
~F_{i+1} = E_{i}
E_{i+1} = D_{i} + T
 D_{i+1} = C_{i}
C_{i+1} = B_{i}
B_{i+1} = A_{i}
A_{i+1} = T + S_{0}(A_{i}) + Maj(A_{i}, B_{i}, C_{i}) mod 2^{32}

где:

  • S_{0}(x) = (x>>>2)\oplus(x>>>13)\oplus(x>>>22)
  • S_{1}(x) = (x>>>6)\oplus(x>>>11)\oplus(x>>>25)
  • Ch(x,y,z) = (x\&y)\oplus(x'\&z)
  • Maj(x,y,z) = (x\&y)\oplus(x\&z)\oplus(y\&z)
  • >>> - побитовый циклический сдвиг
  • T - временная переменная
  • 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 к различным видам атак. В то же время, требования, предъявляемые к хэш-функциям при их разработке, концептуально иные и данный тезис не слишком обоснован.В своей работе Markku Saarinen описал возможные атаки с использованием связанных ключей на алгоритм 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 Панасенко С.Алгоритмы шифрования. Специальный справочник
  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. Jiqiang Lu, Jongsung Kim, Nathan Keller, Orr Dunkelman.Related-Key Rectangle Attack on 42-Round SHACAL-2, 2006

Ссылки[править | править вики-текст]