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

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

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

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

Математика

Учитывая функцию ${ 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}}}$ разные аргументы в среднем.

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

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

^[4]

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

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

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

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

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

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

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

Биты	Возможные выходы (H)	Желаемая вероятность случайного столкновения (2 н.ф.) (п)
Биты	Возможные выходы (H)	10⁻¹⁸	10⁻¹⁵	10⁻¹²	10⁻⁹	10⁻⁶	0.1%	1%	25%	50%	75%
16	2¹⁶ (~ 6,5 х 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	6,100,000	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(п) необходим для достижения заданной вероятности успеха при условии, что все хэши равновероятны. Для сравнения, 10⁻¹⁸ к 10⁻¹⁵ - коэффициент неисправимых битовых ошибок типичного жесткого диска.^[7] Теоретически, MD5 хеши или UUID будучи 128 битами, он должен оставаться в этом диапазоне примерно до 820 миллиардов документов, даже если его возможные результаты намного больше.

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

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

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

{ 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}$ .

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

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

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

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

Примечания

^ Дэниел Дж. Бернштейн. «Анализ затрат на хэш-коллизии: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF). Cr.yp.to. Получено 29 октября 2017.
^ Брассар, Жиль; Хёйер, Питер; Тэпп, Ален (20 апреля 1998 г.). LATIN'98: Теоретическая информатика. Конспект лекций по информатике. 1380. Шпрингер, Берлин, Гейдельберг. С. 163–169. arXiv:Quant-ph / 9705002. Дои:10.1007 / BFb0054319. ISBN 978-3-540-64275-6. S2CID 118940551.
^ «Математический форум: спросите доктора математики: вопросы и ответы: проблема дня рождения». Mathforum.org. Получено 29 октября 2017.
^ Гупта, Ганеш (2015). "Что такое атака по случаю дня рождения ??". Дои:10.13140/2.1.4915.7443. Цитировать журнал требует | журнал = (Помогите)
^ Видеть верхняя и нижняя границы.
^ Жак Патарен, Одри Монтрей (2005). "Переосмысление схем Бенеша и бабочки" (PostScript, PDF ). Университет Версаля. Получено 2007-03-15. Цитировать журнал требует | журнал = (Помогите)
^ Грей, Джим; ван Инген, Катарина (25 января 2007 г.). «Эмпирические измерения частоты отказов дисков и ошибок». arXiv:cs / 0701166.
^ "CiteSeerX". Архивировано из оригинал на 2008-02-23. Получено 2006-05-02.
^ «Точно вычислить журнал (1 + x) для малых значений x». Mathworks.com. Получено 29 октября 2017.

внешняя ссылка

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

[1] Дэниел Дж. Бернштейн. «Анализ затрат на хэш-коллизии: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF). Cr.yp.to. Получено 29 октября 2017.

[2] Брассар, Жиль; Хёйер, Питер; Тэпп, Ален (20 апреля 1998 г.). LATIN'98: Теоретическая информатика. Конспект лекций по информатике. 1380. Шпрингер, Берлин, Гейдельберг. С. 163–169. arXiv:Quant-ph / 9705002. Дои:10.1007 / BFb0054319. ISBN 978-3-540-64275-6. S2CID 118940551.

[3] «Математический форум: спросите доктора математики: вопросы и ответы: проблема дня рождения». Mathforum.org. Получено 29 октября 2017.

[4] Гупта, Ганеш (2015). "Что такое атака по случаю дня рождения ??". Дои:10.13140/2.1.4915.7443. Цитировать журнал требует | журнал = (Помогите)

[5] Видеть верхняя и нижняя границы.

[6] Жак Патарен, Одри Монтрей (2005). "Переосмысление схем Бенеша и бабочки" (PostScript, PDF ). Университет Версаля. Получено 2007-03-15. Цитировать журнал требует | журнал = (Помогите)

[7] Грей, Джим; ван Инген, Катарина (25 января 2007 г.). «Эмпирические измерения частоты отказов дисков и ошибок». arXiv:cs / 0701166.

[8] "CiteSeerX". Архивировано из оригинал на 2008-02-23. Получено 2006-05-02.

[9] «Точно вычислить журнал (1 + x) для малых значений x». Mathworks.com. Получено 29 октября 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]