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

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

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

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

Колізійна атака
Знаходження двох довільних різних повідомлень 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]

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

Collision atack exploit pdf ICS.gif
  • Комп'ютерні програми мають умовні переходи (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]

Перебіг нападу[ред.ред. код]

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

Цифрові підписи[ред.ред. код]

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

Зауважимо, що всі сертифікати з відкритим ключем, по типу сертифікатів 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 (June 2007).
  3. Magnus Daum, Stefan Lucks. «Hash Collisions (The Poisoned Message Attack)». Eurocrypt 2005 rump session. Архів оригіналу за 2013-07-22. 
  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-11-30).
  6. Alexander Sotirov et al (2008-12-30). «Creating a rogue CA certificate». Архів оригіналу за 2013-07-22. 
  7. «Hash Collision Q&A». Cryptography Research Inc. 2005-02-15. Архів оригіналу за 2008-07-17. «Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply» 
  8. Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures

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