Практические аспекты построения хэш-функций

Основные определения, обозначения и алгоритмы. Введем следующие обозначения. Хэш-функция h обозначается как А (а) и /?(а, Р) для одного и двух аргументов соответственно. Хэш-код функции h обозначается как Я. При этом Я₀= / обозначает начальное значение (вектор инициализации) хэш-функции. Под обозначением © будет пониматься операция сложения по модулю 2 или логическая операция XOR (исключающее ИЛИ). Результат шифрования блока В блочным шифром на ключе k обозначается E_k(B).

Для лучшего понимания дальнейшего материала приведем небольшой пример построения хэш-функции. Предположим нам необходимо получить хэш-код для некоторого сообщения М. В качестве шифрующего преобразования в хэш-функции будут использоваться процедуры шифра DES с ключом k. Тогда чтобы получить хэшкод Я сообщения М при помощи хэш-функции h необходимо выполнить следующую итеративную операцию:

где сообщение М разбито на п 64-битных блока. Хэш-кодом данной хэш-функции является значение Я = h (M, Г) = Н_гГ

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

Атака, основанная на «парадоксе дня рождения», заключается в следующем. Пусть а4п предметов выбираются с возвращением из некоторого множества с мощностью п. Тогда вероятность того, что два из них окажутся одинаковыми, составляет 1 — е~^а2/2.

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

Например, для криптоанализа хэш-функций, основанных на использовании криптоалгоритма DES, указанная атака может быть проведена следующим образом. Пусть п — мощность области хэшкодов (для криптоалгоритма DES она равна 2⁶⁴). Предположим, что есть два сообщения т_л и т₂. Первое сообщение достоверно, а для второго криптоаналитик пытается получить то же самое значение хэш-кода, выдав таким образом сообщение т_л за сообщение т₂ (т.е. криптоаналитик пытается получить коллизию). Для этого криптоаналитик подготавливает порядка Jn различных, незначительно отличающихся версий т_{ и т₂ и для каждой из них вычисляет хэшкод. С высокой вероятностью криптоаналитику удается обнаружить пару версий т и т'₂, имеющих один и тот же хэш-код. В дальнейшем при использовании данного хэш-кода можно выдать сообщение т₂ вместо сообщения т, содержание которого близко к содержанию сообщения т_{.

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

Методы построения криптографически стойких хэш-функций. Практические методы построения хэш-функций можно условно разделить на три группы: методы построения хэш-функций на основе какого-либо алгоритма шифрования (пример, приведенный выше), методы построения хэш-функций на основе какой-либо известной вычислительно трудной математической задачи и методы построения хэш-функций «с нуля».

Рассмотрим примеры построения хэш-функций на основе алгоритмов шифрования. Наряду с примером, приведенным выше, покажем, как строить хэш-функции на основе наиболее известных блочных шифров ГОСТ 28 147–89, DES и FEAL.

В качестве шифрующего преобразования будут использоваться некоторые режимы шифров ГОСТ 28 147–89, DES и FEAL с ключом k. Тогда чтобы получить хэш-код Я сообщения М при помощи хэш-функции /г, необходимо выполнить следующую итеративную операцию (например, с использованием алгоритма ГОСТ 28 147–89):

Таким образом, хэш-кодом данной хэш-функции является значение Я = А (М, Г) = Н_п. При этом используется режим выработки имитовставки ГОСТ 28 147–89, а шифрующее преобразование 64-битовых блоков заключается в выполнении 16 циклов алгоритма шифрования в режиме простой замены.

Алгоритм DES (в режиме СЕВ) можно использовать в качестве базового, например, в следующей хэш-функции (с получением хэш-кода Я = h (M, /) = Я_н):

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

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

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

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

Алгоритм MD4 (Message Digest) был разработан Р. Ривес.том. Размер вырабатываемого хэш-кода — 128 битов. По заявлениям самого разработчика, при создании алгоритма он стремился достичь следующих целей.

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

Алгоритм MD5 является доработанной версией алгоритма MD4. Аналогично MD4 в алгоритме MD5 размер хэш-кода равен 128 битам. После ряда начальных действий MD5 разбивает текст на блоки длиной 512 битов, которые, в свою очередь, делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хэш-код.

В 1993 г. Национальный институт стандартов и технологий (NIST) США совместно с Агентством национальной безопасности (NSA) США выпустили «Стандарт стойкой хэш-функции» (secure hash standard), частью которого является алгоритм SHA. Агентство национальной безопасности США периодически объявляет конкурсы на построение практически значимых и криптографически стойких хэш-функций.

Предложенная процедура вырабатывает хэш-код длиной 160 битов для произвольного текста длиной менее 264 битов. Разработчики считают, что для SHA невозможно предложить алгоритм, имеющий разумную трудоемкость, который строил бы два различных набора данных, дающих один и тот же хэш-код (т.е. алгоритм, находящий коллизии). Алгоритм SHA основан на тех же самых принципах, которые использовал Р. Ривест при разработке MD4, более того, алгоритмическая структура SHA очень похожа на структуру MD4. Процедура дополнения хэшируемого текста до кратного 512 битам полностью совпадает с процедурой дополнения алгоритма MD5.

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

• • любой из известных алгоритмов построения коллизий не должен быть эффективнее метода, основанного на «парадоксе дня рождения»;
• • алгоритм должен допускать эффективную программную реализацию на 32- или 64-разрядном процессоре;
• • алгоритм не должен использовать сложных структур данных и подпрограмм;
• • алгоритм должен быть оптимизирован с точки зрения его реализации на широко распространенных микропроцессорах (например, семейства х86 Intel).