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

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

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

ред.

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

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

ред.

Нехай задана функція  , мета атаки — це знаходження двох різних входів до функції   таких, що  . Така пара   зветься колізією. Методом виявлення колізій є просте обчислення функції   для різних значень на вході, які можуть братись довільним або псевдодовільним чином доки не отримаємо потрібний вислід. Через парадокс днів народження, цей метод найімовірніше буде дієвим. Зокрема, якщо функція   породжує будь-яке значення з   рівноймовірно і   достатньо велика множина, тоді ми очікуємо отримати пару різних аргументів   і   з   після обчислення функції для близько   різних аргументів в середньому.

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

 

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

 

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

 

Нехай Q(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] [Архівовано 13 квітня 2010 у Wayback Machine.]. Теоретично, MD5, 128 біт, має залишатись в цих межах доки не досягнуто 820 мільярдів документів.

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

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

ред.

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

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

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

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

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

Див. також

ред.

Примітки

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

Посилання

ред.