Collision attack
V kryptografii, kolize útok na kryptografický hash se snaží najít dva libovolné vstupy, které budou produkovat stejnou hodnotu hash, tj. hash kolize . Na rozdíl od útoku preimage , je uvedeno ani hodnota mřížky, ani jeden ze vstupů.
Existují zhruba dva typy kolize:
Najít dvou libovolných různé zprávy m1 a m2 taková, že hash (m1) = hash (m2) .
Vzhledem k tomu, dva různé předpony p1, p2 najdeme dva přídavky m1 am2 taková, že hash (p1 ∥ m1) = hash (p2 ∥ m2) (kde ∥ je zřetězeníprovoz).
Matematicky řečeno, kolize útok najde dvě různé zprávy m1 a m2 , tak, abyhash (m1) = hash (m2) . V klasické kolizní útok, útočník nemá žádnou kontrolu nad obsahem obou zpráv, ale oni jsou zvolena libovolně podle algoritmu.
Stejně jako symetrický klíč šifry jsou náchylné k útoku hrubou silou , každýkryptografické hashovací funkce je zákonitě zranitelné ke kolizím pomocí útok narozenin . Vzhledem k narozeninám problém , tyto útoky jsou mnohem rychleji než hrubé síly by. Hash n bitů lze rozdělit do 2 n / 2 času (hodnocení hash funkce).
Účinnější útoky jsou možné tím, že zaměstná dešifrování na konkrétní hašovacích funkcí. Je-li kolize útok objevena a je zjištěno, že je rychlejší než narozeninový útok, je funkce mřížky často odsouzen jako "zlomený". NIST hash funkce soutěž byla velmi indukována publikovaná kolize útoků proti dvěma velmi běžně používaných hašovacích funkcí, MD5 [ 1 ] a SHA-1 . Ke kolizi útoky proti MD5 se zlepšila natolik, že to trvá jen pár vteřin na pravidelné počítače.[ 2 ] Hash kolize takto vytvořené jsou obvykle konstantní délky a do značné míry nestrukturovaný, takže nelze přímo použít k útoku rozšířené formáty dokumentů nebo protokolů.
Nicméně, řešení jsou možná tím, že zneužila dynamické konstrukty přítomné v mnoha formátech. Tímto způsobem by dva dokumenty se vytvoří, které jsou podobné jako to možné, aby se mají stejnou hodnotu hash. Jeden dokument by být prokázáno, že orgán, který bude podepsána, a pak může být podpis kopírovat do jiného souboru. Takový škodlivý dokument bude obsahovat dvě různé zprávy ve stejném dokumentu, ale podmíněně zobrazit jednu nebo druhou přes drobné změny do souboru:
Některé formáty dokumentů, jako PostScript , nebo maker v aplikaci Microsoft Word , mají podmíněné konstrukce. [ 3 ] [ 4 ] (if-then-else), které umožňují testování, zda umístění v souboru má jednu hodnotu nebo jiný s cílem kontrolovat, co se zobrazí .
TIFF soubory mohou obsahovat oříznuté obrázky, s jinou částí obrazu jsou zobrazovány bez ovlivnění hodnoty hash. [ 4 ]
PDF soubory jsou citlivé na kolize pomocí barevné hodnoty (takové, že text jedné zprávy se zobrazí s bílou barvou, který se hodí do pozadí, a text na straně druhé zprávy se zobrazí s tmavou barvou), které pak mohou být přizpůsobeny tak, aby změny podepsaného dokumentu je obsah. [ 4 ]
Rozšíření kolize útoku je volený-prefix kolize útok, který je specifický proMerkle-Damgård hašovacích funkcí . V tomto případě, může útočník vybrat dvě libovolně různé dokumenty, a pak připojit různé vypočtené hodnoty, které vedou k celé dokumentaci, která mají stejnou hodnotu hash. Tento útok je mnohem silnější než klasické kolizní útok.
Matematicky řečeno, vzhledem dva různé předpony p1, p2 , útok najde dva přídavky m1 a m2 taková, že hash (p1 ∥ m1) = hash (p2 ∥ m2) (kde ∥ jezřetězení provoz).
V roce 2007, byl vybrán-prefix kolize útok v neprospěch MD5, vyžaduje zhruba 2 50 vyhodnocení MD5 funkce. Papír také demonstruje dva X.509 certifikáty pro různé názvy domén, s kolize hodnoty hash. To znamená, že certifikační autorita by mohl být požádán, aby podepsal osvědčení pro jednu doménu, a pak, že certifikát může být použit k vydávání se za jinou doménu. [ 5 ]
Real-world kolize útok byl zveřejněn v prosinci 2008, kdy skupina bezpečnostních výzkumníků zveřejnila falšované X.509 podpisový certifikát, který by mohl být použit k zosobnění certifikační autority , využívat útoku předpony kolize proti MD5 hash funkce. To znamenalo, že by útočník mohl vydávat se za jinou SSL zabezpečené webové stránky jako man-in-the-middle , čímž podrývání ověření certifikátu postavený v každém webovém prohlížeči na ochranu elektronického obchodu . Rogue osvědčení nemůže být revokable skutečnými orgány, a mohlo by mít také libovolný kované vypršení času. I když byl MD5 známo, že je velmi slabý v roce 2004, [ 1 ] certifikační autority byly ještě ochoten podepsat MD5-ověřené certifikáty v prosinci 2008, [ 6 ] , a alespoň jeden Microsoft code-podpisový certifikát ještě pomocí MD5 v květnu 2012.
Flame malware úspěšně použit nový variantu volený-předpony kolizní útok na spoof podepisování kódu jejích složek ze strany Microsoft Root Certificate, který stále používal kompromitovaný MD5 algoritmus. [ 7 ] [ 8 ]
Mnoho aplikací crytographic hašovacích funkcí se nespoléhají na kolize odpor , tak kolize nemá vliv na jejich bezpečnost. Například, HMACs nejsou náchylné.[ 9 ] Pro útok užitečné, musí být útočník pod kontrolou vstup do hash funkce.
Vzhledem k tomu, digitální podpis algoritmy nemůže podepsat velké množství dat efektivně, většina implementací použít hash funkci pro snížení ("compress") množství dat, která musí být podepsána až do konstantní velikosti. Digitální podpisová schémata jsou často náchylné k hash kolize, pokud pomocí technik, jako je randomizovaných hašování. [ 10 ]
Všimněte si, že všechny certifikáty veřejného klíče , stejně jako SSLcertifikáty, také spoléhají na zabezpečení digitálních podpisů a jsou ohroženy hash kolize.
Obvyklá případě útoku vypadá takto:
Mallory vytváří dva různé dokumenty A a B, které mají stejnou hodnotu hash (kolize).
Mallory pak odešle dokument na Alici , která souhlasí s tím, co píše se v dokumentu, podepíše jej a pošle zpět do Mallory.
Mallory zkopíruje podpis poslal Alice z dokumentu do dokumentu B.
Pak pošle dokument B k Bobovi , prohlašovat, že Alice podepsal jiný dokument. Vzhledem k tomu, že digitální podpis odpovídá dokument hash, Bobův software není schopen detekovat změnu.