Устойчивость к коллизиям

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

Определение и виды коллизий

Коллизией хеш-функции называется ситуация, когда для двух разных сообщений \( m_1 \) и \( m_2 \) (где \( m_1 \neq m_2 \)) выполняется равенство \( H(m_1) = H(m_2) \). Поскольку область значений хеш-функции (мощность множества возможных дайджестов) всегда меньше области определения (множества всех возможных сообщений), коллизии существуют для любой хеш-функции в силу принципа Дирихле. Однако устойчивость к коллизиям означает, что их нахождение вычислительно невозможно за приемлемое время.

Различают два основных типа атак, связанных с коллизиями:

• Слабая устойчивость к коллизиям (устойчивость к нахождению второго прообраза): Задача заключается в том, чтобы для заданного сообщения \( m_1 \) найти другое сообщение \( m_2 \), такое что \( H(m_1) = H(m_2) \). Эта задача считается более сложной, чем нахождение произвольной коллизии.
• Сильная устойчивость к коллизиям (устойчивость к коллизиям): Задача заключается в том, чтобы найти любую пару различных сообщений \( m_1 \) и \( m_2 \), для которых \( H(m_1) = H(m_2) \). Атакующий не ограничен выбором первого сообщения и может подбирать оба.

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

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

1. Вычислительная неосуществимость: Вероятность нахождения коллизии за полиномиальное время должна быть пренебрежимо мала. Практически это означает, что для нахождения коллизии требуется выполнить не менее \( 2^{n/2} \) операций хеширования, где \( n \) — длина дайджеста в битах (атака «дня рождения»).
2. Лавинный эффект: Малейшее изменение входного сообщения (даже на один бит) должно приводить к кардинальному изменению хеш-суммы, причём каждый бит выходного значения должен изменяться с вероятностью, близкой к 50%. Это затрудняет поиск сообщений с похожими дайджестами.
3. Однонаправленность: По значению хеш-суммы должно быть вычислительно невозможно восстановить исходное сообщение. Это свойство не является прямым следствием устойчивости к коллизиям, но обычно требуется вместе с ней.

Методы оценки и атаки

Устойчивость к коллизиям оценивается как криптоаналитиками, так и разработчиками. Основные методы атак:

• Атака «дня рождения»: Основана на парадоксе дней рождения. Для хеш-функции с длиной дайджеста \( n \) бит ожидаемое количество попыток для нахождения коллизии составляет примерно \( 2^{n/2} \). Например, для SHA-256 (256-битный дайджест) требуется около \( 2^{128} \) попыток, что считается недостижимым для современных вычислительных мощностей.
• Криптоаналитические атаки: Используют внутреннюю структуру хеш-функции (например, структуру Меркла-Дамгора или губки). Известные примеры: атака на MD5 (коллизии найдены в 2004 году группой Ван Сяоюня), атака на SHA-1 (первая практическая коллизия продемонстрирована в 2017 году компанией Google и CWI). Эти атаки позволяют находить коллизии значительно быстрее, чем методом «дня рождения».
• Дифференциальный криптоанализ: Анализирует, как различия во входных данных влияют на различия в выходных. Используется для поиска коллизий в хеш-функциях, построенных на основе блочных шифров.

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

История развития хеш-функций тесно связана с поиском устойчивых к коллизиям алгоритмов.

• MD5 (1991): Долгое время считался стандартом, но в 2004 году были найдены коллизии. В настоящее время MD5 не рекомендуется для использования в криптографических целях, хотя всё ещё применяется в некоторых небезопасных приложениях (например, для проверки целостности файлов в неконфиденциальных системах).
• SHA-1 (1995): Разработан АНБ США. В 2005 году были теоретически показаны атаки, снижающие сложность нахождения коллизий до \( 2^{69} \) операций. В 2017 году была продемонстрирована первая практическая коллизия (SHAttered). С 2017 года SHA-1 считается устаревшим, и его использование в криптографии запрещено или не рекомендуется большинством регуляторов (например, NIST).
• Семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512): Разработано после обнаружения уязвимостей в SHA-1. На 2024 год не имеет известных практических атак на устойчивость к коллизиям. Является текущим стандартом для большинства криптографических систем (TLS/SSL, цифровые подписи, блокчейн).
• SHA-3 (Keccak): Победитель конкурса NIST (2012). Основан на конструкции «губка», что обеспечивает иной уровень устойчивости к коллизиям по сравнению с SHA-2. На 2024 год также считается безопасным.
• BLAKE2, BLAKE3: Современные высокопроизводительные хеш-функции, не имеющие известных атак на коллизии. BLAKE3, в частности, оптимизирован для многопоточных вычислений.

Применение в информационной безопасности

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

• Цифровые подписи: Подпись ставится не на само сообщение, а на его хеш-сумму. Если злоумышленник сможет найти коллизию (два сообщения с одинаковым хешем), он может подменить подписанное сообщение на другое, не меняя подписи.
• Хранение паролей: Хеши паролей (с солью) должны быть устойчивы к коллизиям, чтобы злоумышленник не мог подобрать другой пароль, дающий тот же хеш (атака на второй прообраз). Однако для этой цели важнее устойчивость к нахождению прообраза и медленное хеширование (bcrypt, scrypt, Argon2).
• Контроль целостности: Хеш-суммы файлов (например, контрольные суммы ISO-образов) используются для проверки, что файл не был изменён. Если злоумышленник может подменить файл на другой с тем же хешем, целостность будет нарушена.
• Блокчейн и криптовалюты: В блокчейне (например, Bitcoin) хеш-функция SHA-256 используется для связывания блоков и майнинга. Устойчивость к коллизиям гарантирует, что нельзя подделать историю транзакций, подменив содержимое блока без изменения его хеша.
• Аутентификация сообщений (HMAC): В HMAC хеш-функция используется для создания кода аутентичности сообщения. Устойчивость к коллизиям необходима для предотвращения подделки ключа.

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

Несмотря на то, что устойчивость к коллизиям является строгим требованием, существуют ограничения:

• Теоретическая неизбежность: Как уже упоминалось, коллизии существуют для любой хеш-функции. Речь идёт только о практической невозможности их нахождения.
• Квантовая угроза: Квантовые компьютеры, использующие алгоритм Гровера, могут находить коллизии для хеш-функции с длиной дайджеста \( n \) бит за \( O(2^{n/3}) \) операций, что значительно быстрее классического \( O(2^{n/2}) \). Для SHA-256 это снижает сложность с \( 2^{128} \) до \( 2^{85} \) операций, что всё ещё считается практически недостижимым, но требует пересмотра стандартов в долгосрочной перспективе.
• Компромисс между скоростью и безопасностью: Некоторые хеш-функции (например, MurmurHash, CityHash) оптимизированы для скорости, но не являются криптографически стойкими и не гарантируют устойчивости к коллизиям. Они используются в хеш-таблицах, где коллизии допустимы (обрабатываются цепочками), но не в криптографии.

Стандарты и рекомендации в России

В Российской Федерации для криптографической защиты информации используются стандарты, установленные Федеральным законом № 63-ФЗ «Об электронной подписи» и методическими документами ФСБ России. Основным стандартом хеш-функции является ГОСТ Р 34.11-2012 («Стрибог»), который обеспечивает устойчивость к коллизиям с длиной дайджеста 256 или 512 бит. Этот стандарт обязателен для использования в государственных информационных системах и при создании усиленных квалифицированных электронных подписей. На 2024 год не известно о практических атаках на устойчивость к коллизиям ГОСТ Р 34.11-2012.

Источники

1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 2002.
2. Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. — CRC Press, 1996.
3. Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. — CRYPTO 2004.
4. Stevens M., Bursztein E., Karpman P., Albertini A., Markov Y. The first collision for full SHA-1. — CRYPTO 2017.
5. Федеральный закон № 63-ФЗ «Об электронной подписи» (с изменениями и дополнениями).
6. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хеширования. — М.: Стандартинформ, 2012.
7. NIST Special Publication 800-107. Recommendation for Applications Using Approved Hash Algorithms. — National Institute of Standards and Technology, 2012.