Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 4
© Сергей Панасенко, 2013
Продолжим рассмотрение атак на приложения и протоколы, в которых используется алгоритм хэширования MD5.
В ноябре 2005 г. вышла работа [1] двух известных экспертов по криптографии: Брюса Шнайера (Bruce Schneier) и Пола Хоффмана (Paul Hoffman), посвященная текущим атакам на алгоритмы хэширования MD5 и SHA-1 (в меньшей степени, чем MD5, поскольку атаки по поиску коллизий для SHA-1 на тот момент требовали несравнимо большей трудоемкости, чем атаки на MD5), широко используемые в различных сетевых протоколах. Эксперты классифицировали варианты использования алгоритмов хэширования в сетевых протоколах и пришли к выводу, что в подавляющем большинстве случаев применение абстрактных коллизий для конструирования практически применимых атак на сетевые протоколы невозможно, поскольку для этого требуются атаки, направленные на поиск прообраза, а не коллизии. Наиболее опасным применением абстрактных коллизий против сетевых протоколов авторы работы [1] посчитали рассмотренную в предыдущей части статьи атаку по конструированию двух сертификатов с эквивалентным хэш-значением MD5 [2], но и данная атака, по мнению Шнайера и Хоффмана, требовала выполнения слишком многих условий, противоречащих реальным процедурам выпуска сертификатов, что делает атаку практически неприменимой в реальном мире.
Тем не менее, авторы [1] сделали вывод о том, что необходимо задуматься о переходе на более стойкий алгоритм хэширования (в качестве которого они рекомендовали алгоритм SHA-256 [3]), а также о разработке сетевых протоколов, в которых было бы относительно просто переходить на новые алгоритмы хэширования при появлении эффективных атак против используемых алгоритмов).
Существенно менее оптимистичные выводы сделали авторы опубликованной в марте 2006 г. работы [4], которые показали, что опубликованные в течение 2005 г. атаки на приложения, использующие алгоритм MD5, весьма опасны для различных применений данного алгоритма. Авторы работы проанализировали степень подверженности атакам, основанным на абстрактных коллизиях, различных применений MD5 и сделали вывод о возможности успешных атак на некоторые из них – см. таблицу из работы [4]:
Применение | Возможность атаки | Атакуемые свойства |
---|---|---|
Подпись сообщений | Есть |
Неотказуемость, целостность |
Подпись существующих сертификатов | Нет |
|
Подпись новых сертификатов | Есть |
Аутентификация, неотказуемость |
HMAC | Нет |
|
Подмена существующих программ | Нет |
|
Подмена новых программ | Есть |
Неотказуемость, аутентификация, целостность |
Обсудим приведенные в таблице сведения.
Во всех приведенных в таблице случаях атаки имеют различные ограничения по возможности их применения. Тем не менее, атаки практически применимы, и факт их наличия должен был ускорить отказ от использования алгоритма MD5.
Что касается надстроек HMAC и NMAC, то первые известные попытки распространения атак на алгоритм MD5 на данные надстройки над алгоритмом были сделаны в том же 2006 г. в работах [7] и [8], которые обсуждались ранее в [9]. В части надстроек над MD5 авторы работы [8] предложили атаку на алгоритм NMAC-MD5, позволяющую получить следующие результаты:
Цель атаки | Требуемое количество данных | Трудоемкость |
---|---|---|
Вычисление внутреннего ключа k1 (см. [6]) | 247 |
1 |
Поиск второго прообраза для выбранного атакующим сообщения | 247 |
245 |
Атаки основаны на коллизиях внутренней функции хэширования алгоритма NMAC. В [8] отмечено, что внешняя функция хэширования скрывает результат выполнения внутренней функции, но не скрывает факт возникновения внутренней коллизии.
Несмотря на невысокую трудоемкость, данные атаки можно считать практически неприменимыми, поскольку:
Альтернативный вариант атаки по поиску второго прообраза для NMAC-MD5 был предложен в 2007 г. в работе [10]. Атака принципиально отличается от опубликованной в [8] тем, что она позволяет найти второй прообраз для произвольного сообщения (т. е. это первая известная реальная атака, направленная на поиск прообраза для NMAC-MD5). Опубликованная в [10] атака также использует связанные ключи; ее требования к ресурсам, однако, существенно выше: для успешной атаки требуется 251 блоков данных при трудоемкости 2100 операций. Таким образом, данная атака также не является практически применимой.
Литература