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

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

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

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

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

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

Дуже подібно до того, що шифрування з симетричними ключами вразливе до атаки повного перебору, кожній криптографічній геш-функції властива вразливість до знайдення колізій через атаку «днів народження». відповідно до парадоксу днів народження, ці атаки набагато швидші ніж повний перебір. Геш в n бітів може бути зламано за час 2n/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, яка вимагала лише 250 обчислень функції 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 Бобу, стверджуючи, що Аліса підписала документ. У зв'язку з тим, що цифрова сигнатура збігається з хешем документу, ПЗ Боба не має змоги виявити підміну.

Примітки

  1. ↑ а б Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD [Архівовано 2011-09-03 у Wayback Machine.], Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.
  2. ↑ M.M.J. Stevens. On Collisions for MD5. — 2007. — 1 червня. Архівовано з джерела 17 травня 2017. Процитовано 7 травня 2012.
  3. ↑ Magnus Daum, Stefan Lucks. Hash Collisions (The Poisoned Message Attack). Eurocrypt 2005 rump session. Архів оригіналу за 22 липня 2013. Процитовано 7 травня 2012.
  4. ↑ а б Max Gebhardt, Georg Illies, Werner Schindler. A Note on the Practical Value of Single Hash Collisions for Special File Formats. Архівовано з джерела 5 червня 2011. Процитовано 7 травня 2012.
  5. ↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. — 2007. — 30 листопада. Архівовано з джерела 11 травня 2012. Процитовано 7 травня 2012.
  6. ↑ Alexander Sotirov та ін. (30 грудня 2008). Creating a rogue CA certificate. Архів оригіналу за 18 квітня 2012. Процитовано 7 травня 2012. {{cite web}}: Явне використання «та ін.» у: |author= (довідка)
  7. ↑ Microsoft releases Security Advisory 2718704. Microsoft. 3 червня 2012. Архів оригіналу за 7 червня 2012. Процитовано 4 червня 2012.
  8. ↑ Marc Stevens (7 червня 2012). CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware. Centrum Wiskunde & Informatica. Архів оригіналу за 28 лютого 2017. Процитовано 9 червня 2012.
  9. ↑ Hash Collision Q&A. Cryptography Research Inc. 15 лютого 2005. Архів оригіналу за 17 липня 2008. Процитовано 7 травня 2012. Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply
  10. ↑ Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures [Архівовано 20 червня 2009 у Wayback Machine.]

Посилання