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

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

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

Колізійна атака
Знаходження двох довільних різних повідомлень 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, 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 червня.
  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. Marc Stevens, Arjen Lenstra, Benne de Weger. Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. — 2007. — 30 листопада.
  6. Alexander Sotirov et al (30 грудня 2008). Creating a rogue CA certificate. Архів оригіналу за 18 квітня 2012. Процитовано 7 травня 2012.
  7. Microsoft releases Security Advisory 2718704. Microsoft. 3 червня 2012. Процитовано 4 червня 2012.
  8. Marc Stevens (7 червня 2012). CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware. Centrum Wiskunde & Informatica. Процитовано 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

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.