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

Вот общая схема:

Н₀ = I_H где I_H - случайное начальное значение

H_i = Е_А(В)  С

где А, В и С могут быть либо М_i , H_i-1__ь (М_i  H_i-1), либо константы (возможно равные 0). H₀ - это некоторое случайное начальное число I_H. Сообщение разбивается на части в соответствии с размером блока, М_i , обрабатываемые отдельно. Кроме того, используется вариант МD-усиления, возможно та же процедура дополнения, что и в МD5 и SНА.

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

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

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

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

Третья схема предлагалась в каче­стве стандарта ISO. Пятая схема была предложена Карлом Майером, но в литературе обычно называется Davies Mayer. Десятая схема была предложена в качестве режима хэш-функции для LOKI.

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

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

Было показано, что следующие схемы, описанные в литературе, небезопасны. Эта схема была взломана: H_i = E_Mi (H_i-1)

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

Модификация схемы Davies-Меуеr

Лай и Массей модифицировали метод Davies-Меуег, чтобы можно было использовать шифр IDЕА использует 64-битовый блок и 128-битовый ключ . Вот предложенная ими схема:

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

М_i

Модификация схемы Davies-Meyer.

Эта хэш-функция выдает хэш-значение, в два раза большее длины блока алгоритма шифрования: при 64-битовом алгоритме получается 128-битовое хэш-значение .

При 64-битовом блочном алгоритме схема выдает два 64-битовых хэш-значения , G_i , и H_i , объединение которых и дает 128-битовое хэш-значение. У большинства блочных алгоритмов длина блока равна 64 битам. Два соседних блока, L_i и R_i , размер каждого равен размеру блока, хэшируются вместе.

G₀ = I_G, где I_G - случайное начальное значение

Но = I_H, , где I_H - другое случайное начальное значение

Лай приводит вскрытие этой схемы, которое в некоторых случаях делает вскрытие методом дня рождения тривиальным. Пренел и Копперсмит также успешно взломали эту схему. Не используйте ее.

К сожалению эта схема тоже небезопасна. Оказывается, что хэш-функция удвоенной длины со скоростью хэширования, равной 1, не может быть безопаснее, чем Davies-Meyer.