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

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

Нехай задана функція ${\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 p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)},\,}$

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

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

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

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

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

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

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

Бітів	Можливих виходів (приблизно)(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) (метрика для оцінки пошкодження даних, що дорівнює кількості помилок даних на прочитаний біт після застосування будь-якого визначеного методу виправлення помилок) типового жорсткого диску . Теоретично, MD5, 128 біт, має залишатись в цих межах доки не досягнуто 820 мільярдів документів.

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

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

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

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

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

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

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

• "What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.
• "Birthday Attack" X5 Networks Crypto FAQs