Атака «день рождения

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

Принцип действия

Математическая основа: парадокс дней рождения

Парадокс дней рождения утверждает, что в группе из 23 человек вероятность того, что хотя бы у двух человек совпадает день рождения, превышает 50 %. Для группы из 57 человек эта вероятность превышает 99 %. В контексте криптографии «день рождения» — это конкретное значение хеш-функции, а «люди» — это входные данные. Если хеш-функция выдает значения длиной \( n \) бит, то пространство возможных хешей составляет \( 2^n \). Для нахождения коллизии методом простого перебора потребовалось бы в среднем \( 2^{n-1} \) попыток. Однако парадокс дней рождения показывает, что для нахождения коллизии с вероятностью более 50 % достаточно перебрать всего около \( \sqrt{2^n} = 2^{n/2} \) различных входных данных. Это число называется «границей дня рождения» (birthday bound).

Алгоритм атаки

1. Генерация входных данных. Злоумышленник создаёт два набора данных: один — легитимные сообщения (например, контракты, которые жертва готова подписать), другой — поддельные сообщения (с выгодными для злоумышленника условиями).
2. Вычисление хешей. Для каждого сообщения из обоих наборов вычисляется хеш-значение.
3. Поиск совпадений. Злоумышленник ищет пару сообщений (одно из первого набора, одно из второго), у которых хеши совпадают. Если хеш-функция имеет длину \( n \) бит, то для нахождения такой пары достаточно перебрать около \( 2^{n/2} \) вариантов.
4. Подмена. Злоумышленник предъявляет жертве легитимное сообщение из найденной пары. Жертва вычисляет его хеш и подписывает его (например, цифровой подписью). После этого злоумышленник подменяет подписанный хеш на поддельное сообщение, которое имеет тот же хеш. Таким образом, подпись, сделанная для легитимного сообщения, оказывается действительной для поддельного.

История и развитие

Ранние упоминания

Идея использования парадокса дней рождения в криптографии была впервые сформулирована в 1970-х годах. В 1979 году американский криптограф Густавус Симмонс (Gustavus Simmons) описал атаку на основе парадокса для анализа хеш-функций. В 1980-х годах атака была формализована и получила название «атака дня рождения».

Практические применения

В 1990-е годы, с ростом популярности хеш-функций (например, MD5, SHA-1), атака «день рождения» стала активно изучаться. В 2004 году китайские исследователи Сяоюнь Ван (Xiaoyun Wang) и Хунбо Ю (Hongbo Yu) продемонстрировали практическую атаку на хеш-функцию MD5, найдя коллизию за время, значительно меньшее \( 2^{64} \) операций (граница дня рождения для MD5 составляет \( 2^{64} \)). В 2005 году они же атаковали SHA-1, сократив сложность до \( 2^{69} \) операций (при границе дня рождения \( 2^{80} \)).

Современное состояние

После успешных атак на MD5 и SHA-1, криптографическое сообщество перешло на более стойкие хеш-функции, такие как SHA-2 (семейство SHA-256, SHA-512) и SHA-3 (Keccak). Для этих функций граница дня рождения (\( 2^{128} \) для SHA-256 и \( 2^{256} \) для SHA-512) считается практически недостижимой для современных вычислительных мощностей. Однако атака «день рождения» остаётся актуальной для более коротких хешей (например, 64-битных) и для некоторых протоколов, где длина хеша уменьшена (например, в некоторых реализациях HMAC).

Виды атак «день рождения»

Атака на цифровые подписи

Наиболее известный сценарий. Злоумышленник создаёт два набора сообщений: «честные» (например, контракт на небольшую сумму) и «мошеннические» (контракт на крупную сумму). После нахождения коллизии жертва подписывает «честное» сообщение, а злоумышленник подменяет его на «мошенническое». Эта атака особенно опасна для протоколов, где подписывается только хеш, а не само сообщение.

Атака на хеш-таблицы

В информатике хеш-таблицы используются для быстрого поиска данных. Если злоумышленник может контролировать входные данные, он может подобрать такие ключи, которые будут коллизировать (давать одинаковые хеши), что приведёт к деградации производительности хеш-таблицы до \( O(n) \) (линейный поиск). Это может быть использовано для атак типа «отказ в обслуживании» (DoS) на веб-серверы, базы данных или кэширующие системы.

Атака на протоколы аутентификации

В некоторых протоколах (например, в некоторых реализациях Kerberos или в протоколах, использующих хеши паролей) атака «день рождения» может быть применена для подбора пароля или сессионного ключа. Если длина хеша мала (например, 64 бита), злоумышленник может найти коллизию быстрее, чем при полном переборе.

Условия успешной атаки

Длина хеша

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

• MD5 (128 бит): \( 2^{64} \) операций — уязвим для современных атак.
• SHA-1 (160 бит): \( 2^{80} \) операций — уязвим для атак с использованием специализированного оборудования (например, FPGA).
• SHA-256 (256 бит): \( 2^{128} \) операций — считается безопасным для ближайших десятилетий.
• SHA-512 (512 бит): \( 2^{256} \) операций — практически нереализуемо.

Контроль над входными данными

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

Вычислительные ресурсы

Для атаки на хеш-функции с длиной 128–160 бит требуются значительные вычислительные мощности (кластеры серверов, GPU, FPGA). Для 256-битных хешей атака считается практически невозможной при текущем уровне развития технологий.

Методы защиты

Увеличение длины хеша

Использование хеш-функций с длиной выхода не менее 256 бит (SHA-256, SHA-512, SHA-3). Это поднимает границу дня рождения до \( 2^{128} \) и выше, что делает атаку нереализуемой.

Использование соли (salt)

В системах хранения паролей добавление случайной соли перед хешированием делает атаку «день рождения» неэффективной, так как злоумышленник не может заранее вычислить хеши для всех возможных паролей.

Применение криптографических протоколов с защитой от коллизий

Например, использование схем подписи, которые подписывают не только хеш, но и само сообщение (например, RSA-PSS). Также применяются протоколы, которые включают в подпись случайные данные (nonce), чтобы предотвратить подмену.

Ограничение числа попыток

В системах аутентификации (например, при вводе пароля) ограничение числа попыток входа или введение временных задержек затрудняет атаку.

Примеры из практики

Атака на MD5 (2004–2008)

В 2004 году группа Сяоюнь Ван опубликовала метод нахождения коллизий для MD5 за \( 2^{39} \) операций, что значительно меньше \( 2^{64} \). В 2008 году исследователи смогли создать два различных SSL-сертификата с одинаковым хешем MD5, что позволило бы злоумышленнику выдать поддельный сертификат за действительный. Это привело к постепенному отказу от MD5 в криптографических протоколах.

Атака на SHA-1 (2017)

В 2017 году компания Google совместно с исследователями из CWI Amsterdam объявила о первой практической атаке на SHA-1 (атака SHAttered). Для нахождения коллизии потребовалось \( 2^{63} \) операций и около 6500 лет процессорного времени (в реальном времени — несколько месяцев на кластере GPU). После этого SHA-1 был признан небезопасным и исключён из рекомендаций NIST.

Атака на хеш-таблицы (2003)

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

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

• Парадокс дней рождения, лежащий в основе атаки, был впервые описан в 1939 году математиком Ричардом фон Мизесом (Richard von Mises) в контексте теории вероятностей. В криптографию он был перенесён только в 1970-х годах.
• Для хеш-функции с длиной 128 бит (MD5) граница дня рождения составляет \( 2^{64} \) — это примерно 18,4 квинтиллиона операций. Для сравнения, современный GPU (например, NVIDIA RTX 4090) может выполнять около \( 2^{35} \) операций хеширования в секунду, что делает атаку на MD5 возможной за несколько месяцев.
• Атака «день рождения» является одной из немногих криптографических атак, которая не требует знания секретного ключа и может быть выполнена исключительно на основе открытых данных.

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

• Атака «день рождения» не является универсальной: она эффективна только для хеш-функций, которые не обладают другими уязвимостями (например, уязвимостью к дифференциальному криптоанализу). Для некоторых хеш-функций (например, SHA-3) атака «день рождения» остаётся теоретической, но не практической.
• Атака требует, чтобы злоумышленник имел возможность генерировать произвольные входные данные. В реальных системах (например, в протоколах с фиксированными форматами сообщений) это может быть затруднено.
• Для защиты от атаки «день рождения» достаточно использовать хеш-функции с длиной выхода не менее 256 бит, что является стандартом для современных криптографических систем (например, ГОСТ Р 34.11-2012 «Стрибог» в России).

Источники

• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Wang, X., Yu, H. (2005). «How to Break MD5 and Other Hash Functions». Advances in Cryptology – EUROCRYPT 2005.
• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. (2017). «The First Collision for Full SHA-1». Advances in Cryptology – CRYPTO 2017.
• NIST (2015). Secure Hash Standard (SHS). FIPS PUB 180-4.
• Федеральный закон РФ «О техническом регулировании» (2002) — в части требований к криптографическим средствам.