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ů:
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:
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]
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.
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:
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] .