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

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

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

Докладніше: Парадокс днів народження

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

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

Нехай задана функція ${\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) і для 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 × 10^4	2	2	2	2	2	11	36	1.9 × 10^2	3.0 × 10^2	4.3 × 10^2
32	4.3 × 10^9	2	2	2	2.9	93	2.9 × 10^3	9.3 × 10^3	5.0 × 10^4	7.7 × 10^4	1.1 × 10^5
64	1.8 × 10^19	6.1	1.9 × 10^2	6.1 × 10^3	1.9 × 10^5	6.1 × 10^6	1.9 × 10^8	6.1 × 10^8	3.3 × 10^9	5.1 × 10^9	7.2 × 10^9
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	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	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	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⁻¹⁸ до 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.

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

Цифровий підпис може бути чутливий до атаки «днів народження». Зазвичай для повідомлення ${\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.

Див. також

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

Примітки

1. Math Forum: Ask Dr. Math FAQ: The Birthday Problem. Архів оригіналу за 22 липня 2013. Процитовано 4 травня 2012.
2. Див. Верхня та нижня межа.
3. Jacques Patarin, Audrey Montreuil (2005). . Université de Versailles. Архів оригіналу (PostScript, PDF) за 29 вересня 2007. Процитовано 15 березня 2007.
4. . Архів оригіналу за 24 грудня 2010. Процитовано 5 травня 2012.

Посилання

• from RSA Security's crypto FAQ.
• "Birthday Attack" [ 21 квітня 2021 у Wayback Machine.] X5 Networks Crypto FAQs