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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Розуміння питання[ред.ред. код]

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

Математичне підґрунтя[ред.ред. код]

дана функція 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(nH) буде ймовірністю. що хоча б одне значення трапилось більш як раз. Цю ймовірність можна приблизно виразити як

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

Нехай n(pH) буде найменшою кількістю значень, що ми маємо вибрати так, щоб імовірність знаходження повтору була не менша від  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 × 1019 різних виходів. Якщо вони всі рівноймовірні (найкращий випадок), тоді потрібно лише 5.1 × 109 спроб для отрмання колізії, із використанням грубої сили. Це чило відоме як межа днів народження (англ. birthday bound)[2] і для n-бітових кодів її можна обрахувати як 2n/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−18 до 10−15 — це оцінка невипраних бітових помилок (англ. uncorrectable bit error rate) (метрика для оцінки пошкодження даних, що дорівнює кількості помилок даних на прочитаний біт після застосування будь-якого визначеного методу виправлення помилок) типового жорсткого диску [1]. Теоретично, MD5, 128 біт, має залишатись в цих межах доки не досягнуто 820 мільярдів документів.

Легко побачити, що за умови нерівномірного розподілу виходів функції, зустріти колізію швидше. Поняття 'збалансованості' геш-функцій вимірює стійкість функції до атаки «днів народження» і дозволяє обчислити вразливість розповсюджених гешів на кшталт MD і SHA (Bellare and Kohno, 2004). На сьогодні найкращий пошукач колізій для SHA-1 потребує 251 обчислень гешу. Через відносну нестійкість до такої атаки в подальших розробках пропонують використовувати 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.[4]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. «Math Forum: Ask Dr. Math FAQ: The Birthday Problem». Архів оригіналу за 2013-07-22. 
  2. Див. Верхня та нижня межа.
  3. Jacques Patarin, Audrey Montreuil Benes and Butterfly schemes revisited (PostScript, PDF) Université de Versailles (2005). Процитовано 2007-03-15.
  4. DNS Cache Poisoning — The Next Generation

Посилання[ред.ред. код]