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

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

Содержание

• 1 Понимание проблемы
• 2 Математика
  • 2.1 Простое приближение
• 3 Восприимчивость к цифровой подписи
• 4 См. Также
• 5 Примечания
• 6 Ссылки
• 7 Внешние ссылки

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

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

Математика

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

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

$p\; (n;\; H)\; \approx \; 1\; -\; e\; -\; n\; (n\; -\; 1)\; /\; (2\; H)\; \approx \; 1\; -\; e\; -\; n\; 2\; /\; (2\; H)\; \{\backslash \; displaystyle\; p\; (n;\; H)\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; n\; (n-1)\; /\; (2H)\}\; \backslash \; приблизительно\; 1-e\; ^\; \{-\; n\; ^\; \{2\}\; /\; (2H)\}\}$

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

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

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

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

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

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

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

Биты	Возможные выходы (H)	Желаемая вероятность случайного столкновения. (2 sf) (p)
		10	10	10	10	10	0,1%	1%	25%	50%	75%
16	2 (~ 6,5 x 10)	<2	<2	<2	<2	<2	11	36	190	300	430
32	2 (~ 4,3 × 10)	<2	<2	<2	3	93	2900	9300	50,000	77,000	110,000
64	2 (~ 1,8 × 10)	6	190	6100	190,000	6100000	1,9 × 10	6,1 × 10	3,3 × 10	5,1 × 10	7,2 × 10
128	2 (~ 3,4 × 10)	2,6 × 10	8,2 × 10	2,6 × 10	8,2 × 10	2,6 × 10	8,3 × 10	2,6 × 10	1,4 × 10	2,2 × 10	3,1 × 10
256	2 (~ 1,2 × 10)	4,8 × 10	1,5 × 10	4,8 × 10	1,5 × 10	4,8 × 10	1,5 × 10	4,8 × 10	2,6 × 10	4,0 × 10	5,7 × 10
384	2 (~ 3,9 × 10)	8,9 × 10	2,8 × 10	8,9 × 10	2,8 × 10	8,9 × 10	2,8 × 10	8,9 × 10	4,8 × 10	7,4 × 10	1,0 × 10
512	2 (~ 1,3 × 10)	1,6 × 10	5,2 × 10	1,6 × 10	5,2 × 10	1,6 × 10	5,2 × 10	1,6 × 10	8,8 × 10	1,4 × 10	1,9 × 10

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

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

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

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

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

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

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

или

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

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

Примечания

Ссылки

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

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

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