Возможные атаки на функции хэширования

Простейшая атака с целью создания поддельного сообще­ния, применимая к любой хэш-функции, состоит в следую­щем. Злоумышленник может осуществить генерацию некото­рого числа (r₁) сообщений, вычислить значения их сверток и сравнить получившиеся значения с известными значениями сверток некоторого множества (из r₂) переданных ранее со­общений. Атака окажется успешной при получении хотя бы одного совпадения. Вероятность успеха Р можно оценить на основании парадокса "дней рождений". Известно, что эта ве­роятность оценивается по формуле

где п – длина свертки, е – основание натуральных логарифмов. Наибольшей эта вероятность становится при r₁ = r₂ = 2^п/2. В этом случае ее значение приблизительно равно 0,63.

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

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

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

Контрольные вопросы

1. Для каких целей применяются хэш-функции?

2. Перечислите основные требования, предъявляемые к хэш-функциям.

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

4. Сравните требования, предъявляемые к ключевым и бес­ключевым хэш-функциям.