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

Вот общая схема (см. Рис. 18-8):

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

H_i= E_A(B) Å C

где A, B и C могут быть либо M_i, H_i-1, (M_i Å H_i-1), либо константы (возможно равные 0). H₀- это некоторое случайное начальное число I_H. Сообщение разбивается на части в соответствии с размером блока, M_i, обрабатываемые отдельно. Кроме того, используется вариант MD-усиления, возможно та же процедура дополнения, что и в MD5 и SHA.

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

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

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

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

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

Первая схема была описана в [1028]. Третья схема была описана в [1555, 1105, 1106] и предлагалась в качестве стандарта ISO [766]. Пятая схема была предложена Карлом Майером (Carl Meyer), но в литературе обычно называется Davies-Meyer [1606, 1607, 434, 1028]. Десятая схема была предложена в качестве режима хэш-функции для LOKI [273].

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

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

Было показано, что следующие схемы, описанные в литературе, небезопасны.

Эта схема [1282] была взломана в [369]:

Дэвис (Davies) и Прайс (Price) предложили вариант, в котором все сообщение циклически обрабатывается алгоритмом дважды [432, 433]. Вскрытие Копперсмита взламывает такую схему даже при небольшой вычислительной мощности [369]. В [1606] была показана небезопасность еще одной схемы [432, 458]:

В [1028] была показана небезопасность следующей схемы (c - константа):