Коллизия хэш-функции

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

Природа возникновения

Коллизия возникает из-за принципа «принципа Дирихле» (или «принципа ящиков»): если количество возможных входных сообщений превышает количество возможных выходных хэшей, то как минимум два разных входа должны дать один и тот же выход. Например, для хэш-функции с выходом длиной 256 бит существует 2^256 возможных хэш-значений. Количество возможных входных сообщений (например, всех текстов длиной до 1000 символов) значительно превышает это число, что гарантирует наличие коллизий.

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

• Слабая коллизия (свойство второго прообраза): для заданного входного сообщения x сложно найти другое сообщение x' такое, что h(x) = h(x').
• Сильная коллизия (свойство коллизионной стойкости): сложно найти любую пару различных сообщений x и x' таких, что h(x) = h(x').

История и известные атаки

Ранние уязвимости (1990-е — 2000-е годы)

Первые практические атаки на коллизии были продемонстрированы для устаревших хэш-функций. В 2004 году китайские криптографы Сяоюнь Ван и Хунбо Ю опубликовали атаки на MD4, MD5, SHA-0 и SHA-1. Для MD5 была найдена коллизия за время, значительно меньшее теоретической оценки (2^64 операций). В 2005 году Ван и соавторы представили первую практическую коллизию для SHA-1, хотя её сложность была ещё высока (2^69 операций вместо 2^80).

Атака на SHA-1 (2017 год)

В 2017 году компания Google совместно с Центром математики и информатики (CWI) в Амстердаме объявила о первой практической коллизии для SHA-1. Атака получила название SHAttered. Исследователи создали два различных PDF-файла с одинаковым SHA-1-хэшем. Для этого потребовалось около 6500 лет процессорного времени (в пересчёте на один процессор) и 110 графических процессоров (GPU), работавших несколько месяцев. Стоимость атаки оценивалась в несколько сотен тысяч долларов. Это событие привело к окончательному отказу от SHA-1 в большинстве протоколов (TLS, Git, SSL-сертификаты).

Атаки на MD5 и SHA-1 в контексте цифровых подписей

Коллизии MD5 и SHA-1 активно использовались для создания поддельных цифровых подписей. В 2008 году исследователи из Университета Эйндховена и Университета Джона Хопкинса продемонстрировали атаку на цифровые сертификаты, использующие MD5. Они создали поддельный сертификат, который был принят браузерами как действительный. В 2019 году была опубликована атака SHAttered на сертификаты SHA-1, что ускорило отказ от этой функции.

Классификация и причины

Криптографические свойства, предотвращающие коллизии

Идеальная хэш-функция должна обладать следующими свойствами:

• Коллизионная стойкость: вычислительно невозможно найти два различных сообщения с одинаковым хэшем.
• Стойкость к нахождению прообраза: по заданному хэшу вычислительно невозможно найти исходное сообщение.
• Стойкость к нахождению второго прообраза: по заданному сообщению вычислительно невозможно найти другое сообщение с тем же хэшем.

Причины уязвимости

Уязвимости возникают из-за недостатков в конструкции функции:

• Слабая диффузия: изменения во входных данных плохо распространяются по внутреннему состоянию.
• Недостаточная нелинейность: использование линейных или слабо нелинейных операций.
• Короткая длина выхода: чем короче хэш, тем больше вероятность коллизии (парадокс дней рождения).
• Атаки на сжатие: использование математических методов для нахождения коллизий в отдельных раундах сжатия.

Применение и последствия

Криптография и цифровые подписи

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

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

Хэширование паролей (например, с помощью bcrypt, scrypt, Argon2) уязвимо к коллизиям, если злоумышленник может найти пароль, дающий тот же хэш, что и исходный. Однако на практике для атаки на пароли чаще используется атака по словарю или радужным таблицам, а не поиск коллизий.

Проверка целостности данных

Коллизии позволяют подменить файл (например, исполняемый файл, образ диска) так, что его хэш останется неизменным. Это используется для распространения вредоносного ПО, когда злоумышленник создаёт файл с тем же хэшем, что и легитимный, но с другим содержимым.

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

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

Современные стойкие хэш-функции

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

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512): разработана АНБ США в 2001 году. Считается стойкой к коллизиям, хотя теоретические атаки на усечённые версии существуют.
• SHA-3 (Keccak): победитель конкурса NIST 2012 года. Основана на губчатой конструкции, устойчива к известным типам атак.
• BLAKE2 и BLAKE3: высокопроизводительные функции, используемые в криптовалютах (например, Decred, Siacoin) и протоколах.
• SM3: китайский стандарт, используемый в национальных криптосистемах.

Парадокс дней рождения и оценка вероятности

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

P ≈ 1 - exp(-k² / (2 * 2^n))

Для 50% вероятности коллизии требуется примерно 2^(n/2) сообщений. Например, для SHA-256 (n=256) требуется около 2^128 сообщений, что вычислительно невозможно. Для MD5 (n=128) — около 2^64 сообщений, что было достигнуто на практике.

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

• В 2017 году исследователи из Google и CWI создали два разных PDF-файла с одинаковым SHA-1-хэшем. Для этого потребовалось 9,2 миллиарда вычислений SHA-1.
• В 2008 году атака на MD5 позволила создать поддельный SSL-сертификат для сайта «*» (все домены), который был принят браузерами.
• В 2019 году была опубликована атака SHAttered на SHA-1, которая позволила создать коллизию за 2^63 операций, что значительно быстрее теоретической оценки.
• Существует понятие «коллизионная атака на сжатие», когда злоумышленник находит коллизию не для всей функции, а для её внутреннего состояния (сжатия). Это может быть использовано для атаки на цепочку блоков.

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

• Некоторые исследователи критикуют подход к оценке стойкости хэш-функций, основанный только на отсутствии известных атак. Например, SHA-1 считался стойким до 2017 года, но затем была найдена практическая коллизия.
• Для некоторых функций (например, MD5) коллизии могут быть найдены за секунды на обычном компьютере, что делает их полностью непригодными для криптографии.
• В ряде случаев (например, в системах контроля версий Git) коллизии хэш-функций могут привести к потере данных или нарушению целостности репозитория, хотя на практике это крайне маловероятно.

Источники

1. Wang, X., Yu, H. (2005). "How to Break MD5 and Other Hash Functions". Advances in Cryptology – EUROCRYPT 2005.
2. Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. (2017). "The First Collision for Full SHA-1". CRYPTO 2017.
3. NIST. "Secure Hash Standard (SHS)". FIPS PUB 180-4.
4. Menezes, A., van Oorschot, P., Vanstone, S. (1996). "Handbook of Applied Cryptography". CRC Press.
5. Bellare, M., Rogaway, P. (1993). "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols". ACM CCS 1993.