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

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

hi =/(M„ Л.-.О

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

M i J ---------------------------------

> Однонаправленная

функция > h i

/7/-1 *\ ---------------------------------

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

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

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

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

18.2 Snefru

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

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

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

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

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

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