Введение

Криптографическая атака

В криптографии коллизионная атака на криптографическую хеш-функцию пытается найти два различных входных значения, дающих одно и то же хеш-значение, то есть коллизию хешей. Это отличается от атаки по прообразу, где задаётся конкретное целевое хеш-значение. Существуют, в основном, два типа коллизионных атак:
Классическая коллизионная атака: найти два различных сообщения m1 и m2, таких, что hash(m1) = hash(m2). В более общем случае:
Атака на коллизию с выбранными префиксами: заданы два различных префикса p1 и p2, необходимо найти два суффикса s1 и s2, такие, что hash(p1 ∥ s1) = hash(p2 ∥ s2), где ∥ обозначает операцию конкатенации.

Классическая атака столкновения

Подобно тому, как симметричные шифры уязвимы для атак полным перебором, каждая криптографическая хеш-функция по своей сути уязвима к коллизиям с использованием атаки «день рождения». Из-за парадокса дней рождения эти атаки значительно быстрее, чем атаки полным перебором. Хеш-функцию с n битами можно взломать за 2<sup>n/2</sup> шагов (вычислений хеш-функции). Математически, атака на коллизии находит два различных сообщения m1 и m2, таких что hash(m1) = hash(m2). В классической атаке на коллизии злоумышленник не контролирует содержимое ни одного из сообщений, но они выбираются алгоритмом случайным образом. Более эффективные атаки возможны при использовании криптоанализа для конкретных хеш-функций. Если обнаружена атака на коллизии, которая оказывается быстрее атаки «день рождения», хеш-функцию часто объявляют «скомпрометированной». Конкурс хеш-функций NIST был во многом вызван опубликованными атаками на коллизии против двух широко используемых хеш-функций: MD5 и SHA-1. Атаки на коллизии MD5 настолько улучшились, что к 2007 году на обычном компьютере они занимают всего несколько секунд. Хеш-коллизии, созданные таким образом, обычно имеют фиксированную длину и слабо структурированы, поэтому их нельзя напрямую использовать для атак на распространенные форматы документов или протоколы. Однако возможны обходные пути, использующие динамические конструкции, присутствующие во многих форматах. Таким образом, создаются два документа, максимально похожих друг на друга, чтобы иметь одинаковое хеш-значение. Один документ предъявляется для подписи, а затем подпись копируется в другой файл. Такой вредоносный документ будет содержать два разных сообщения в одном и том же файле, но условно отображать одно или другое посредством незначительных изменений в файле:

Некоторые форматы документов, такие как PostScript или макросы в Microsoft Word, имеют условные конструкции (if-then-else), позволяющие проверять, имеет ли определенное местоположение в файле одно значение или другое, чтобы контролировать отображаемое содержимое. Файлы TIFF могут содержать обрезанные изображения, при этом отображается другая часть изображения без изменения хеш-значения. Реальная атака на коллизии была опубликована в декабре 2008 года, когда группа исследователей в области безопасности опубликовала поддельный сертификат подписи X.509, который можно было использовать для выдачи себя за центр сертификации, воспользовавшись атакой на коллизии префиксов против хеш-функции MD5. Это означало, что злоумышленник мог выдать себя за любой веб-сайт, защищенный SSL, действуя как «человек посередине» и тем самым подрывая встроенную в каждый веб-браузер проверку сертификатов, предназначенную для защиты электронной коммерции. Поддельный сертификат может быть не отозван реальными центрами сертификации и может иметь произвольный поддельный срок действия. Несмотря на то, что MD5 был признан очень слабым еще в 2004 году, по крайней мере один сертификат подписи кода Microsoft все еще использовал MD5 в мае 2012 года. Вредоносное ПО Flame успешно использовало новую вариацию атаки на коллизии выбранных префиксов для подделки подписи кода своих компонентов корневым сертификатом Microsoft, который все еще использовал скомпрометированный алгоритм MD5. В 2019 году исследователи обнаружили атаку на коллизии выбранных префиксов против SHA-1 с вычислительной сложностью от 2<sup>66.9</sup> до 2<sup>69.4</sup> и стоимостью менее 100 000 долларов США. В 2020 году исследователи снизили сложность атаки на коллизии выбранных префиксов против SHA-1 до 2<sup>63.4</sup>.

Сценарии атаки

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

Наводнение гашишем

Hash flooding (также известный как HashDoS) — это атака типа «отказ в обслуживании», использующая коллизии хэшей для эксплуатации наихудшего случая (линейного поиска) времени выполнения операций поиска в хеш-таблице. Она была впервые описана в 2003 году. Для осуществления такой атаки злоумышленник отправляет серверу множество данных, которые приводят к одному и тому же значению хэша, а затем пытается заставить сервер выполнять медленные операции поиска. Поскольку основное внимание при разработке хеш-функций, используемых в хеш-таблицах, уделялось скорости, а не безопасности, большинство основных языков программирования оказались уязвимы, и новые уязвимости этого типа продолжают появляться даже спустя десятилетие после первоначального описания. (Незащищённые "простые" хеши остаются безопасными для использования, если хеш-таблица приложения не контролируется извне.) Возможно проведение аналогичной атаки для переполнения фильтров Блума с использованием (частичной) атаки по нахождению прообраза.