Стандарты Хеш-функций. Основные определения и требования безопасности к функциям хеширования, страница 2

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

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

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

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

Ниже опишем лучшие известные атаки на функции хеширования [6].

1. Атака “грубой силой” или атака случайного (второго) прообраза может быть выполнена для нахождения прообраза по заданному хэш-значению или для нахождения прообраза, который даёт заданное хэш-значение. Суть атаки заключается в последовательном или случайном переборе входных сообщений и сравнения результата выполнения функции хеширования с заданным. Успех атаки при равновероятных выпадениях хеш результатов будет равна , где  - длина хеш-значения в битах. Сложность такой атаки оценивается  операций вычисления хеш-значений.

2. Атака методом “дня рождения” выполняется для нахождения двух различных сообщений с одинаковыми хеш-значениями. Эта атака основана на парадоксе “дня рождения” и заключается в том, что в двух сгенерированных множествах хеш-значений, содержащих n₁ и n₂ элементов соответственно, вероятность нахождения совпадающих элементов между этими множествами оценивается выражением: . При  сложность атаки оценивается как  операций вычисления хеш-значений, а вероятность успеха равна .

3. Атака “встреча посередине” [7] является модификацией атаки методом “дня рождения” и используется для хеш-функций с циклической структурой, если цикловая функция  инвертируема по отношению к промежуточному значению  или блоку сообщения . Эта атака по сложности сопоставима с атакой методом “дня рождения”.

4. Атака с коррекцией блока используется в случае, если атакующий обладает сообщением и хочет изменить в нем один или более блоков без изменения хеш-значения. Один цикл MD5 уязвим к этой атаке: атакующий берет блок сообщения  (16 слов по 32 бита), оставляет 11 слов, модифицирует одно слово, и вычисляет оставшиеся 4. В результате получается блок , отображающийся в то же самое хеш-значение, что и . Полная версия MD5 не уязвима к этой атаке.

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