Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

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

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

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

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

Колізійна атака
Знаходження двох довільних різних повідомлень 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 і SHA-1. Колізійна атака проти MD5 була покращена настільки, що вона потребувала лише декількох секунд на звичайному комп'ютері.

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

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

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

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

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

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

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

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

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

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

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

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

Зауважимо, що всі сертифікати з відкритим ключем, по типу сертифікатів 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). 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). . Архів оригіналу за 18 квітня 2012. Процитовано 7 травня 2012. {{}}: Явне використання «та ін.» у: |author= ()
  7. . Microsoft. 3 червня 2012. Архів оригіналу за 7 червня 2012. Процитовано 4 червня 2012.
  8. Marc Stevens (7 червня 2012). . 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.]

Посилання

    Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

    Kolizijna ataka na kriptografichnij gesh namagayetsya znajti dva dovilnih vhodi yaki mayut odnakove gesh znachennya tobto gesh koliziyu Na vidminu vid ataki znahodzhennya pershovzoru ne viznacheni ani gesh znachennya ani odin z vhodiv Isnuye priblizno dva riznovidi kolizijnih atak Kolizijna ataka Znahodzhennya dvoh dovilnih riznih povidomlen m1 i m2 takih sho hash m1 hash m2 Prefiksna kolizijna ataka Dlya danih dvoh prefiksiv p1 p2 znajti dva dopovnennya m1 i m2 takih sho hash p1 m1 hash p2 m2 de ce diya ob yednannya Klasichna kolizijna atakaKolizijna ataka yaka znahodit dva riznih povidomlennya m1 i m2 takih sho hash m1 hash m2 V klasichnij kolizijnij ataci atkuvalnik ne maye kontrolyu nad vmistom zhodnogo z povidomlen voni dovilnim chinom obirayutsya algoritmom Duzhe podibno do togo sho shifruvannya z simetrichnimi klyuchami vrazlive do ataki povnogo pereboru kozhnij kriptografichnij gesh funkciyi vlastiva vrazlivist do znajdennya kolizij cherez ataku dniv narodzhennya vidpovidno do paradoksu dniv narodzhennya ci ataki nabagato shvidshi nizh povnij perebir Gesh v n bitiv mozhe buti zlamano za chas 2n 2 obchislen gesh funkciyi Diyevishi ataki mozhna znajti iz vikoristannyam kriptoanalizu do konkretnoyi gesh funkciyi Shojno znajdeno kolizijnu ataku i vona spracovuye shvidshe za ataku dniv narodzhennya to gesh funkciya vvazhayetsya zlamanoyu Zmagannya gesh funkcij organizovane NIST bulo znachnoyu miroyu zumovlene oprilyudnennyam kolizijnih atak proti dvoh shirokozastosovnih gesh funkcij MD5 i SHA 1 Kolizijna ataka proti MD5 bula pokrashena nastilki sho vona potrebuvala lishe dekilkoh sekund na zvichajnomu komp yuteri Gesh koliziyi utvoreni takim chinom zazvichaj mayut stalu dovzhinu i malo strukturovani otzhe ne mozhut buti pryamo zastosovani dlya atakuvannya shiroko rozpovsyudzhenih formativ dokumentiv i protokoliv Odnak obhidni shlyahi mozhna znajti cherez zlovzhivannya dinamichnimi konstrukciyami prisutnimi v bagatoh formatah Takij shkidnickij dokument mig bi mistiti dva riznih povidomlennya v odnomu dokumenti za neobhidnistyu pokazuyuchi odin chi drugij zalezhno vid togo yake z dvoh konfliktnih gesh znachen prisutnye Komp yuterni programi mayut umovni perehodi if then else sho dozvolyayut yake z dvoh znachen maye pevne misce v fajli Deyaki formati dokumentiv taki yak PostScript abo Makrosi v Microsoft Word takozh mayut umovni perehodi Fajlovi formati sho mistyat zobrazhennya vklyuchno z TIFF i PDF vrazlivi do kolizijnih atak iz vikoristannya konfliktuyuchih gesh znachen takih yak indeksovani kolori Kolizijna ataka z obranim prefiksomRozvitkom kolizijnoyi ataki ye kolizijna ataka z obranim prefiksom yaka ye specifichnoyu dlya gesh funkcij Merkla Demgarda V comu vipadku mozhe obrati dva dovilni rizni dokumenti i todi dodavati znachennya taki sho otrimani dokumenti matimut odnakovi gesh znachennya Cya ataka nabagato potuzhnisha nish klasichna kolizijna ataka Dlya danih dvoh riznih prefiksiv p1 p2 ataka znahodit dva dopovnennya m1 i m2 taki sho hash p1 m1 hash p2 m2 de konkatenaciya 2007 bula vinajdena kolizijna ataka z obranim prefiksom proti MD5 yaka vimagala lishe 250 obchislen funkciyi MD5 Zvit takozh vkazuye na dva X 509 sertifikati dlya vidminnih domennih imen z konfliktuyuchimi gesh znachennyami Ce znachit sho akreditovanij centr sertifikaciyi klyuchiv mogli zapitati pidpisati sertifikat dlya odnogo domenu i todi vikoristati cej sertifikati shob uosobiti inshij domen Mozhlivo najkrasha realna kolizijna ataka bula oprilyudnena v grudni 2008 koli grupa doslidnikiv pokazali vrazlivist infrastrukturi vidkritih klyuchiv do kolizijnih atak vklyuchno z utvorennyam SSL sertifikatu yakij dozvolyaye napadniku uosobiti akreditovanij centr sertifikaciyi klyuchiv Tut vikoristali perevagu prefiksnoyi kolizijnoyi ataki proti gesh funkciyi MD5 Ce oznachaye sho napadnik mozhe uosobiti SSL bezpechnij vebsajt yak lyudina poseredini pidrivayuchi perevirku sertifikativ u veboglyadachi She girshe shahrajskij sertifikat ne mozhe vidklikati spravzhnij centr i takozh vin mozhe mati yakij zavgodno termin diyi Popri te sho MD5 buv vidomij svoyeyu slabkistyu she 2004 centri sertifikaciyi vse she pidpisuvali sertifikati z vikoristannyam MD5 u grudni 2008 i prinajmni she odin sertifikat pidpisanij Majkrosoft buv u vikoristanni u travni 2012 roku Virus Flame uspishno vikoristovuvav novu variaciyu kolizijnoyi ataki z obranim prefiksom dlya zlovzhivannya z pidpisom dlya vikonannya kodu svoyih komponent vid imeni korenevogo sertifikatu Majkrosoft sho prodovzhuvav vikoristovuvati skomprometovanij MD5 algoritm Perebig napaduBagato sposobiv vikoristannya kriptografichnih gesh funkcij ne pokladayutsya na kolizijnu stijkist otzhe kolizijni ataki ne vplivayut na yih bezpeku Napriklad geshuvannya paroliv i HMAC ne vrazlivi HMAC ne vimagaye vid svoyeyi funkciyi stiskannya stijkosti do kolizij lishe shob vona bula psevdovipadkovoyu funkciyeyu Dlya uspishnosti ataki napadnik maye keruvati vhidnimi danimi gesh funkciyi Cifrovi pidpisi Cherez te sho algoritmi cifrovih pidpisiv ne mozhut diyevo pidpisuvati veliki kilkosti danih bilshist vtilen vikoristovuyut gesh funkciyu dlya zmenshennya stiskannya danih yaki potrebut pidpisu do pevnogo rozmiru Shema cifrovih pidpisiv chasto vrazlivi dlya kolizij hiba sho vikoristovuyutsya pidhodi na kshtalt vipadkovogo geshuvannya Zauvazhimo sho vsi sertifikati z vidkritim klyuchem po tipu sertifikativ SSL takozh pokladayutsya na bezpeku cifrovih pidpisiv i gesh koliziyi stanovlyat dlya nih zagrozu Zvichajnij perebig ataki takij Mellori stvoryuye dva riznih dokumenti A i B yaki mayut totozhni gesh znachennya koliziyu Todi Mellori vidsilaye dokument A Alisi yaka pogodzhuyetsya z dokumentam i pidpisuye jogo a potim vidsilaye nazad Mellori Mellori kopiyuye pidpis otrimanij vid Alisi z dokumentu A do dokumentu B Todi vidsilaye dokument B Bobu stverdzhuyuchi sho Alisa pidpisala dokument U zv yazku z tim sho cifrova signatura zbigayetsya z heshem dokumentu PZ Boba ne maye zmogi viyaviti pidminu PrimitkiXiaoyun Wang Dengguo Feng Xuejia Lai Hongbo Yu Collisions for Hash Functions MD4 MD5 HAVAL 128 and RIPEMD 2011 09 03 u Wayback Machine Cryptology ePrint Archive Report 2004 199 16 Aug 2004 revised 17 Aug 2004 Retrieved July 27 2008 M M J Stevens On Collisions for MD5 2007 1 chervnya z dzherela 17 travnya 2017 Procitovano 7 travnya 2012 Magnus Daum Stefan Lucks Hash Collisions The Poisoned Message Attack 2005 rump session Arhiv originalu za 22 lipnya 2013 Procitovano 7 travnya 2012 Max Gebhardt Georg Illies Werner Schindler A Note on the Practical Value of Single Hash Collisions for Special File Formats z dzherela 5 chervnya 2011 Procitovano 7 travnya 2012 Marc Stevens Arjen Lenstra Benne de Weger Chosen prefix Collisions for MD5 and Colliding X 509 Certificates for Different Identities 2007 30 listopada z dzherela 11 travnya 2012 Procitovano 7 travnya 2012 Alexander Sotirov ta in 30 grudnya 2008 Arhiv originalu za 18 kvitnya 2012 Procitovano 7 travnya 2012 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite web title Shablon Cite web cite web a Yavne vikoristannya ta in u author dovidka Microsoft 3 chervnya 2012 Arhiv originalu za 7 chervnya 2012 Procitovano 4 chervnya 2012 Marc Stevens 7 chervnya 2012 Centrum Wiskunde amp Informatica Arhiv originalu za 28 lyutogo 2017 Procitovano 9 chervnya 2012 Hash Collision Q amp A Cryptography Research Inc 15 lyutogo 2005 originalu za 17 lipnya 2008 Procitovano 7 travnya 2012 Because of the way hash functions are used in the HMAC construction the techniques used in these recent attacks do not apply Shai Halevi and Hugo Krawczyk Randomized Hashing and Digital Signatures 20 chervnya 2009 u Wayback Machine Posilannya

    Дата публікації:
    Топ