Атаки дней рождения и коллизий

В группе из 23 человек вероятность того, что у двух из них день рождения в один день, превышает 50%. Для 70 человек она превышает 99,9%. Математически в множестве размера N вероятность коллизии превышает 50% после примерно √N образцов. Это и есть граница дней рождения.

Для хеш-функции с n-битным результатом коллизию (H(m1) = H(m2), m1 ≠ m2) можно найти примерно за 2^{n/2} случайных попыток. Для SHA-256 с результатом 256 бит поиск коллизии требует примерно 2^{128} операций, что вычислительно невыполнимо. Для MD5 с результатом 128 бит требуется примерно 2^{64} операций, что уже находится на грани практической реализуемости.

Общий поиск коллизий: сгенерировать 2^{n/2} случайных сообщений, вычислить хеши, отсортировать их по значению хеша и найти дубликаты. Память O(2^{n/2}). Алгоритм ро, использующий поиск циклов Флойда, уменьшает потребление памяти до O(1) при той же временной сложности. Параллельный поиск коллизий ван Оорсхота—Винера сокращает время за счёт аппаратных ресурсов.

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

Более мощный вариант: для двух произвольных префиксов P1 и P2 найдите суффиксы S1 и S2 такие, чтобы H(P1||S1) = H(P2||S2). Стивенс и его коллеги в 2017 году нашли коллизии MD5 с выбранным префиксом. Это позволило создать вредоносный сертификат CA с действительной подписью MD5. После этого MD5 перестали использовать для сертификатов.

SHAttered от Google (2017) — первая практическая коллизия SHA-1. Два разных файла PDF имеют одинаковый хеш SHA-1. Для атаки потребовалось 2^{63.1} вычислений сжатия SHA-1, что эквивалентно 6500 годам вычислений на CPU и 110 годам вычислений на GPU. Стоимость составила примерно 110 000 долларов. В 2017 году браузеры отказались от сертификатов SHA-1.

Для хеш-функций Меркла—Дамгарда (MD5, SHA-1, SHA-2): если известно H(m), можно вычислить H(m||padding||m'), не зная m. Это нарушает конструкции MAC, такие как H(secret||message). Решение: используйте HMAC (в котором применяются внутреннее и внешнее дополнение) или SHA-3 (губчатая конструкция, невосприимчивая к расширению длины).

Устойчивость к коллизиям: найти любые два различных сообщения с одинаковым хешем (требуется 2^{n/2} операций). Устойчивость ко второму прообразу: для заданного m найти m' ≠ m с таким же хешем (требуется 2^n операций). Устойчивость к нахождению прообраза: найти любое сообщение для заданного хеша (требуется 2^n операций). Устойчивость к коллизиям всегда самая слабая.

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

Joux (2004): для хеш-функций Меркла—Дамгарда поиск коллизий для 2^k сообщений с одинаковым хешем требует лишь в k раз больше работы, чем поиск одной коллизии, а не в k раз больше на каждом этапе. Это усиливает уязвимости объединённых хешей (H1(m)||H2(m) не настолько надёжен, как может показаться).

Используйте SHA-256 или SHA-3 для хеширования с устойчивостью к коллизиям. Не используйте MD5 и SHA-1 в целях безопасности. Для MAC: HMAC-SHA-256 или HMAC-SHA-3. Для хеширования паролей: Argon2 (а не SHA-2 напрямую). Всегда используйте SHA-3, когда требуется устойчивость к расширению длины.

Примерно сколько вычислений хеша требуется, чтобы найти коллизию в хеш-функции с длиной хеша n бит?

Атака дней рождения находит коллизии хеша за 2^{n/2} операций. Для MD5 существуют практические коллизии с выбранным префиксом; SHA-1 был взломан в 2017 году. Атаки расширения длины нарушают наивные MAC H(key||msg). Используйте SHA-256 или SHA-3; для аутентификации сообщений используйте HMAC. Далее: атаки «встреча посередине».