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

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

h_i= f(M_i, h_i-1)

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

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

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

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

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

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 состоял из двух проходов.