Атака на день рождения - Birthday attack

Нападение дня рождения является типом криптографической атаки , которая использует математику за проблемами рождения в теории вероятностей . Эта атака может использоваться для злоупотребления связью между двумя или более сторонами. Атака зависит от более высокой вероятности столкновений, обнаруженных между случайными попытками атаки и фиксированной степенью перестановок ( ячеек ). С нападением на день рождения, можно найти коллизию хэш - функцию в системе , с будучи классическим сопротивлением прообраза безопасности. Существует общий (хотя и оспариваемый) результат, что квантовые компьютеры могут выполнять атаки по случаю дня рождения, тем самым нарушая сопротивление столкновениям в . ${\ textstyle {\ sqrt {2 ^ {n}}} = 2 ^ {n / 2}}$${\ textstyle 2 ^ {п}}$${\ textstyle {\ sqrt [{3}] {2 ^ {n}}} = 2 ^ {n / 3}}$

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

Сравнение задачи дня рождения (1) и атаки дня рождения (2):

В (1) столкновения обнаруживаются в пределах одного набора, в данном случае 3 из 276 пар 24 лунных астронавтов.

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

В качестве примера рассмотрим сценарий, в котором учитель с классом из 30 учеников (n = 30) спрашивает у всех день рождения (для простоты игнорируйте високосные годы ), чтобы определить, есть ли у двух учеников одинаковый день рождения (что соответствует хэш-коллизии. как описано далее). Интуитивно этот шанс может показаться небольшим. Как это ни парадоксально, вероятность того, что хотя бы у одного ученика в любой день день рождения такой же, как у любого другого ученика, составляет около 70% (для n = 30), согласно формуле . ${\ displaystyle 1 - {\ frac {365!} {(365-n)! \ cdot 365 ^ {n}}}}$

Если учитель выбрал определенный день (скажем, 16 сентября), то вероятность того, что хотя бы один ученик родился в этот конкретный день, составляет около 7,9%. ${\ displaystyle 1- (364/365) ^ {30}}$

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

Математика

Для заданной функции цель атаки - найти два разных входа, такие что . Такая пара называется коллизией. Метод, используемый для обнаружения коллизии, заключается в простом вычислении функции для различных входных значений, которые могут быть выбраны случайным образом или псевдослучайно до тех пор, пока один и тот же результат не будет найден более одного раза. Из-за проблемы с днем ​​рождения этот способ может быть достаточно эффективным. В частности, если функция дает какая - либо из различных выходов с равной вероятностью , и достаточно велико, то мы ожидаем , чтобы получить пару различных аргументов и с после оценки функции около различных аргументов в среднем. ${\ displaystyle f}$${\ displaystyle x_ {1}, x_ {2}}$${\ Displaystyle f (x_ {1}) = f (x_ {2})}$${\ displaystyle x_ {1}, x_ {2}}$${\ displaystyle f}$ ${\ displaystyle f (x)}$${\ displaystyle H}$${\ displaystyle H}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ Displaystyle f (x_ {1}) = f (x_ {2})}$${\ displaystyle 1.25 {\ sqrt {H}}}$

Рассмотрим следующий эксперимент. Из набора значений H мы выбираем n значений равномерно и случайным образом, тем самым позволяя повторения. Пусть p ( n ;  H ) - вероятность того, что во время этого эксперимента хотя бы одно значение будет выбрано более одного раза. Эта вероятность может быть аппроксимирована как

${\ Displaystyle п (п; ЧАС) \ приблизительно 1-е ^ {- п (п-1) / (2H)} \ приблизительно 1-е ^ {- п ^ {2} / (2H)}}$

Пусть n ( p ;  H ) будет наименьшим количеством значений, которые мы должны выбрать, так что вероятность обнаружения столкновения не меньше  p . Обращая это выражение выше, мы находим следующее приближение

${\ displaystyle n (p; H) \ приблизительно {\ sqrt {2H \ ln {\ frac {1} {1-p}}}}}$

и присвоив вероятность столкновения 0,5, мы приходим к

${\ displaystyle n (0,5; H) \ приблизительно 1,1774 {\ sqrt {H}}}$

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

${\ Displaystyle Q (H) \ приблизительно {\ sqrt {{\ frac {\ pi} {2}} H}}}$

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

Биты	Возможные выходы (H)	Желаемая вероятность случайного столкновения (2 sf) (p)
		10 −18	10 −15	10 −12	10 −9	10 −6	0,1%	1%	25%	50%	75%
16	2 16 (~ 6,5 х 10 4 )	<2	<2	<2	<2	<2	11	36	190	300	430
32	2 32 (~ 4,3 × 10 9 )	<2	<2	<2	3	93	2900	9300	50 000	77 000	110 000
64	2 64 (~ 1,8 × 10 19 )	6	190	6100	190 000	6 100 000	1,9 × 10 8	6,1 × 10 8	3,3 × 10 9	5,1 × 10 9	7,2 × 10 9
128	2 128 (~ 3,4 × 10 38 )	2,6 × 10 10	8,2 × 10 11	2,6 × 10 13	8,2 × 10 14	2,6 × 10 16	8,3 × 10 17	2,6 × 10 18	1,4 × 10 19	2,2 × 10 19	3,1 × 10 19
256	2 256 (~ 1,2 × 10 77 )	4,8 × 10 29	1,5 × 10 31	4,8 × 10 32	1,5 × 10 34	4,8 × 10 35	1,5 × 10 37	4,8 × 10 37	2,6 × 10 38	4,0 × 10 38	5,7 × 10 38
384	2 384 (~ 3,9 × 10 115 )	8,9 × 10 48	2,8 × 10 50	8,9 × 10 51	2,8 × 10 53	8,9 × 10 54	2,8 × 10 56	8,9 × 10 56	4,8 × 10 57	7,4 × 10 57	1,0 × 10 58
512	2 512 (~ 1,3 × 10 154 )	1,6 × 10 68	5,2 × 10 69	1,6 × 10 71	5,2 × 10 72	1,6 × 10 74	5,2 × 10 75	1,6 × 10 76	8,8 × 10 76	1,4 × 10 77	1,9 × 10 77

В таблице показано количество хешей n ( p ), необходимое для достижения заданной вероятности успеха, при условии, что все хеши равновероятны. Для сравнения, от 10 ^-18 до 10 ^-15 - это коэффициент неисправимых битовых ошибок типичного жесткого диска. Теоретически хэши MD5 или UUID , имеющие 128 бит, должны оставаться в этом диапазоне примерно до 820 миллиардов документов, даже если их возможных выходов намного больше.

Легко видеть, что если выходы функции распределены неравномерно, то коллизия может быть обнаружена еще быстрее. Понятие «баланса» хэш-функции количественно определяет устойчивость функции к атакам по случаю дня рождения (используя неравномерное распределение ключей). Однако определение баланса хэш-функции обычно требует вычисления всех возможных входных данных и, таким образом, неосуществимо для популярных хэш-функции, такие как семейства MD и SHA. Подвыражение в уравнении для small при прямом переводе на общепринятые языки программирования не вычисляется точно из-за потери значимости . Когда он доступен (например, в C99 ), вместо него следует использовать эквивалентное выражение . Если этого не сделать, первый столбец приведенной выше таблицы считается равным нулю, а несколько элементов во втором столбце не имеют ни одной правильной значащей цифры. ${\ displaystyle \ ln {\ frac {1} {1-p}}}$${\ Displaystyle п (п; Н)}$${\ displaystyle p}$log(1/(1-p))log1p-log1p(-p)

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

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

${\ displaystyle p (n) \ приблизительно {n ^ {2} \ более 2H}}$

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

${\ displaystyle H \ приблизительно {n ^ {2} \ более 2p (n)}}$.

или же

${\ displaystyle n \ приблизительно {\ sqrt {2H \ times p (n)}}}$.

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

Эта схема аппроксимации особенно удобна при работе с показателями степени. Например, предположим, что вы создаете 32-битные хэши ( ) и хотите, чтобы вероятность коллизии составляла не более одного из миллиона ( ), сколько документов у нас может быть не больше? ${\ displaystyle H = 2 ^ {32}}$${\ displaystyle p \ приблизительно 2 ^ {- 20}}$

${\ displaystyle n \ приблизительно {\ sqrt {2 \ times 2 ^ {32} \ times 2 ^ {- 20}}} = {\ sqrt {2 ^ {1 + 32-20}}} = {\ sqrt {2 ^ {13}}} = 2 ^ {6.5} \ приблизительно 90,5}$

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

Восприимчивость к цифровой подписи

Цифровые подписи могут быть уязвимы для атак по случаю дня рождения. Сообщение обычно подписывается сначала вычислением , где используется криптографическая хеш-функция , а затем с использованием некоторого секретного ключа для подписи . Предположим, Мэллори хочет обманом заставить Боба подписать мошеннический контракт. Мэллори готовит честный и мошеннический контракт . Затем она находит ряд позиций, которые можно изменить без изменения значения, например, вставка запятых, пустых строк, одного или двух пробелов после предложения, замены синонимов и т. Д. Комбинируя эти изменения, она может создать огромное количество вариаций. по которым заключаются все честные контракты. ${\ displaystyle m}$${\ displaystyle f (m)}$${\ displaystyle f}$${\ displaystyle f (m)}$${\ displaystyle m}$${\ displaystyle m '}$${\ displaystyle m}$${\ displaystyle m}$

Точно так же Мэллори создает огромное количество вариантов мошеннического контракта . Затем она применяет хэш - функцию для всех этих изменений , пока она не найдет версию договора справедливой и версию мошеннической договора , которые имеют одинаковое значение хеш - функции, . Она представляет Бобу на подпись справедливую версию. После того, как Боб подписал, Мэллори берет подпись и прикрепляет ее к мошенническому контракту. Эта подпись затем «доказывает», что Боб подписал мошеннический контракт. ${\ displaystyle m '}$${\ Displaystyle е (м) = е (м ')}$

Вероятности немного отличаются от исходной задачи о дне рождения, поскольку Мэллори ничего не получает, находя два честных или два мошеннических контракта с одним и тем же хешем. Стратегия Мэллори состоит в том, чтобы создать пары из одного честного и одного мошеннического контракта. Применяются уравнения задачи дня рождения, где - количество пар. Количество фактически генерируемых Мэллори хэшей равно . ${\ displaystyle n}$${\ displaystyle 2n}$

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

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

Алгоритм Ро Полларда для логарифмов является примером алгоритма, использующего атаку по случаю дня рождения для вычисления дискретных логарифмов .

Смотрите также

• Атака столкновения
• Атака на встречу посередине

Заметки

Рекомендации

• Михир Белларе , Тадаёши Коно: Баланс хеш-функции и его влияние на атаки по случаю дня рождения. EUROCRYPT 2004: стр. 401–418
• Прикладная криптография, 2-е изд. по Брюс Шнайер

Внешние ссылки

• «Что такое цифровая подпись и что такое аутентификация?» из часто задаваемых вопросов о криптографии RSA Security .
• "Атака на день рождения" X5 Networks Crypto: вопросы и ответы