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

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

Існує приблизно два різновиди колізійних атак:

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

Знаходження двох довільних різних повідомлень m1 і m2, таких що hash(m1) = hash(m2).

Префіксна колізійна атака

Для даних двох префіксів p1, p2 знайти два доповнення m1 і m2, таких що hash(p1 ∥ m1) = hash(p2 ∥ m2) (де ∥ — це дія об'єднання).

Класична колізійна атака

Колізійна атака, яка знаходить два різних повідомлення m1 і m2, таких що hash(m1) = hash(m2). В класичній колізійній атаці, аткувальник не має контролю над вмістом жодного з повідомлень, вони довільним чином обираються алгоритмом.

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

Дієвіші атаки можна знайти із використанням криптоаналізу до конкретної геш-функції. Щойно знайдено колізійну атаку і вона спрацьовує швидше за атаку днів народження, то геш-функція вважається зламаною. Змагання геш-функцій організоване NIST було значною мірою зумовлене оприлюдненням колізійних атак проти двох широкозастосовних геш-функцій MD5^[1] і SHA-1. Колізійна атака проти MD5 була покращена настільки, що вона потребувала лише декількох секунд на звичайному комп'ютері.^[2]

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

• Комп'ютерні програми мають умовні переходи (if-then-else), що дозволяють яке з двох значень має певне місце в файлі.
• Деякі формати документів такі як PostScript або Макроси в Microsoft Word, також мають умовні переходи.^[3][4]
• Файлові формати, що містять зображення, включно з TIFF і PDF, вразливі до колізійних атак із використання конфліктуючих геш-значень таких як індексовані кольори.^[4]

Колізійна атака з обраним префіксом

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

Для даних двох різних префіксів p1, p2, атака знаходить два доповнення m1 і m2, такі що hash(p1 ∥ m1) = hash(p2 ∥ m2) (де ∥ — конкатенація).

2007, була винайдена колізійна атака з обраним префіксом проти MD5, яка вимагала лише 2⁵⁰ обчислень функції MD5. Звіт також вказує на два X.509 сертифікати для відмінних доменних імен, з конфліктуючими геш-значеннями. Це значить, що акредитований центр сертифікації ключів могли запитати підписати сертифікат для одного домену, і тоді використати цей сертифікати щоб уособити інший домен.^[5]

Можливо, найкраща реальна колізійна атака була оприлюднена в грудні 2008, коли група дослідників показали вразливість інфраструктури відкритих ключів до колізійних атак, включно з утворенням SSL-сертифікату, який дозволяє нападнику уособити акредитований центр сертифікації ключів. Тут використали перевагу префіксної колізійної атаки проти геш-функції MD5. Це означає, що нападник може уособити SSL-безпечний вебсайт як людина посередині, підриваючи перевірку сертифікатів у вебоглядачі. Ще гірше, шахрайський сертифікат не може відкликати справжній центр і також він може мати який завгодно термін дії. Попри те, що MD5 був відомий своєю слабкістю ще 2004,^[1] центри сертифікації все ще підписували сертифікати з використанням MD5 у грудні 2008,^[6] і принаймні ще один сертифікат підписаний Майкрософт був у використанні у травні 2012 року.

Вірус Flame успішно використовував нову варіацію колізійної атаки з обраним префіксом для зловживання з підписом для виконання коду своїх компонент від імені кореневого сертифікату Майкрософт, що продовжував використовувати скомпрометований MD5 алгоритм.^[7][8]

Перебіг нападу

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

Цифрові підписи

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

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

Звичайний перебіг атаки такий:

1. Меллорі створює два різних документи A і B, які мають тотожні геш-значення (колізію).
2. Тоді Меллорі відсилає документ A Алісі, яка погоджується з документам і підписує його, а потім відсилає назад Меллорі.
3. Меллорі копіює підпис отриманий від Аліси з документу А до документу B.
4. Тоді відсилає документ B Бобу, стверджуючи, що Аліса підписала документ. У зв'язку з тим, що цифрова сигнатура збігається з хешем документу, ПЗ Боба не має змоги виявити підміну.