Kolizní útok

Kolizní útok v kryptografii  je hledání dvou různých vstupních bloků kryptografické hašovací funkce , které vytvářejí stejnou hašovací hodnotu, tedy hašovací kolizi . Na rozdíl od útoku preimage není hodnota hash zvolena záměrně.

Přibližně[ objasnit ] Existují dva různé typy kolizních útoků:

Klasický kolizní útok

Kolizní útok najde dvě různé zprávy m1 a m2 takové, že . V klasickém případě útoku nemá útočník kontrolu nad obsahem zpráv, ale jsou náhodně vybírány algoritmem. Mnoho symetrických kryptosystémů je zranitelných vůči útokům hrubou silou , jakákoli kryptografická hashovací funkce je podle definice zranitelná vůči narozeninovému útoku . Vzhledem k narozeninovému paradoxu může být druhá metoda útoku mnohem rychlejší než metoda hrubou silou. Hash N bitů lze zlomit 2n / 2krát (výpočtem hashovací funkce). Nejúčinnější útoky jsou možné při použití kryptoanalýzy na konkrétní hashovací funkci. Když je kolizní útok rychlejší než „narozeninový“ útok, hašovací funkce jsou často odsuzovány jako „rozbité“. Vytvoření hašovací funkce SHA-3 (soutěž) bylo do značné míry motivováno potřebou nahradit staré funkce MD5 [1] a SHA-1 . Kolizní útoky proti algoritmu MD5 se zlepšily natolik, že na běžném počítači zaberou jen několik sekund. [2] Kolize hashů generované tímto způsobem mají obecně konstantní délku a do značné míry nestrukturované, takže je nelze přímo použít k útoku na běžné formáty dokumentů nebo protokoly. Řešení jsou však možná zneužitím dynamických konstrukcí přítomných v mnoha formátech. Vzniknou tak dva dokumenty, které jsou navzájem shodné, takže mají stejnou hash hodnotu. Pokud je jeden dokument podepsán důvěryhodnou osobou, lze její podpis zkopírovat do jiného souboru. Takový škodlivý dokument by obsahoval dvě různé zprávy ve stejném dokumentu, ale přesto by byl schopen zobrazit kteroukoli z nich prostřednictvím malých změn v souboru:

Kolizní útok s danou předponou

Výsledkem vylepšení kolizního útoku byl kolizní útok s daným prefixem, určený pro strukturu Merkle-Damgard . V tomto případě si útočník může vybrat 2 náhodné různé dokumenty a pak je doplnit 2 různými vypočítanými hodnotami, takže 2 dokumenty skončí se stejnou hash hodnotou. Tento útok je vážnější než jeho klasická verze.

Matematicky vzato, existují 2 různé předpony p1, p2 , jejich 2 doplňky m1 a m2 se vypočítají tak, že hash(p1 ∥ m1) = hash(p2 ∥ m2) (kde ∥ je operace zřetězení ).

V roce 2007 byl vytvořen útok na kolize hash s prefixem MD5, který vyžadoval přibližně 250 výpočtů funkce MD5 . Poznámka obsahovala dva certifikáty X.509 pro různé názvy domén, které mají stejné hashovací funkce. To znamená, že certifikát jedné důvěryhodné domény může používat jiná neznámá doména. [5]

Skutečný kolizní útok byl zveřejněn v prosinci 2008, kdy skupina bezpečnostních výzkumníků zveřejnila falešný podpisový certifikát X.509 , který lze použít k anonymní autorizaci certifikátu pomocí kolizní útoku s danou předponou hash MD5. To znamenalo, že útočník mohl podvrhnout jakoukoli webovou stránku zabezpečenou TLS jako prostředníka , čímž by porušil ověření certifikátu zabudované do každého webového prohlížeče pro zabezpečení elektronického obchodu . Falešný certifikát nemohou důvěryhodné strany zrušit, může také vypršet libovolně dlouhá doba. Navzdory slabinám MD5 zjištěným v roce 2004 [1] v prosinci 2008 vyšlo najevo, že mnoho lidí stále používá certifikáty s touto hashovací funkcí [6] a přinejmenším Microsoft ji stále používal v květnu 2012.

Ve Flame malware úspěšně použil novou variantu útoku s předponou kolize ke zfalšování komponent pro podepisování kódu pomocí kořenových certifikátů společnosti Microsoft, které stále používaly kompromitovaný algoritmus MD5. [7] [8]

Schéma útoku

Mnoho aplikací s kryptografickými hašovacími funkcemi nevyžaduje ochranu proti útoky na kolizi nemohou jejich ochranu obejít Například HMAC nepodléhají tomuto druhu útoku. [9] Pro úspěšný útok musí mít útočník kontrolu nad vstupem.

Elektronické podpisy

Protože algoritmy elektronického podpisu nemohou efektivně podepisovat velká množství dat, mnoho doplňků používá k jejich podepisování v pevné velikosti funkce komprese dat. Schémata elektronického podpisu jsou často náchylná ke kolizím navzdory skutečnosti, že používají techniku ​​náhodného hašování. [deset]

Obvykle útok probíhá takto:

  1. Eva vytvoří 2 různé dokumenty A a B se stejnými hodnotami hash. Eve se snaží oklamat Boba tím, že vydává svůj dokument za Alicin.
  2. Eva pošle dokument A Alici , která důvěřuje obsahu dokumentu, podepíše jeho hash a pošle podpis Evě.
  3. Eva připojí podpis dokumentu A k dokumentu B.
  4. Eva pak pošle podpis a dokument B Bobovi s tím, že dokument podepsala Alice. Protože elektronický podpis kontroluje pouze hašovací hodnotu dokumentu B, Bob o substituci neví.

V roce 2008 výzkumníci napadli MD5 s předponou pomocí výše uvedeného skriptu, aby vytvořili falešný certifikát. Vytvořili 2 verze certifikátu veřejného klíče TLS , z nichž jedna byla ověřena pro autorizaci RapidSSL. Jiná verze, která má stejnou hodnotu hash MD5, obsahovala příznaky, které signalizovaly prohlížeči důvěru a právo vydávat důvěryhodnost jiným certifikátům [11] .

Poznámky

  1. ↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Kolize pro hashovací funkce MD4, MD5, HAVAL-128 a RIPEMD Archivováno 23. srpna 2011. , Cryptology ePrint Archive Report 2004/199, 16. srpna 2004, revidováno 17. srpna 2004. Staženo 27. července 2008.
  2. ↑ MJ Stevens. O kolizích pro MD5  (neopr.) . - 2007. - Červen.
  3. ↑ Magnus Daum, Stefan Lucks. Hash Collisions (The Poisoned Message Attack) . Zasedání Eurocrypt 2005 . Archivováno z originálu 27. března 2010.
  4. ↑ 1 2 3 Max Gebhardt, Georg Illies, Werner Schindler. Poznámka k praktické hodnotě kolizí jednotlivých hash pro speciální formáty souborů  (anglicky)  : journal.
  5. ↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Kolize s vybranými prefixy pro MD5 a kolidující certifikáty X.509 pro různé identity  (anglicky)  : časopis. - 2007. - 30. listopadu.
  6. ↑ Alexandr Sotirov. Vytváření podvodného certifikátu CA (nedostupný odkaz) (30. prosince 2008). Datum přístupu: 15. prosince 2015. Archivováno z originálu 18. dubna 2012. 
  7. ↑ Microsoft vydává bezpečnostní upozornění 2718704 . Microsoft (3. června 2012). Získáno 4. června 2012. Archivováno z originálu 7. června 2012.
  8. ↑ Marc Stevens. CWI Cryptanalist objevil novou variantu kryptografického útoku v malwaru Flame Spy . Centrum Wiskunde & Informatica (7. června 2012). Získáno 9. června 2012. Archivováno z originálu 28. února 2017.
  9. ↑ Otázky a odpovědi o hash Collision . Cryptography Research Inc (15. února 2005). "Vzhledem k tomu, jak jsou hashovací funkce použity v konstrukci HMAC, techniky použité v těchto nedávných útocích neplatí." Archivováno z originálu 17. července 2008.
  10. ↑ Shai Halevi a Hugo Krawczyk, Randomizované hašování a digitální podpisy Archivováno 20. června 2009 na Wayback Machine
  11. ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger (30. prosince 2008). MD5 je dnes považováno za škodlivé . Chaos Communication Congress 2008. Archivováno z originálu dne 2017-03-25 . Staženo 2015-12-15 . Použitý zastaralý parametr |deadlink=( nápověda )

Odkazy