Методы криптоанализа хэш-функций

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

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

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

Метод требует большого объема памяти для хранения генерируемых наборов, а также эффективных методов сортировки.

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

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

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

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

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