Безопасность SHA

SHA очень похожа на MD4, но выдает 160-битовое хэш-значение. Главным изменением является введение расширяющего преобразования и добавление выхода предыдущего шага в следующий с целью получения более быстрого лавинного эффекта. Рон Ривест опубликовал цели, преследуемые им при проектировании MD5, но разработчики SHA этого не сделали. Вот улучшения, внесенные Ривестом в MD5 относительно MD4, и их срав­нение с SHA:

1. "Добавился четвертый этап." В SHA тоже. Однако в SHA на четвертом этапе используется та же функция f, что и на втором этапе.

2. "Теперь в каждом действии используется уникальная прибавляемая константа." SHA придерживается схемы MD4, повторно используя константы для каждой группы их 20 этапов.

3. "Функция G на этапе 2 с ((XaY)v(XaZ)v(YaZ)) была изменена на (XaZ)v(Ya(­Z)), чтобы сделать G менее симметричной." В SHA используется версия функции из MD4: (1л 7) v(Xa Z) v (7л Z).

4. "Теперь каждое действие добавляется к результату предыдущего этапа. Это обеспечивает более быст­рый лавинный эффект." Это изменение было внесено и в SHA. Отличие состоит в том, что в SHA до­бавлена пятая переменная к Ъ, с и d, которые уже используются в f_t. Это незначительное изменение делает применения вскрытия MD5 ден Боером и Босселаерсом невозможным по отношению к SHA.

5. "Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3, чтобы сделать

шаблоны менее похожими." SHA в этом месте совершенно отличается, так как использует цикличе­ский код исправления ошибок.

6. "Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для уск о-рения лавинного эффекта. Четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на других этапах." SHA на каждом этапе использует постоянное значение сдвига. Это значение - взаимно простое число с размером слова, как и в MD4.

Это приводит к следующему заключению: SHA - это MD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. MD5 - это MD4 с улучшенным битовым хэширова­нием, дополнительным этапом и улучшенным лавинным эффектом.

Сведения об успешных криптографических вскрытиях SHA отсутствуют. Так как эта однонаправленная хэш-функция выдает 160-хэш-значение, она устойчивее к вскрытию грубой силой (включая вскрытие методом дня рождения), чем 128-битовые хэш-функции, рассматриваемые в этой главе.

18.8 RIPE-MD

RIPE-MD была разработана для проекта RIPE Европейского сообщества [1305] (см. раздел 25.7). Этот алго­ритм представляет собой вариант MD4, разработанный так, чтобы противостоять известным методам крипто­графического вскрытия, и выдает 128-битовое хэш-значение. Внесены изменения в циклические сдвиги и поря­док слов сообщения. Кроме того, параллельно работают две копии алгоритма, отличающиеся константами. По­сле каждого блока результат обоих копий добавляется к переменным сцепления. По видимому, это повышает устойчивость алгоритма к криптоанализу.

18.9 HAVAL

HAVAL - это однонаправленная хэш-функция переменной длины [1646]. Она является модификацией MD5. HAVAL обрабатывает сообщение блоками по 1024 бита, в два раза большими, чем в MD5. Используется восемь 32-битовых переменных сцепления, в два раза больше, чем в MD5, и переменное число этапов, от трех до пяти (в каждом 16 действий). Функция может выдавать хэш-значения длиной 128, 160, 192, 224 или 256 битов.

HAVAL заменяет простые нелинейные функции MD5 на сильно нелинейные функции 7 переменных, каждая из которых удовлетворяет строгому лавинному критерию. На каждом этапе используется одна функция, но при каждом действии входные переменные переставляются различным образом. Используется новый порядок со­общения, и при каждом этапе (кроме первого этапа) используется своя прибавляемая константа. В алгоритме также используется два циклических сдвига.

Ядром алгоритма являются следующие действия:

TEMP = (f(j,A,B,C,D,E,F,G) <«7) + (Я<«11) + M[i][r(j)+K(j)]

H = G; G = F; F = E; E = D; D = C; С = В; В = А; А = TEMP

Переменное количество этапов и переменная длина выдаваемого значения означают, что существует 15 ве р-сий алгоритма. Вскрытие MD5, выполненное ден Боером и Босселаерсом [203], неприменимо к HAVAL из-за циклического сдвига Н.

18.10 Другие однонаправленные хэш-функции

MD3 является еще одной хэш-функцией, предложенной Роном Ривестом. Она имела ряд недостатков и нико­гда не выходила за пределы лаборатории, хотя ее описание недавно было опубликовано в [1335].

Группа исследователей из Университета Ватерлоо предложила однонаправленную хэш-функцию на базе итеративного возведения в степень в GF(2⁵⁹³) [22]. По этой схеме сообщение разбивается на 593-битовые блоки. Начиная с первого блока блоки последовательно возводятся в степень. Показатель степени - это результат вы­числений для предыдущего блока, первый показатель задается с помощью IV.

Айвэн Дамгард (Ivan Damgard) разработал однонаправленную хэш-функцию, основанную на проблеме рю к-зака (см. раздел 19.2) [414], она может быть взломана примерно за 2³² операций [290, 1232, 787].

В качестве основы для однонаправленных хэш-функций предлагался и клеточный автомат Стива Вольфрама [1608]. Ранняя реализация [414] небезопасна [1052,404]. Другая однонаправленная хэш-функция, Cellhash [384, 404], и улучшенная версия, Subbash [384,402, 405], также основаны на клеточных автоматах и предназначены для аппаратной реализации. Boognish объединил принципы Cellhash и MD4 [402, 407]. StepRightUp также мо­жет быть реализована как хэш-функция [402].

Летом 1991 года Клаус Шнорр (Claus Schnorr) предложил однонаправленную хэш-функцию на базе дис-

кретного преобразования Фурье, названную FFT-Hash [1399]. Через несколько месяцев она была взломана дву­мя независимыми группами [403, 84]. Шнорр предложил новую версию, FFT-Hash II (предыдущая была пере­именована в FFT-Hash I) [1400], которая была взломана через несколько недель [1567]. Шнорр предложил дальнейшие модификации [1402, 1403] но, при данных обстоятельствах, они намного медленнее, чем другие алгоритмы этой главы. Еще одна хэш-функция, SL₂ [1526], небезопасна [315].

Дополнительную информацию по теории проектирования однонаправленных хэш-функций из однонапра в-ленных функций и однонаправленных перестановок можно найти в [412, 1138, 1342].

18.11 Однонаправленные хэш-функции, использующие симметричные блоч­ные алгоритмы

В качестве однонаправленных хэш-функций можно использовать симметричные блочные алгоритмы ши ф-рования. Идея в том, что если безопасен блочный алгоритм, то и однонаправленная хэш-функция будет без о-пасной.

Самым очевидным способом является шифрование сообщения в режиме СВС или CFB с помощью фиксиро­ванного ключа и IV, хэш-значением будет последний блок шифротекста. Эти методы описаны в различных стандартах, использующих DES: оба режима в [1143], СВС в [1145], CFB в [55, 56, 54]. Этот способ не слиш­ком подходит для однонаправленных хэш-функций, хотя он будет работать для MAC (см. раздел 18.14) [29].

Способ поумнее использует в качестве ключа блок сообщения, предыдущее хэш-значение в качестве входа, а текущее хэш-значение служит выходом.

Действительные хэш-функции даже еще сложнее. Размер блока обычно совпадает с длиной ключа, и разм е-ром хэш-значения будет длина блока. Так как большинство блочных алгоритмов 64-битовые, спроектирован ряд схем, дающих хэш-значение в два раза большее длины блока.

При условии, что хэш-функция правильна, безопасность этой схемы основана на безопасности используемой блочной функции. Однако есть и исключения. Дифференциальный криптоанализ лучше работает против блоч­ных функций в хэш-функциях, чем против блочных функций, используемых для шифрования: ключ известен, поэтому можно использовать различные приемы. Для успеха нужна только одна правильная пара, и можно г е-нерировать столько выбранного открытого текста, сколько нужно. Это направление освещается в [1263, 858, 1313].