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

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

Принцип возникновения

Хеш-функция \( H \) принимает на вход сообщение \( M \) произвольной длины и возвращает хеш \( h \) фиксированной длины \( n \). Количество возможных хешей равно \( 2^n \). Если количество возможных входных сообщений превышает \( 2^n \), то по принципу Дирихле (принципу ящиков) хотя бы два разных сообщения \( M_1 \) и \( M_2 \) будут иметь одинаковый хеш: \( H(M_1) = H(M_2) \). Это и есть коллизия.

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

Классификация коллизий

В криптографии различают несколько типов атак, связанных с коллизиями, в зависимости от того, какой контроль злоумышленник имеет над входными данными:

Слабая коллизия (второй прообраз)

Злоумышленнику дано исходное сообщение \( M_1 \) и его хеш \( h \). Задача — найти другое сообщение \( M_2 \neq M_1 \), такое что \( H(M_2) = h \). Стойкость к этому типу коллизий называется стойкостью ко второму прообразу. Для идеальной функции сложность такой атаки составляет \( 2^n \).

Сильная коллизия (первый прообраз)

Злоумышленнику дан только хеш \( h \). Задача — найти любое сообщение \( M \), для которого \( H(M) = h \). Стойкость к этому типу называется стойкостью к прообразу. Сложность — \( 2^n \).

Свободная коллизия (коллизия в собственном смысле)

Злоумышленник может выбирать оба сообщения \( M_1 \) и \( M_2 \) произвольно. Задача — найти любую пару, для которой \( H(M_1) = H(M_2) \). Это самый слабый тип атаки, и для его успеха требуется всего \( 2^{n/2} \) попыток (граница дней рождения). Именно этот тип обычно имеют в виду, когда говорят о «коллизии хеш-функции».

Последствия коллизий

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

• Нарушение целостности данных: Если злоумышленник может создать два разных документа с одинаковым хешем, он может подменить один документ другим, не меняя цифровую подпись, которая была вычислена для первого документа.
• Подделка цифровых подписей: В схемах цифровой подписи (например, RSA, DSA) подписывается хеш сообщения, а не само сообщение. Если найдена коллизия, злоумышленник может заставить владельца подписи подписать безобидный документ \( M_1 \), а затем выдать подпись за подпись вредоносного документа \( M_2 \).
• Компрометация сертификатов: В инфраструктуре открытых ключей (PKI) сертификаты удостоверяющих центров (УЦ) подписываются хешем. Коллизия может позволить создать поддельный сертификат, который будет принят системой как действительный.
• Атаки на системы хранения паролей: Хотя коллизии напрямую не помогают восстановить пароль, они могут быть использованы для обхода проверок, если система сравнивает только хеши.

Известные примеры коллизий

MD5

Алгоритм MD5 (Message Digest 5), созданный Роном Ривестом в 1991 году, долгое время был одним из самых распространённых. Однако к 2004 году китайские исследователи (Сяоюнь Ван и др.) продемонстрировали практический метод нахождения коллизий для MD5 за секунды на обычном компьютере. В 2008 году была создана пара сертификатов X.509 с одинаковой подписью MD5, что позволило сгенерировать поддельный корневой сертификат УЦ. После этого MD5 был признан полностью небезопасным и выведен из употребления в криптографических протоколах.

SHA-1

Алгоритм SHA-1 (Secure Hash Algorithm 1), разработанный АНБ США в 1995 году, считался стойким до середины 2010-х годов. В 2017 году компания Google совместно с CWI Amsterdam объявила о первой практической коллизии для SHA-1 (атака SHAttered). Для её нахождения потребовалось 6 500 лет процессорного времени (в эквиваленте одного ядра) и 110 лет графического процессора. Два разных PDF-файла имели одинаковый 160-битный хеш. После этого NIST (Национальный институт стандартов и технологий США) официально рекомендовал отказаться от SHA-1 к 2030 году, а все основные браузеры и удостоверяющие центры перестали принимать сертификаты, подписанные с использованием SHA-1.

SHA-2 и SHA-3

Семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) и алгоритм SHA-3 (Keccak) считаются на текущий момент (2025 год) стойкими к коллизиям. Для SHA-256, например, сложность нахождения коллизии методом дней рождения составляет \( 2^{128} \) операций, что на много порядков превышает возможности современных вычислительных систем. Однако теоретически коллизии для них существуют, и с развитием квантовых вычислений (алгоритм Гровера снижает сложность до \( 2^{n/3} \)) их поиск может стать более доступным.

Методы защиты от коллизий

Для предотвращения использования коллизий в практических атаках применяются следующие подходы:

• Использование криптостойких хеш-функций: Выбор функций с длиной выхода не менее 256 бит (например, SHA-256, SHA-3-256). Функции с выходом 128 бит (MD5, SHA-1) считаются устаревшими.
• Соль (salt) в хешировании паролей: Добавление случайной строки (соли) к каждому паролю перед хешированием делает невозможным использование предвычисленных таблиц (радужных таблиц) и усложняет атаку по нахождению коллизий, так как злоумышленник не знает соль.
• Итеративное хеширование (Key stretching): Многократное применение хеш-функции (например, в алгоритмах bcrypt, PBKDF2, Argon2) значительно увеличивает время вычисления, делая атаку методом полного перебора (brute force) или поиска коллизий экономически невыгодной.
• Использование нескольких хеш-функций: В некоторых протоколах (например, в цифровых подписях ГОСТ Р 34.10-2012) применяется хеш-функция с большой длиной дайджеста (512 бит), что многократно увеличивает границу дней рождения.

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

• Парадокс дней рождения, лежащий в основе оценки вероятности коллизий, был впервые описан Ричардом фон Мизесом в 1939 году. Он показывает, что в группе из 23 человек вероятность того, что у двух человек совпадает день рождения, превышает 50%. Для хеш-функции с 365-битным выходом (гипотетически) это означало бы, что коллизию можно найти примерно за \( \sqrt{365} \approx 19 \) попыток.
• Первая публично задокументированная коллизия для MD5 была найдена в 1993 году (псевдоколлизия), но практическая атака была реализована только в 2004 году.
• Атака SHAttered на SHA-1 в 2017 году потребовала более 9 квинтиллионов (9×10¹⁸) вычислений хеша. Для сравнения: это примерно в 100 000 раз больше, чем количество звёзд в галактике Млечный Путь.

Источники

• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. Handbook of Applied Cryptography. CRC Press, 1996.
• Wang, X., Yu, H. How to Break MD5 and Other Hash Functions. EUROCRYPT 2005.
• Stevens, M., Bursztein, E., Karpman, P., et al. The First Collision for Full SHA-1. CRYPTO 2017.
• NIST SP 800-107 Rev. 1. Recommendation for Applications Using Approved Hash Algorithms. 2012.
• Фергюсон, Н., Шнайер, Б. Практическая криптография. Вильямс, 2005.