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

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

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

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

18.8 RIPE-MD

RIPE-MD б1ла разработана для проекта 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 = (/(/,A,B,C,D,E,F,G) «<7) + (H «<11) + M[,][r(/)+K(/)]

H = G; G = F; F = E; E = D; D = C; C = B; B = A; A = TEMP

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

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

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

Группа исследователей из Университета Ватерлоо предложила однонаправленную хэш-функцию на базе итеративного возведения в степень в GF(2593) [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] но, при данных обстоятельствах, они намного медленнее, чем другие алгоритмы этой главы. Еще одна хэш-функция, SL2 [1526], небезопасна [315].

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

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

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

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

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

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

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

1313].

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

Полезной мерой для хэш-функций, основанных на блочных шифрах, является скорость хэширования, или количество n-битовых блоков сообщения (n - это размер блока алгоритма), обрабатываемых при шифровании. Чем выше скорость хэширования, тем быстрее алгоритм . (Другое определение этого параметра дается в [1262], но определение, приведенное мной, более интуитивно и шире используется . Это может запутать.)

Схемы, в которы1х длина хэш-значения равна длине блока

Вот общая схема (см. 10-й):

H0 = /я, , где /я - случайное начальное значение

H = Ea(b) e c

где A, B и C могут быть либо M,, Я,--1, (M; e Я,--1), либо константы (возможно равные 0). Я0 - это некоторое случайное начальное число /H. Сообщение разбивается на части в соответствии с размером блока, M,, обрабатываемые отдельно. Кроме того, используется вариант MD-усиления, возможно та же процедура дополнения, что и в MD5 и SHA.

I Ключ! Шифрование

►е-

Рис. 18-8. Обобщенная хэш-функция, у которой длина хэш-значения равна длине блок

Табл. 18-1. Безопасные хэш-функции, у которых

длина хэш-значения равна длине блока

Три различные переменные могут принимать одно из четырех возможных значений, поэтому всего сущес т-вует 64 варианта схем этого типа. Они все были изучены Бартом Пренелом (Bart Preneel) [1262].

Пятнадцать из них тривиально слабы, так как результат не зависит от одного из входов . Тридцать семь небезопасны по более тонким причинам. В 17-й перечислены оставшиеся 12 безопасных схем: первые четыре безопасны против всех вскрытий (см. 9th), а последние 8 безопасны против всех типов вскрытий, кроме вскр ы-тия с фиксированной точкой, о котором в реальных условиях не стоит беспокоиться .

I Ключ! Шифрование

Ключ

Шифрование

I Ключ! Шифрование

Рис. 18-9. Четыре безопасных хэш-функции, у которых длина хэш-значения равна длине блок

Первая схема была описана в [1028]. Третья схема была описана в [1555, 1105, 1106] и предлагалась в качестве стандарта ISO [766]. Пятая схема б1ла предложена Карлом Майером (Carl Meyer), но в литературе обычно называется Davies-Meyer [1606, 1607, 434, 1028]. Десятая схема была предложена в качестве режима хэш-функции для LOKI [273].

Скорость хэширования первой, второй, третьей, четвертой, пятой и одиннадцатой схем равна 1 - длина кл ю-ча равна длине блока. Скорость хэширования других схем составляет k/n, где k -длина ключа. Это означает, что если длина ключа короче длины блока, то блок сообщения должен быть по длине равен ключу . Не рекомендуется, чтобы блок сообщения был длиннее ключа, даже если длина ключа алгоритма шифрования больше, чем длина блока.

Если блочный алгоритм подобно DES обладает свойством комплиментарности и слабыми ключами , для всех 12 схем существует возможность дополнительного вскрытия . Оно не слишком опасно и в действительности не стоит об это м беспокоиться. Однако вы можете обезопасить себя от такого вскрытия, зафиксировав значение второго и третьего битов ключа, равное 01" или 10" [1081,1107]. Конечно же это уменьшит длину k с 56 битов до 54 битов (для DES) и уменьшит скорость хэширования.

Было показано, что следующие схемы, описанные в литературе, небезопасны .

Эта схема [1282] была взломана в [369]:

H.- = Em. (H..-1)

Дэвис (Davies) и Прайс (Price) предложили вариант, в котором все сообщение циклически обрабатывается алгоритмом дважды [432, 433]. Вскрытие Копперсмита взламывает такую схему даже при небольшой вычисл и-тельной мощности [369]. В [1606] была показана небезопасность еще одной схемы [432, 458]: