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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Атака «дней рождения» — используемое в криптоанализе название для метода взлома шифров или поиска коллизий хеш-функций на основе парадокса дней рождения.

Понимание проблемы[править | править код]

Рассмотрим пример: в группе, состоящей из 23, будет ли у двух человек одинаковый день рождения. Один год, исключая високосные годы, составляет 365 дней, поэтому существует 365 разных дней рождения, гораздо большее число, чем 23, заставляет нас чувствовать, что это парадоксально. Если бы мы выбрали конкретный день, то вероятность того, что по крайней мере один человек родился в тот конкретный день, была , примерно 6,1%. Однако вероятность того, что по крайней мере один человек имеет тот же день рождения, что и любой другой человек, составляет около 50% из формулы [1]. При n = 70, вероятность такого совпадения составляет 99,9%.

Математика[править | править код]

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

т.е Пусть - хеш-функция. Атака «дней рождения» успешна если найдется пара такая, что , но . Таким образом, если функция дает любой из разных выходов с равной вероятностью и достаточно велико, то мы ожидаем получить пару различных аргументов , с после оценки функции около различных аргументов в среднем. Оценку числа операций хэширования для поиска коллизии идеальной криптографической хеш-функции с размером выхода бит часто записывают как а не [2].

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

= .

Следуя из ряда Тейлора функции .

Найдем число , чтобы .

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

[1].

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

Биты Возможные выходы (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
В таблице показано количество хэшей , необходимых для достижения заданной вероятности успеха, предполагая, что все хэши одинаково вероятны. Для сравнения, 10−18 до 10−15 - это некорректируемый коэффициент ошибок на бит типичного жесткого диска.[3]. Теоретически, MD5 хэши или UUID, составляющий 128 бит, должны оставаться в пределах этого диапазона до примерно 820 миллиардов документов, даже если его возможные результаты намного больше.

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

Чувствительность цифровой подписи[править | править код]

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

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

BIND атака «дней рождения»[править | править код]

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

Термином Рекурсия в DNS обозначают алгоритм поведения 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, тогда поддельные пакеты будут приниматься как действительные пакеты. Реальный ответ от DNS-сервера B не будет обрабатываться DNS-сервером A. Таким образом, атакующий может отравить кеш DNS-сервера A, чтобы отобразить взломанный домен на IP-адрес, указанный атакующим. При обычной атаке мы отправляем N поддельных ответов для одного запроса, вероятность успеха равна (TID - 16-битное число).

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

Простое приближение[править | править код]

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

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

.

или

.

Это хорошо работает для вероятностей, меньших или равных 0,5. Эта схема аппроксимации особенно проста в использовании при работе с показателями. Например, предположим, что вы строите 32-битные хэши () и хотите, чтобы вероятность коллизии составляла не более одного миллиона (), сколько документов у нас может быть самое большее?

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

Примеры[править | править код]

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

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

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

Примечания[править | править код]

  1. 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to algorithms, third edition, p. 130-133
  2. Буханцов А. Д, Дружкова И. В, О модификации алгоритма MD5, Белгородский государственный национальный исследовательский университет, 2016, p. 176
  3. Gray, Jim & van Ingen, Catharine (25 January 2007), "Empirical Measurements of Disk Failure Rates and Error Rates", arΧiv:cs/0701166 
  4. Joe Stewart, DNS Cache Poisoning, р.4-5.
  5. 1 2 Л.К. Бабенко, Е.А. Ищукова, Анализ симметричных криптосистем, р. 146.

Литература[править | править код]

  • 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