Глава 18

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

18.1 Основы

Однонаправленная функция H(M) применяется к сообщению произвольной длины M и возвращает значение фиксированной длины h.

h = H(M), где h имеет длину m

Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у однонаправленных хэш-функций есть дополнительные свойства, делающие их однонаправленными [1065]:

Зная M, легко вычислить h.

Зная H, трудно определить M, для которого H(M)=h.

Зная M, трудно определить другое сообщение, M, для которого H(M) = H(M).

Если бы Мэллори умел делать трудные вещи, он смог бы разрушить безопасность любого протокола, и с-пользующего однонаправленную хэш-функцию. Смысл однонаправленных хэш-функций и состоит в обеспеч е-нии для M уникального идентификатора ("отпечатка пальца"). Если Алиса подписала M с помощью алгоритма цифровой подписи на базе H(M), а Боб может создать M, другое сообщение, отличное от M, для которого H(M) = H(M), то Боб сможет утверждать, что Алиса подписала M.

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

Должно быть трудно найти два случайных сообщения, M и M, для которых H(M) = H(M).

Помните вскрытие методом дня рождения из раздела 7.4? Оно основано не на поиске другого сообщения M, для которого H(M)= H(M), а на поиске двух случайных сообщений, M и M, для которых H(M)= H(M).

Следующий протокол, впервые описанный Гидеоном Ювалом (Gideon Yuval) [1635], показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обм а-на Боба.

(1)Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству

(2)Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хэш-функции . (Этими изменениями могут быть действия, подобные следующим : замена ПРОБЕЛА комбинацией ПРО-БЕЛ-ЗАБОИ-ПРОБЕЛ, вставка одного-двух пробелов перед возвратом каретки, и т.д. Делая или не делая по одному изменению в каждой из 32 строк, Алиса может легко получить 2 32 различных документов.)

(3)Алиса сравнивает хэш-значения для каждого изменения в каждом из двух документов , разыскивая пару, для которой эти значения совпадают. (Если выходом хэш-функции является всего лишь 64-разрядное зн а-чение, Алиса, как правило, сможет найти совпадающую пару сравнив 2 32 версий каждого документа.) Она восстанавливает два документа, дающих одинаковое хэш-значение .

(4)Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только хэш-значение .

(5)Спустя некоторое время Алиса подменяет контракт, подписанный Бобом, другим, который он не подпис ы-вал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт .

Это заметная проблема. (Одним из советов является внесение косметических исправлений в подписываемый документ.)

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

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

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

документа с одинаковыми хэш-значениями, для вскрытия методом дня рождения придется хэшировать 264 случайных документов, что, впрочем, недостаточно, если нужна длительная безопасность . NIST в своем Стандарте безопасного хэширования (Secure Hash Standard, SHS), использует 160-битовое хэш-значение. Это еще сильнее усложняет вскрытие методом дня рождения, для которого понадобится 280 хэширований.

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

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

(2)Хэш значение добавляется к сообщению.

(3)Генерируется хэш-значение объединения сообщения и хэш-значения этапа (1).

(4)Создается большее хэш-значение, состоящее из объединения хэш-значения этапа (1) и хэш-значения этапа (3).

(5)Этапы (1)-(4) повторяются нужное количество раз для обеспечения требуемой длины хэш-значения .

Хотя никогда не была доказана безопасность или небезопасность этого метода, уряд людей этот метод выз ы-вает определенные сомнения [1262,859].

Обзор однонаправленных хэш-функций

Не легко построить функцию, вход которой имеет произвольный размер, а тем более сделаьть ее однон а-правленной. В реальном мире однонаправленные хэш-функции строятся на идее функции сжатия. Такая однонаправленная функция выдает хэш-значение длины n при заданных входных данных большей длины m [1069, 414]. Входами функции сжатия являются блок сообщения и выход предыдущего блока текста (см. 17-й). Выход представляет собой хэш-значение всех блоков до этого момента. То есть, хэш-значение блока М равно

h, = /М,, й,-1)

Это хэш-значение вместе со следующим блоком сообщения становится следующим входом функции сжатия . Хэш-значением всего сообщения является хэш-значение последнего блока .

Однонаправленная функция

Рис. 18-1. Однонаправленная функция

Хэшируемый вход должен каким-то способом содержать бинарное представление длины всего сообщения . Таким образом преодолевается потенциальная проблема, вызванная тем, что сообщения различной длины могут давать одно и то же хэш-значение [1069, 414]. Иногда такой метод называется MD-усилением [930].

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

На тему проектирования однонаправленных хэш-функций написано много. Более подробную математическую информацию можно найти [1028, 793, 791, 1138, 1069, 414, 91, 858, 1264]. Возможно самым толковой интерпретацией однонаправленных хэш-функций являются тезисы Барта Пренела (Bart Preneel) [1262].

18.2 Snefru

Snefru - это однонаправленная хэш-функция, разработанная Ральфом Мерклом [1070]. (Snefru, также как Khufu и Khafre, был египетским фараоном.) Snefru хэширует сообщения произвольной длины, превращая их в 128-битовые 256-битовые значения.

Сначала собщение разбивается на кусочки длиной по 512-m. (Переменная m является длитной хэш-значения.) Если выход - это 128-битовое значение, то длина кусочков равна 384 битам, а если выход -128-битовое значение, то длина кусочков - 256 битов.

Сердцем алгоритма служит функция H, хэширующая 512-битовое значение в m-битовое. Первые m битов выхода H являются хэш-значением блока, остальные отбрасываются . Следующий блок добавляется к хэш-значению предыдущего блока и снова хэшируется. (К первоначальному блоку добавляется строка нулей .) После последнего блока (если сообщение состоит не из целого числа блоков, последний блок дополняется нулями ) первые m битов добавляются к бинарному представлению длины сообщения и хэшируются последний раз .

Функция H основывается на E, обратимой функции блочного шифрования, работающей с 512 битовыми

блоками. H - это последние m битов выхода E, объединенные посредством XOR с первыми m битами входа E.

Безопасность Snefru опирается на функцию E, которая рандомизирует данные за несколько проходов . Каждый проход состоит из 64 рандомизирующих этапов. В каждом этапе в качестве входа S-блока используется другой байт данных. Выходное слово подвергается операции XOR с двумя соседними словами сообщения. Построение S-блоков аналогично построению S-блоков в Khafre (см. раздел 13.7). Кроме того, выполняется ряд циклических сдвигов. Оригинальный Snefru состоял из двух проходов.

Криптоанализ Snefru

Используя дифференциальный криптоанализ, Бихам и Шамир показали небезопасность двухпроходного Snefru (с 128-битовым хэш-значением) [172]. Их способ вскрытия за несколько минут обнаруживает пару соо б-щений с одинаковым хэш-значением .

Для 128-битового Snefru их вскрытия работают лучше, чем вскрытие грубой силой для четырех и менее пр о-ходов. Вскрытие Snefru методом дня рождения требует 264 операций; дифференциальный криптоанализ может найти пару сообщений с одинаковым хэш-значением за 228.5 операций для трехпроходного Snefru и за 244.5 операций для четырехпроходного Snefru. Нахождение сообщения, хэш-значение которого совпадает с заданным, при использовании грубой силы требует 2128 операций, при дифференциальном криптоанализе для этого нужно 256 операций для трехпроходного и 288 операций для четырехпроходного Snefru.

Хотя Бихам и Шамир не анализировали 256-битовые хэш-значения, они провели анализ вплоть до 224-битовых хэш-значений. В сравнении с вскрытием методом дня рождения, требующим 2 112 операций они могут найти сообщения с одинаковым хэш-значением за 212.5 операций для двухпроходного Snefru, за 233 операций для трехпроходного Snefru и за для 281 операций для четырехпроходного Snefru.

В настоящее время Меркл рекомендует использовать Snefru по крайней мере с восемью проходами [1073]. Однако с таким количеством проходов алгоритм становится намного медленнее, чем MD5 или SHA.

18.3 N-хэш

N-хэш - это алгоритм, придуманный в 1990 году исследователями Nippon Telephone and Telegraph, теми же людьми, которые изобрели FEAL [1105, 1106]. N-хэш использует 128-битовые блоки сообщения, сложную ран-домизирующую функцию, похожую на FEAL, и выдает 128-битовое хэш-значение.

Хэш-значение каждого 128-битового блока является функцией блока и хэш-значения предыдущего блока .

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

Hi = g(M„ H-1) © Mi © H-1

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

Функция g достаточно сложна. Схема алгоритма приведена на 16-й. Сначала переставляются левая и правая 64-битовые половины 128-битового хэш-значения предыдущего блока Hi-1, а затем выполняется XOR с повторяющимся шаблоном (128-битовым) и XOR с текущим блоком сообщения Mi. Далее это значение каскадно преобразуется в N (на рисунках N= 8) стадий обработки. Другим входом стадии обработки является предыдущее хэш-значение, подвергнутое XOR с одной из восьми двоичных констант.