Стойкость (безопасность) хэш-функций

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

Атака, основанная на «парадоксе дня рождения», заключается в следующем. Пусть a предметов выбираются с возвращением из некоторого множества с мощностью n. Тогда вероятность того, что два из них окажутся одинаковыми, составляют.

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

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

Предположим, что есть две программы m₁ и m₂. Первая программа достоверна, а для второй криптоаналитик пытается получить то же самое значение хэш-кода, выдав таким образом программу m₁ за программу m₂ (то есть криптоаналитик пытается получить коллизию). Для этого криптоаналитик подготавливает порядка различных, незначительно отличающихся версий m₁ и m₂ и для каждой из них вычисляет хэш-код. С высокой вероятностью криптоаналитику удается обнаружить пару версий m`<sub>1</sub> и m`₂, имеющих один и тот же хэш-код.

В дальнейшем при использовании данного хэш-кода можно выдать программу m`<sub>2</sub> вместо программы m`₁, содержание которой близко к содержанию программы m₁.

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

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

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

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

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

Алгоритм DES (в режиме CFB) можно использовать в качестве базового, например, в следующей хэш-функции (с получением хэш-кода H=h (M, I)=H_n):

шифрование компьютерный хэширование Другие примеры хэш-функций на основе алгоритмов шифрования. N-хэш алгоритм разработан фирмой Nippon Telephone Telegraph в 1990 году. N-хэш алгоритм использует блоки длиной 128 битов, шифрующую функцию, аналогичную функции алгоритма шифрования FEAL, и вырабатывает блок хэш-кода длиной 128 битов.

На вход пошаговой хэш-функции в качестве аргументов поступают очередной блок кода M_i длиной 128 битов и хэш-код H_i-1 предыдущего шага также размером 128 битов. При этом H₀=I, а H_i=E_k(M_i, H_i-1)M_iH_i-1. Хэш-кодом всего кода программы объявляется хэш-код, получаемый в результате преобразования последнего блока текста.

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

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

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