Обычно требуется, чтобы бесключевые хэш-функции обладали следующими свойствами:
1) однонаправленность, (по Y = h(X) трудно определить X)
2) устойчивость к коллизиям, (по X трудно найти X’, такое, что h(X) = h(X’).
3) устойчивость к нахождению второго прообраза, (трудно найти пару X, X’ такие, что h(X) = h(X’))
Например, хэш-функция CRC-32, представляющая собой контрольную сумму, является линейным отображением и поэтому не соответствует ни одному из этих трех свойств.
Использование в качестве бесключевой хэш-функции функции, построенной на основе алгоритма блочного шифрования в режиме выработки имитовставки, также нецелесообразно, так как обратимость блочного шифрования позволяет подбирать входное сообщение для любого значения свертки при фиксированном и общеизвестном ключе.
Для построения примера хэш-функции, удовлетворяющей свойству 1), рассмотрим функцию, заданную формулой gk(x) = Еk(х) Å х, где Еk — алгоритм блочного шифрования. Такая функция является однонаправленной по обоим аргументам. Поэтому на ее основе можно построить хэш-функцию, определив одношаговую сжимающую функцию одной из следующих формул:
f(x, H) = EH(x) Å x или f(х, Н) = Ех(Н) Å Н.
Первая из этих функций лежит в основе российского стандарта хэш-функции, а вторая - в основе американского стандарта SHA.
Обе приведенные выше шаговые функции хеширования принадлежат семейству:
Не все функции данного семейства стойки к коллизиям. Стойкие к известным методам криптоанализа конструкции шаговых функций хеширования сведены в таблицу.
Таблица 8. Шаговые функции хеширования f(X, Y), использующие блочное шифрование Ek. (длина блока равна длине ключа или ключ дополнен до длины блока)
| EY(X) Å X EY(X Å Y) Å X Å Y EY(X) Å X Å Y EY(X Å Y) Å X | EX(Y) Å Y EX(X Å Y) Å X Å Y EX(Y) Å X Å Y EX(X Å Y) Å Y | EX Å Y(X) Å X EX Å Y(Y) Å Y EX Å Y(X) Å Y EX Å Y(Y) Å X |
Трудоемкость подбора прообраза для однонаправленной функции или трудоемкость поиска второго- прообраза оцениваются величиной О(2n). В то же время трудоемкость поиска коллизии оценивается величиной О(2n/2), так как в данной ситуации применима атака, основанная на парадоксе "дней рождений".
Значением любой из хэш-функций, построенных из приведенных одношаговых сжимающих функций, является вектор длины n, равной размеру блока. В случае если эта величина оказывается недостаточной, ее можно увеличить, заменив одношаговую функцию f на функцию f’ с удвоенной размерностью значений. Это можно сделать, например, путем двукратного применения функции f с последующим перемешиванием полублоков согласно формуле:
f’(x, Hl, H2) = π(f(x, Hl), f(x, H2)),
в которой π переставляет произвольные полублоки а, b, с, d по правилу π((a,b),(c,d)) = (a,d,c,b) . Такой подход реализован в конструкции одношаговой функции MDC-2.
Другие примеры бесключевых хэш-функций дают известные алгоритмы MD-4, MD-5 и SHA. Они оперируют с блоками длины n, совпадающей с длиной результирующего значения свертки, причем п = 128 для алгоритма MD-4 и п = 160 для MD-5 и SHA. Указанные алгоритмы спроектированы специально с учетом эффективной реализации на 32-разрядных ЭВМ.
При их использовании исходное сообщение М разбивается на блоки длиной т = 512 бит. Последний блок формируется путем дописывания к концу сообщения комбинации 10...0 до получения блока размера 448 бит, к которому затем добавляется комбинация из 64 бит, представляющая битовую длину сообщения. Затем вычисляется значение свертки с использованием одношаговой сжимающей функции, заданной формулой f(x, H)=Ex(H) Å H, где х - блок сообщения длины т = 512 бит, Н - блок из п бит, а Ех - некоторое преобразование множества блоков. Значение начального вектора определяется в описании преобразования Ех. В стандарте хэш-функции ГОСТ Р 34.11-94 приняты значения п = т = 512. Одношаговая сжимающая функция f(x,H), используемая для вычисления последовательности значений Hi = f(xi, Hi-1), построена на базе четырех параллельно работающих схем блочного шифрования (ГОСТ 28147-89), каждая из которых имеет 256-битовый ключ и оперирует с блоками размера 64 бита. Каждый из ключей вычисляется в соответствии с некоторой линейной функцией от блока исходного сообщения xi и значения Hi-1. Значение Hi, является линейной функцией от результата шифрования, блока исходного сообщения xi, и значения Hi-1. После вычисления значения HN для последовательности блоков M1,M2,..,MN применяют еще два шага вычисления согласно формуле
H = h(M) = f(Z Å MN, f(L, HN)),
где Z — сумма по модулю два всех блоков сообщения, a L — длина сообщения.