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

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

История

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

В 1990-х годах атака дня рождения стала широко известна в связи с развитием криптоанализа. В 2004 году китайские исследователи Ван Сяоюнь, Фэн Дэнго и Ю Хунбо продемонстрировали успешную атаку на хеш-функции MD5 и SHA-0, используя методы, основанные на парадоксе дней рождения. Это привело к постепенному отказу от MD5 и SHA-0 в пользу более стойких алгоритмов, таких как SHA-256 и SHA-3.

Теоретическая основа

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

Парадокс дней рождения утверждает, что вероятность того, что в группе из \(k\) случайно выбранных людей хотя бы у двух совпадут дни рождения, превышает 0,5 при \(k \geq 23\). В общем виде для множества из \(N\) равновероятных исходов (например, \(N = 365\) для дней рождения) вероятность коллизии \(P(k)\) вычисляется по формуле:

\[ P(k) = 1 - \frac{N!}{(N-k)! \cdot N^k} \approx 1 - e^{-k(k-1)/(2N)}. \]

При \(k \approx 1,177 \sqrt{N}\) вероятность достигает 0,5. В криптографии \(N = 2^n\), где \(n\) — длина хеша в битах, поэтому ожидаемое число попыток для нахождения коллизии составляет около \(2^{n/2}\).

Применение к хеш-функциям

Хеш-функция \(H\) отображает произвольный входной набор данных в строку фиксированной длины \(n\) бит. Коллизия возникает, если \(H(x) = H(y)\) при \(x \neq y\). Атака дня рождения позволяет найти такую пару, перебирая случайные входные значения и сравнивая их хеши. Вероятность успеха после \(q\) попыток приблизительно равна \(q^2 / (2 \cdot 2^n)\).

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

Классическая атака (поиск коллизий)

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

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

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

Атака на шифры с гаммированием

В некоторых режимах работы блочных шифров (например, CTR, OFB) атака дня рождения может привести к коллизии гаммы, что позволяет расшифровать часть данных. Вероятность коллизии гаммы при использовании одного ключа для шифрования \(q\) блоков составляет \(q^2 / 2^{n+1}\), где \(n\) — размер блока.

Устройство и реализация

Алгоритм

1. Злоумышленник выбирает \(q\) случайных входных данных \(x_1, x_2, \dots, x_q\).
2. Вычисляет хеши \(h_i = H(x_i)\) для всех \(i\).
3. Сортирует хеши или помещает их в хеш-таблицу для быстрого поиска совпадений.
4. Если найдена пара \((i, j)\) с \(h_i = h_j\) и \(x_i \neq x_j\), коллизия обнаружена.

Сложность алгоритма составляет \(O(q)\) по памяти и \(O(q \log q)\) по времени при использовании сортировки.

Оптимизации

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

Применение в криптоанализе

Взлом хеш-функций

Атака дня рождения является стандартным инструментом для оценки стойкости хеш-функций. Если длина хеша \(n\) мала (например, 64 бита), то \(2^{32}\) попыток (около 4 миллиардов) достаточно для нахождения коллизии, что выполнимо на современном оборудовании. Именно поэтому в современных системах используются хеши длиной не менее 256 бит (SHA-256, SHA-3-256).

Взлом протоколов аутентификации

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

Примеры успешных атак

• MD5: длина хеша 128 бит, ожидаемая сложность атаки — \(2^{64}\). В 2004 году была найдена коллизия за \(2^{39}\) операций, что значительно ниже теоретического предела.
• SHA-0: длина 160 бит, ожидаемая сложность — \(2^{80}\). В 1998 году была найдена коллизия за \(2^{61}\) операций.
• SHA-1: длина 160 бит, ожидаемая сложность — \(2^{80}\). В 2017 году Google и CWI Amsterdam продемонстрировали коллизию за \(2^{63}\) операций (атака SHAttered).

Защита от атаки дня рождения

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

Основной метод защиты — использование хеш-функций с достаточной длиной выхода. Современные стандарты (SHA-256, SHA-3-256, BLAKE2) обеспечивают \(n \geq 256\), что делает атаку дня рождения практически невыполнимой (требуется \(2^{128}\) операций).

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

Добавление случайной соли (salt) перед хешированием усложняет атаку, так как злоумышленник не может заранее подготовить набор хешей для всех возможных входов. Однако соль не защищает от коллизий внутри одного набора данных.

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

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

Использование криптографических подписей

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

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

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

Кроме того, атака дня рождения неэффективна против хеш-функций с доказанной стойкостью к коллизиям, таких как SHA-3, где конструкция (Sponge) затрудняет нахождение коллизий даже при \(2^{n/2}\) попытках.

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

• Парадокс дней рождения часто используется в учебных целях для демонстрации неинтуитивных свойств вероятности.
• В 2012 году атака дня рождения была применена к протоколу TLS для взлома случайной генерации ключей (атака BEAST), что привело к обновлению стандартов.
• В криптовалютах (например, Bitcoin) атака дня рождения теоретически может быть использована для создания коллизии хешей транзакций, но из-за использования SHA-256 это практически невозможно.

Источники

• Menezes, A., van Oorschot, P., Vanstone, S. — Handbook of Applied Cryptography (1996).
• Wang, X., Feng, D., Yu, H. — Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (2004).
• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. — The First Collision for Full SHA-1 (2017).
• Stinson, D. — Cryptography: Theory and Practice (2006).