Бесключевые функции хэширования

Обычно требуется, чтобы бесключевые хэш-функции об­ладали следующими свойствами:

1) однонаправленность,

2) устойчивость к коллизиям,

3) устойчивость к нахождению второго прообраза,

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

Например, хэш-функция CRC-32, представляющая собой контрольную сумму, является линейным отображением и по­этому не удовлетворяет ни одному из этих трех свойств.

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

Для построения примера хэш-функции, удовлетворяющей свойству 1), рассмотрим функцию, заданную формулой g_k(х)=Е_k(х)Åx, где Е_k - алгоритм блочного шифрования. Такая функция является однонаправленной по обоим аргументам. Поэтому на ее основе можно построить хэш-функцию по правилу (7.1), определив одношаговую сжимающую функ­цию одной из следующих формул:

f(х,H)=Е_H(х)Åx

или

f(х,H)=Е_x(H)ÅH.

Первая из этих функций лежит в основе российского стандарта хэш-функции, а вторая – в основе американского стандарта SHA.

Справедливо следующее

Утверждение 1. Если функция хэширования h построена на основе одношаговой сжимающей функции f по правилу (7.1), то из устойчивости к коллизиям функции f следует устойчивость к коллизиям функции h.

Укажем взаимозависимость между свойствами 1) и 2).

Утверждение 2. Если хэш-функция устойчива к коллизиям, то она устойчива к нахождению второго прообраза.

Утверждение 3. Устойчивая к коллизиям хэш-функция не обязана быть однонаправленной.

В качестве примера несжимающей функции приведем функцию h(x)=x, которая, очевидно, является устойчивой к коллизиям и к нахождению второго прообраза, но не явля­ется однонаправленной.

В качестве примера сжимающей хэш-функции рассмот­рим функцию h, определенную условиями

h(x) = (1, х), если битовая длина х равна п,

h(x) = (0, g(x)), если битовая длина х больше п,

где g(x) – сжимающая п-битовая функция, устойчивая к кол­лизиям. Функция h также является устойчивой к коллизиям и к нахождению второго прообраза, но, очевидно, не является однонаправленной.

Утверждение 4. Пусть h': X —>Y – хэш-функция и |Х| > 2|Y|. Тогда если существует эффективный алгоритм обращения функции h, то существует вероятностный алго­ритм нахождения коллизии функции h с вероятностью успе­ха, большей 1/2.

Заметим, что трудоемкость подбора прообраза для однонаправленной функции или трудоемкость поиска второго прообраза оцениваются величиной 0(2^п). В то же время трудоемкость поиска коллизии оценивается величиной 0(2^п/2), так как в данной ситуации применима атака, основанная на парадокce "дней рождений".

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

Пусть E_k – алгоритм блочного шифрования, п – размер блока, l – размер ключа и G – некоторое отображение, ставящее в соответствие вектору длины п вектор длины l. Рассмотрим следующие одношаговые сжимающие функции, построенные на основе алгоритма E_k:

а) f(х,H)=E_x (H)ÅH (Дэвис-Мейер);

б) f(х,H)=E_G(H) (x)Åx (Матиас-Мейер-Осеас);

в) f(х,H)=E_G(H) (x)ÅxÅН (Миагучи-Принель).

Значением любой из хэш-функции, построенных по правилу (7.1) из приведенных одношаговых сжимающих функций, является вектор длины п, равной размеру блока. В случае если эта величина оказывается недостаточной, ее можно увели­чить, заменив одношаговую функцию f на функцию f' с удвоенной размерностью значений. Это можно сделать, например, путем двукратного применения функции f с последующим перемешиванием полублоков согласно формуле:

f '(х, Н₁, Н₂)= p( f (х, Н₁), f (х, Н₁)),

в которой p переставляет произвольные полублоки а, b, с, d по правилу p((а,b),(с,d)) = (a,d,c,b). Такой подход, использующий схему (б), реализован в конструкции одношаго­вой функции MDC-2.

Другие примеры бесключевых хэш-функций дают из­вестные алгоритмы MD-4, MD-5 и SHA. Они оперируют с блоками длины п, совпадающей с длиной результирующего значения свертки, причем п = 128 для алгоритма MD-4 и п= 160 для MD-5 и SHA. Указанные алгоритмы спроектированы специально с учетом эффективной реализации на 32-разрядных ЭВМ.

При их использовании исходное сообщение М разбивает­ся на блоки длиной т= 512 бит. Последний блок формирует­ся путем дописывания к концу сообщения комбинации 10...0 до получения блока размера 448 бит, к которому затем добав­ляется комбинация из 64 бит, представляющая битовую длину сообщения. Затем вычисляется значение свертки согласно процедуре (7.1) с использованием одношаговой сжимающей функции, заданной формулой f(x,H)= E_x (H)ÅH , где х — блок сообщения длины т = 512 бит, Н— блок из п бит, a E_x — некоторое преобразование множества блоков. Значение на­чального вектора определяется в описании преобразования E_x.

В стандарте хэш-функций ГОСТ Р 34.11-94 приняты зна­чения п = т = 512. Одношаговая сжимающая функция f(x,H), используемая для вычисления последовательности значений Н_i = f(х_i, Н_i-1), построена на базе четырех парал­лельно работающих схем блочного шифрования (ГОСТ 28147-89), каждая из которых имеет 256-битовый ключ и опе­рирует с блоками размера 64 бита. Каждый из ключей вычис­ляется в соответствии с некоторой линейной функцией от блока исходного сообщения х_i и значения H_i-1. Значение Н_i является линейной функцией от результата шифрования, бло­ка исходного сообщения х_i и значения Н_i-1. После вычисления значения H_N для последовательности блоков М₁,М₂,..,М_N применяют еще два шага вычисления согласно формуле

Н = h(М) = f(Z Å М_N, f(L, Н_N )),

где Z - сумма по модулю два всех блоков сообщения, a L – длина сообщения.