Атака «днів народження»

Атака «днів народження» — це різновид криптографічної атаки, яка використовує математичне підґрунтя парадоксу днів народження в теорії ймовірностей. Цю атаку можна використати для втручання в зв'язок між двома або більше учасниками. Атака покладається на високу ймовірність знаходження колізій між випадковими спробами і встановленим порядком переставок (принцип Діріхле), як описано в парадоксі днів народження.

Розуміння питання

Для прикладу, розглянемо перебіг подій за якого вчитель класу з 30 студентами запитує кожного про його день народження, щоб визначити чи є збіг (відповідно до колізій гешу як описано нижче; задля простоти, не зважаймо на 29 лютого). Інтуїтивно, така подія може видатись малоймовірною. Якщо вчитель обере певний день (наприклад, 16 вересня), тоді шанс збігу з днем народження одного зі студентів становить $1-(364/365)^{30}$ або ж $29/365$, близько 7.9%. Однак, імовірність того збігу днів народження двох студентів становить близько 70% (за формулою $1-365!/((365-n)!\cdot 365^{n})$ ).

Математичне підґрунтя

Нехай задана функція $f$, мета атаки — це знаходження двох різних входів до функції $x_{1},x_{2}$ таких, що $f(x_{1})=f(x_{2})$. Така пара $x_{1},x_{2}$ зветься колізією. Методом виявлення колізій є просте обчислення функції $f$ для різних значень на вході, які можуть братись довільним або псевдодовільним чином доки не отримаємо потрібний вислід. Через парадокс днів народження, цей метод найімовірніше буде дієвим. Зокрема, якщо функція $f(x)$ породжує будь-яке значення з $H$ рівноймовірно і $H$ достатньо велика множина, тоді ми очікуємо отримати пару різних аргументів $x_{1}$ і $x_{2}$ з $f(x_{1})=f(x_{2})$ після обчислення функції для близько $1.25{\sqrt {H}}$ різних аргументів в середньому.

Розглянемо наступний дослід. З множини значень H ми однорідно виберемо n довільних значень, отже з можливими повторами. Нехай p(n; H) буде ймовірністю, що хоча б одне значення трапилось більш як раз. Цю ймовірність можна приблизно виразити як (див. виведення цього наближення в парадоксі днів народження):

$p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)},\,$

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

$n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}},$

візьмемо імовірність колізій 0.5, приходимо до

$n(0.5;H)\approx 1.1774{\sqrt {H}}.\,$

Нехай Q(H) буде очікуваною кількістю значень, що ми маємо обрати для отримання першої колізії. Це число можна приблизно виразити як

$Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}.$

Як приклад, якщо використовується 64-бітовий геш, то існує близько 1.8 × 10¹⁹ різних виходів. Якщо вони всі рівноймовірні (найкращий випадок), тоді потрібно лише 5.1 × 10⁹ спроб для отримання колізії, із використанням грубої сили. Це число знане як межа днів народження (англ. birthday bound) і для n-бітових кодів її можна обрахувати як 2^n/2.Інші приклади такі:

Бітів	Можливих виходів (приблизно)(H)	Бажано ймовірність випадкової колізії (приблизно) (p)
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
16	6.6 × 104	2	2	2	2	2	11	36	1.9 × 102	3.0 × 102	4.3 × 102
32	4.3 × 109	2	2	2	2.9	93	2.9 × 103	9.3 × 103	5.0 × 104	7.7 × 104	1.1 × 105
64	1.8 × 1019	6.1	1.9 × 102	6.1 × 103	1.9 × 105	6.1 × 106	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	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	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	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	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⁻¹⁵ — це оцінка невипраних бітових помилок (англ. uncorrectable bit error rate) (метрика для оцінки пошкодження даних, що дорівнює кількості помилок даних на прочитаний біт після застосування будь-якого визначеного методу виправлення помилок) типового жорсткого диску [1] [Архівовано 13 квітня 2010 у Wayback Machine.]. Теоретично, MD5, 128 біт, має залишатись в цих межах доки не досягнуто 820 мільярдів документів.

Легко побачити, що за умови нерівномірного розподілу виходів функції, зустріти колізію швидше. Поняття 'збалансованості' геш-функцій вимірює стійкість функції до атаки «днів народження» і дозволяє обчислити вразливість розповсюджених гешів на кшталт MD і SHA (Bellare and Kohno, 2004 [Архівовано 23 лютого 2008 у Wayback Machine.]). На сьогодні найкращий пошукач колізій для SHA-1 потребує 2⁵¹ обчислень гешу. Через відносну нестійкість до такої атаки в подальших розробках пропонують використовувати SHA-256 або SHA-512.

Чутливість цифрових підписів

Цифровий підпис може бути чутливий до атаки «днів народження». Зазвичай для повідомлення $m$ спочатку обчислюють $f(m)$, де $f$ — це криптографічна геш-функція, і $f(m)$ шифрується за допомогою секретного ключа. Припустимо Аліса хоче перехитрити Боба, щоб він підписав шахрайську угоду. Аліса готує чесну угоду $m$ і шахрайський примірник $m'$. Тоді вони знаходить місця де $m$ можна змінити без зміни значення, такі як додавання порожніх рядків, ком, пропусків, заміну сутямків тощо. Поєднуючи ці зміни, вона може утворити значну кількість змінених $m$, які всі є чесними угодами.

Подібним чином, Аліса створює відміни шахрайської угоди $m'$. Тоді вона застосовує геш-функцію до всіх варіацій доки не знайде примірник чесної і шахрайської угоди геші яких збігаються, $f(m)=f(m')$. Вона подає чесну версію Бобу на підпис. Після того як Боб підписав, Аліса бере підпис і додає його до шахрайської угоди. цей підпис доводить, що Боб підписав контракт.

Імовірності трохи різняться порівняно до початкової проблеми днів народження, бо Аліса не отримає переваг у разі отримання збігу гешів у двох шахрайських видозмін угоди. Мета Аліси полягає у віднайдені двійки чесної та шахрайської угод. Рівняння проблеми днів народження застосовується де $n$ — це кількість пар. Кількість обрахованих гешів становить $2n$.

Для уникнення цієї атаки, довжина виходу геш-функції може бути обрана достатньо великою, щоб атака стала обчислювально нездійсненною, тобто близько вдвічі більше біт ніж потрібно для уникнення атаки повного перебору ключів (через квадратний корінь в цій формулі $1.25{\sqrt {H}}$).

Атака «днів народження» часто згадується як потенційна слабкість DNS.

Див. також

• Колізійна атака

Посилання

• "What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.
• "Birthday Attack" [Архівовано 21 квітня 2021 у Wayback Machine.] X5 Networks Crypto FAQs