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

Ата́ка «дней рожде́ния» — используемое в криптоанализе название для метода взлома шифров или поиска коллизий хеш-функций на основе парадокса дней рождения. Суть метода состоит в значительном уменьшении количества передаваемых хеш-функции аргументов, необходимого для обнаружения коллизии, поскольку если хеш-функция генерирует n‑битное значение, то число случайных аргументов хеш-функции, для которого с большой вероятностью будет обнаружена хотя бы одна коллизия хеш-функции (то есть найдётся хотя бы одна пара равных хеш-кодов, полученных на разных аргументах), равно не 2ⁿ, а только около 2^n/2.

Понимание проблемы

Основная статья: Парадокс дней рождения

Рассмотрим пример: будет ли у двух человек в группе, состоящей из 23 человек, одинаковый день рождения? Один год, исключая високосные годы, составляет 365 дней, поэтому существует 365 разных дней рождения, гораздо большее число, чем 23.

Если бы мы выбрали конкретный день, то вероятность того, что по крайней мере один человек родился в тот конкретный день, была бы $1-(364/365)^{23}$, примерно 6,1 %. Однако вероятность того, что по крайней мере один человек имеет тот же день рождения, что и любой другой человек, составляет около 50 %, согласно формуле $1-365!/((365-n)!\cdot 365^{n})$. При n = 70 вероятность такого совпадения составляет 99,9 %.

Математика

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

Пусть $h$ — хеш-функция. Атака «дней рождения» успешна, если найдётся пара $x_{1}\neq x_{2}$ такая, что $h(x_{1})=h(x_{2}).$

Таким образом, если функция $h(x)$ даёт любой из $N$ разных выходов с равной вероятностью и $N$ достаточно велико, то математическое ожидание количества пар различных аргументов $x_{1}\neq x_{2},$ для которых $h(x_{1})=h(x_{2}),$ составляет $1{,}25{\sqrt {N}}$. Оценку числа операций хеширования для поиска коллизии идеальной криптографической хеш-функции с размером выхода $n$ бит часто записывают как $2^{n/2},$ а не $2^{n}$.

Пусть $P(n)$ — вероятность того, что в группе из $n$ человек ($n<N=365$) хотя бы двое имеют одинаковый день рождения.

$P(n)$ = $1-1\cdot \left(1-{\frac {1}{N}}\right)\cdot \left(1-{\frac {2}{N}}\right)\cdot ...\cdot \left(1-{\frac {n-1}{N}}\right)=1-\prod _{i=0}^{n-1}\ \left(1-{\frac {i}{N}}\right).$

Из первых двух членов разложения в ряд Тейлора функции $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3}}{3!}}+\cdots ,$ при $|x|\ll 1$ выполняется $e^{x}\approx 1+x.$ Заменив множители $\left(1-{\frac {i}{N}}\right)$ на ${e}^{-i/N},$ получаем

$P(n)\approx 1-\prod _{i=0}^{n-1}\ {e}^{-i/N}=1-\exp \sum _{i=0}^{n-1}(-i/N)=1-{e}^{-n(n-1)/2N}\approx 1-{e}^{-{\frac {n^{2}}{2N}}}.$

Найдём число $n$ такое, чтобы $P(n)\geq {\frac {1}{2}}.$

${\frac {1}{2}}\geq {e}^{-{\frac {n^{2}}{2N}}}.$

Следовательно,

$n\geq {\sqrt {2\ln 2\cdot N}}\approx 1,177{\sqrt {N}}\approx 23$.

Например, если используется 64-битный хеш, существует примерно 1,8 × 10¹⁹ различных выходов. Если все они одинаково вероятны (лучший случай), то для создания коллизии с использованием грубой силы потребовалось бы «всего» около 5 миллиардов попыток (5,38 × 10⁹). Другие примеры:

Биты	Возможные выходы (N)	Желаемая вероятность случайной коллизии (P)
		10−18	10−15	10−12	10−9	10−6	0,1 %	1 %	25 %	50 %	75 %
16	216 (~6,5 x 103)	<2	<2	<2	<2	<2	11	36	190	300	430
32	232 (~4,3 × 109)	<2	<2	<2	3	93	2900	9300	50 000	77 000	110 000
64	264 (~1.8 × 1019)	6	190	6100	190 000	6 100 000	1,9 × 108	6,1 × 108	3,3 × 109	5,1 × 109	7,2 × 109
128	2128 (~3.4 × 1038)	2,6 × 1010	8,2 × 1011	2,6 × 1013	8,2 × 1014	2,6 × 1016	8,3 × 1017	2,6 × 1018	1,4 × 1019	2,2 × 1019	3,1 × 1019
256	2256 (~1,2 × 1077)	4,8 × 1029	1,5 × 1031	4,8 × 1032	1,5 × 1034	4,8 × 1035	1,5 × 1037	4,8 × 1037	2,6 × 1038	4,0 × 1038	5,7 × 1038
384	2384 (~3,9 × 10115)	8,9 × 1048	2,8 × 1050	8,9 × 1051	2,8 × 1053	8,9 × 1054	2,8 × 1056	8,9 × 1056	4,8 × 1057	7,4 × 1057	1,0 × 1058
512	2512 (~1,3 × 10154)	1,6 × 1068	5,2 × 1069	1,6 × 1071	5,2 × 1072	1,6 × 1074	5,2 × 1075	1,6 × 1076	8,8 × 1076	1,4 × 1077	1,9 × 1077

В таблице показано количество хешей $n(P),$ необходимых для достижения заданной вероятности успеха, в предположении, что все хеши одинаково вероятны. Для сравнения, 10⁻¹⁸ до 10⁻¹⁵ — это некорректируемый коэффициент ошибок на бит типичного жесткого диска. Теоретически, MD5 хеши или UUID, составляющий 128 бит, должны оставаться в пределах этого диапазона до примерно 820 миллиардов документов, даже если его возможные результаты намного больше.

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

Чувствительность цифровой подписи

К этой атаке, например, может быть уязвима электронная цифровая подпись. Допустим, что 2 человека — A и Б — хотят подписать контракт, но А хочет подсунуть Б поддельный вариант контракта. Тогда А составляет подлинный контракт и поддельный контракт. Далее посредством внесения допустимых изменений, не меняющих смысла текста (расстановкой запятых, переносов, отступов), А добивается, чтобы оба контракта имели одинаковый хеш. После этого А посылает Б подлинный контракт, Б его подписывает, а его подпись также показывает, что он подписал и поддельный контракт, так как оба контракта имеют одинаковый хеш. Для избежания уязвимости такого рода достаточно увеличить длину хеша настолько, чтобы стало вычислительно сложно найти 2 контракта с одинаковыми хешами. В частности, требуется в два раза большая длина хеша, чтобы обеспечить вычислительную сложность, сравнимую со сложностью полного перебора. Другими словами, если с помощью полного перебора злоумышленник может вычислить $2^{n}$ хеш-значений, то он начнёт находить хеш-коллизии для всех хешей длиной менее $2n$ бит. (см. en:Birthday attack)

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

Атака методом «дней рождения» протокола BIND

DNS — компьютерная распределённая система для получения информации о доменах. Чаще всего используется для получения IP-адреса по имени хоста (компьютера или устройства).

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

В 2002 году Вагнер Сакраменто опубликовал рекомендацию, показывающую одну проблему с внедрением BIND протокола DNS. Он обнаружил, что BIND отправляет несколько одновременных рекурсивных запросов для одного и того же IP-адреса.

Атакующий отправляет запрос на DNS-сервер жертвы. Он выбирает доменное имя, которое DNS-сервер A не может найти в своем кеше и вынужден пересылать на следующий DNS-сервер B. Каждый обмен разрешениями между A и B аутентифицируется через случайный идентификатор TID. Прежде чем DNS-сервер A сможет получить пакеты ответов с DNS-сервера B, атакующий отправляет N поддельных ответных пакетов на DNS-сервер A. Если один из этих поддельных пакетов имеет тот же TID, что и идентификатор TID DNS-сервера A, то поддельные пакеты будут приняты сервером A за действительные пакеты. Реальный ответ от DNS-сервера B не будет обрабатываться DNS-сервером A. Таким образом, атакующий может «отравить» кеш DNS-сервера A, чтобы отобразить взломанный домен на IP-адрес, указанный атакующим.

При обычной атаке злоумышленник отправляет N поддельных ответов для одного запроса, вероятность успеха равна ${\frac {N}{65535}}$ (TID — 16-битное число).

Атака методом «дней рождения» позволяет выполнить взлом протокола BIND легче. Атакующий отправляет большое количество N запросов на DNS-сервер жертвы, всё одно и то же имя домена. Мы отправляем N поддельных ответов для N запросов. Отсюда вероятность того, что атака будет успешной, равна

$P(n)=1-{e}^{-{\frac {n^{2}}{2N}}}.$

Простое приближение

Хорошей эмпирической закономерностью, которую можно использовать для быстрой оценки в уме, является соотношение

$P(n)\approx {n^{2} \over 2N},$

которое также может быть записано как

$N\approx {n^{2} \over 2P(n)}$

или

$n\approx {\sqrt {2N\times P(n)}}.$

Это приближение хорошо работает для вероятностей, меньших или равных 0,5.

Указанная схема аппроксимации особенно проста в использовании при работе с показателями. Например, пусть необходимо оценить, сколько документов можно обработать 32-битной хеш-функцией ($N=2^{32}$), чтобы вероятность коллизии составляла не более одной миллионной ($P=10^{-6}\approx 2^{-20}$). Оценка наибольшего возможного числа документов для таких условий составляет

$n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6{,}5}\approx 90{,}5,$

что близко к правильному ответу 93.

Примеры

Предположим, что для атаки на 64-битный блочный шифр злоумышленнику нужно получить две пары открытого/шифрованного текста, которые отличаются только в наименее значимом бите. Интерпретация этой задачи в терминах парадокса дней рождения приводит к выводу, что пространство из всего лишь $2^{32}$ известных открытых текстов с высокой вероятностью будет содержать необходимую пару.

В качестве другого примера рассмотрим цикл 64-битового Фейстелева шифра. Предположим, что в шифре использована случайная функция F (32 в 32 бита). Нападающий может захотеть узнать, как много ему необходимо получить открытых текстов для получения коллизии функции F. Согласно парадоксу дней рождения, для этого придётся перебрать около $2^{16}$ открытых текстов.

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

Литература

• Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp401-418
• Don Coppersmith : Another Birthday Attack, Proceeding CRYPTO '85 Advances in Cryptology p. 14-17