Методы построения функций хэширования

Общий способ построения функций хэширования был предложен Ральфом Мерклем (Ralf Merkel) и несколько позже модифицирован Айвоном Дамгардом (Ivan Damgard). Основная идея данного способа заключается в использовании итеративной процедуры, которая обрабатывает входное сообщение за несколько итераций.

Опишем алгоритм Меркля-Дамгарда. На первом этапе зафиксируем натуральное число h > 1 и разобьем исходное сообщение а е Fjf" на блоки длины Ь:

>

где а* € F^, 1еп (а;) = b, i = 1,…, г — 1 при г > 1 и длина последнего блока удовлетворяет неравенству 1еп а_г ^ Ь.

Для реализации основного этапа алгоритма Меркля-Дамгарда необходимо зафиксировать отображение

которое принято называть одношаговой сжимающей функцией, а также начальное значение ho G Fg. Далее вычислим последовательность.

и определим Я (а) = g (h_r-, a_r), где g: F-J х F| -> FJ? — некоторое завершающее преобразование.

Как правило, завершающее преобразование g заключается в следующем. Определим блок а* равенством.

Тогда отображение g задается равенством.

Данный вид преобразования g был предложен Дамгардом и позволил избавиться от неоднозначности при хэшировании сообщений, длина которых не кратна Ь. Позднее мы приведем примеры отображения д, имеющего более сложную структуру.

Таким образом, бссключевая функция хэширования Я задается набором своих параметров:

• 1 .п — длина кода целостности,
• 2. b — длина блока разбиения входных данных,
• 3. / — одношаговая сжимающая функция,
• 4. д — завершающее преобразование последнего блока,
• 5. ho — начальное значение последовательности ho-hi,…, h_r, последний элемент которой является значением функции хэширования,

и полностью определяется равенством.

Далее будем считать, что для каждой исследуемой функции перечисленные нами параметры п, Ь, /, д, ho зафиксированны.

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

Утверждение 8.1. Если функция хэширования Н построена с помощью алгоритма Меркля-Дамгарда, то сложность построения коллизии для одношаговой функции / сравнима со сложностью построения коллизии для функции Н.

Доказательство. Вначале предположим, что мы умеем строить коллизии для функции Я, то есть находить такие сообщения а = а.111 • • • ||а_г и Ъ = bi|| • •? ||6_S, что Я (а) = Я (6). Тогда коллизия для функции / следует из равенства.

где ti = f (ho, bi) и и = f (U-i, bi) для всех г = 2,…, s — 1.

Обратно предположим, что мы умеем строить коллизии для функции /, то есть находить такие пары h, t 6 Fg и <12,62 € F2, что выполнено равенство.

и одно из условий: аг ф 62 или hi Ф t.

Пусть с произвольный вектор из F|, тогда сообщения а = а 111"211с и b = 61Ц62ЦС имеют одинаковые коды целостности. Действительно,.

при условии, что а и ф определяются равенствами

Как следует из приведенного нами доказательства утверждения 8.1, нарушения свойства однонаправленности функции //,(ж) и существование эффективного алгоритма построения коллизий для одношаговой функции / приводят к возможности построения коллизии для функции хэширования Я. Таким образом, становится важным изучение свойств одношаговой функции хэширования /?

Наиболее часто используемым способом построения одношаговой функции хэширования / является использование блочных алгоритмов шифрования. Приведем несколько примеров.

1. Микаэлем Рабиным был предложен следующий способ построения функции /. Пусть Е (к, а) — произвольный алгоритм блочного шифрования, в котором ключ шифрования к € F™, а блок открытого текста а € Fg. Тогда выберем длину блока b = т равной длине ключа к, некоторое значение ho € F!> и определим.

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

2. В алгоритме Дэвиса-Мейера, являющемся модификацией алгоритма Рабина, используется дополнительное сложение по модулю, то есть.

3. В алгоритме Матиаса-Мейера-Осеаса дополнительно используется расширяющее отображение е: FJ? F™, отображающее двоичные векторы длины, совпадающей с длиной блока п алгоритма шифрования, в двоичные векторы длины т, совпадающей с длиной ключа алгоритма шифрования.

Последовательность блоков ai,…, a_r рассматривается как последовательность блоков для шифрования, то есть b = п и ho € F?. Тогда.

4. В алгоритме Миягучи-Принеля, расширяющем предыдущий пример, используется отображение.

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

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

использующее любую из определенных выше в примерах одношаговых функций /: Щ х F? j F2 следующим образом.

Пусть 7 г = (7Г1,7Г2,7гз, 7Г4) — произвольная, отличная от единичной, перестановка из S4. Мы можем представить любой вектор h е Щ^п в виде.

Обозначим 7 г (/г) = v_ni ||? ?? v_n4, тогда отображение п/ может быть определено следующим образом:

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

Упражнение 8.1.1. Постройте отображение лу : F2¹ х > F2¹ с размерностью выхода In для произвольного натурального I.

Далее мы приведем несколько примеров конкретных функций хэширования, построенных с использованием алгоритма МеркляДам гарда.