Стойкость к коллизиям

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

Определение и сущность

Коллизией в контексте хеш-функции называется ситуация, когда два различных входных сообщения A и B (где A ≠ B) после обработки функцией H дают одинаковый хеш: H(A) = H(B). Поскольку область возможных входных данных бесконечна, а длина выходного хеша фиксирована (например, 256 бит для SHA-256), коллизии теоретически неизбежны согласно принципу Дирихле (принципу ящиков). Однако задача стойкой к коллизиям хеш-функции — сделать так, чтобы практическое нахождение любой коллизии было вычислительно невозможно или требовало ресурсов, значительно превышающих доступные атакующему.

Стойкость к коллизиям формально определяется как вычислительная неосуществимость нахождения любой пары различных сообщений, дающих одинаковый хеш, за время, меньшее, чем 2^(n/2) операций, где n — длина хеша в битах. Это значение связано с парадоксом дней рождения: вероятность коллизии в наборе случайных хешей становится высокой, когда количество попыток достигает квадратного корня от размера пространства хешей.

Классификация и виды стойкости

Различают несколько уровней стойкости хеш-функций, которые образуют иерархию:

Стойкость к коллизиям (Collision Resistance)

Это наиболее сильное требование. Атакующий может выбирать оба сообщения произвольно. Его задача — найти любую пару (A, B), такую что H(A) = H(B). Успешная атака на этот уровень означает полную компрометацию хеш-функции для большинства криптографических применений.

Стойкость к нахождению второго прообраза (Second Preimage Resistance)

Атакующему дано сообщение A и его хеш H(A). Он должен найти другое сообщение B (B ≠ A), такое что H(B) = H(A). Это свойство слабее, чем стойкость к коллизиям: если функция нестойка к коллизиям, это не обязательно означает её нестойкость к нахождению второго прообраза, но на практике потеря первого свойства обычно влечёт за собой уязвимость и ко второму.

Стойкость к восстановлению прообраза (Preimage Resistance)

Атакующему дан только хеш h. Он должен найти любое сообщение A, такое что H(A) = h. Это самое слабое из трёх свойств. Функция может быть стойкой к восстановлению прообраза, но нестойкой к коллизиям.

История и примеры атак

Развитие криптографии тесно связано с историей атак на стойкость к коллизиям. Первые широко распространённые хеш-функции, такие как MD4 и MD5, были разработаны Рональдом Ривестом в начале 1990-х годов. Однако к концу 1990-х — началу 2000-х годов были найдены серьёзные уязвимости.

MD5

В 2004 году группа китайских исследователей (Ван Сяоюнь, Фэн Дэнго, Лай Сюэцзя и Юй Хунбо) продемонстрировала первую практическую атаку на коллизию для MD5, используя метод дифференциального криптоанализа. Атака требовала всего около 2^39 операций, что было выполнимо на обычном компьютере за несколько часов. Позднее атаки были усовершенствованы, и коллизии для MD5 стали находиться за секунды. После этого MD5 был признан нестойким к коллизиям и не рекомендуется к использованию в криптографических целях.

SHA-1

Стандарт SHA-1, разработанный АНБ США и опубликованный в 1995 году, долгое время считался надёжным. Однако в 2005 году те же китайские исследователи объявили об атаке на SHA-1 со сложностью 2^69 операций, что значительно ниже теоретической границы 2^80. В 2017 году компания Google совместно с Центром математики и информатики (CWI) в Нидерландах опубликовала первую практическую коллизию для полного SHA-1 (атака SHAttered). Для её нахождения потребовалось 9·10^18 операций SHA-1, что эквивалентно 6500 годам работы одного процессора (или 110 годам работы GPU). После этого SHA-1 был официально объявлен устаревшим, и большинство организаций перешли на SHA-2.

SHA-2 и SHA-3

Семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) было разработано АНБ в 2001 году и на данный момент (2024 год) считается стойким к коллизиям. Атак, которые бы угрожали его практической безопасности, не опубликовано. SHA-3 (Keccak), принятый NIST в 2015 году, был разработан как альтернатива SHA-2 на случай, если в последнем будут найдены уязвимости. Он также обладает заявленной стойкостью к коллизиям.

Применение

Стойкость к коллизиям критически важна в следующих областях:

Цифровые подписи

В схемах цифровой подписи (например, RSA, DSA, ECDSA) сначала вычисляется хеш сообщения, а затем подписывается именно хеш, а не всё сообщение. Если атакующий может найти коллизию, то он может подменить одно сообщение другим, имеющим тот же хеш, и подпись останется действительной для подменённого сообщения. Это может привести к подделке контрактов, финансовых документов или программного обеспечения.

Хранение паролей

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

Контроль целостности

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

Блокчейн и криптовалюты

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

Критика и ограничения

Концепция стойкости к коллизиям имеет ряд ограничений и критических замечаний:

• Теоретическая неизбежность: Как уже отмечалось, коллизии существуют для любой хеш-функции с фиксированной длиной выхода. Речь идёт лишь о вычислительной сложности их нахождения.
• Квантовая угроза: С развитием квантовых компьютеров, алгоритм Гровера позволяет ускорить поиск коллизий. Для хеш-функции с длиной выхода n бит, квантовый алгоритм может найти коллизию за O(2^(n/3)) операций, что требует увеличения длины хеша (например, до 384 или 512 бит) для сохранения безопасности в постквантовую эпоху.
• Атаки по сторонним каналам: Даже если хеш-функция математически стойка, её программная или аппаратная реализация может быть уязвима для атак по времени выполнения, энергопотреблению или электромагнитному излучению, что может косвенно помочь в нахождении коллизий.
• Неоднозначность термина: В некоторых контекстах (например, в хеш-таблицах) термин «стойкость к коллизиям» может означать не криптографическую стойкость, а просто низкую вероятность коллизий при случайном выборе ключей, что достигается правильным выбором хеш-функции и размером таблицы.

Интересные факты

• Парадокс дней рождения, лежащий в основе оценки стойкости к коллизиям, утверждает, что в группе из 23 человек вероятность того, что у двух человек совпадут дни рождения, превышает 50%. Для хешей это означает, что для 256-битной функции достаточно сделать 2^128 попыток, чтобы с высокой вероятностью найти коллизию.
• В 2019 году была опубликована атака на хеш-функцию SHA-1, получившая название SHAttered, которая показала, что коллизию можно найти за 10 дней работы 110 GPU. Это стало последним ударом по доверию к SHA-1.
• Некоторые хеш-функции, такие как BLAKE2 и BLAKE3, специально оптимизированы для высокой скорости работы на современных процессорах, сохраняя при этом заявленную стойкость к коллизиям.

Источники

1. Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
2. Wang, X., Feng, D., Lai, X., & Yu, H. (2004). Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. Cryptology ePrint Archive.
3. Stevens, M., Bursztein, E., Karpman, P., Albertini, A., & Markov, Y. (2017). The first collision for full SHA-1. CRYPTO 2017.
4. NIST. (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. FIPS PUB 202.
5. Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum cryptanalysis of hash and claw-free functions. ACM SIGACT News.