Collision_attack (Kolize útok)

V kryptografii, kolize útok na kryptografický hash se snaží najít dva libovolné vstupy, které budou produkovat stejný hash hodnotu, tj. hash kolize . Na rozdíl od preimage útoku , ani hash hodnotu, ani jeden ze vstupů je specifikována.

Existují zhruba dva typy kolize:

• Kolize útok: nalézt dva libovolné různé zprávy m1 a m2, tak, aby hash (M1) = hash (m2) .

• Prefix kolize útok: daný dva různé předpony p1, p2 najdeme dva přídavky m1 a m2, tak, aby hash (p1 ∥ m1) = hash (p2 ∥ m2), (kde ∥ je zřetězení provoz)

Klasická kolize útok

Matematicky řečeno, kolize útok najde dvě různé zprávy, m1 a m2 , tak, aby hash (M1) = hash (m2) . V klasické kolizi útok, útočník nemá kontrolu nad obsahem obou zpráv, ale oni jsou libovolně zvoleného algoritmu.

Stejně jako symetrický klíč-kódy jsou náchylné k útoku hrubou silou , každý kryptografické hashovací funkce je ve své podstatě zranitelná ke kolizím s použitím narozeniny útoku . Vzhledem k narozeninám problém , tyto útoky jsou mnohem rychlejší, než hrubou silou by být. Hash n bitů lze rozdělit na 2 ^{n / 2} času (hodnocení hash funkce).

Účinnější útoky jsou možná tím, že zaměstná dešifrování na konkrétní hash funkce. Pokud existují kolize, které jsou rychlejší než útok narozenin, hashovací funkce je často odsouzen jako "zlomený".Hašovací funkce NIST soutěž byla velmi vyvolané zveřejněna kolize proti dvěma velmi běžně používané hašovací funkce, MD5 ^, a SHA-1 . Kolize proti MD5 se zlepšila natolik, že trvá jen pár vteřin na pravidelné počítači.

Hash kolize vytvořila tímto způsobem jsou obvykle konstantní délky a do značné míry nestrukturovaný, takže ne přímo být použita k útoku rozšířené formáty dokumentů nebo protokolů. Nicméně, řešení je možné tím, že zneužila dynamické konstrukty vyskytují v mnoha formátech. Takový dokument by obsahovat škodlivý dvě různé zprávy, ve stejném dokumentu, ale podmíněně zobrazuje jeden nebo druhý, podle toho, která ze dvou srazila hodnoty hash je přítomen:

• Počítačové programy mají podmíněné konstrukce (if-then-else), které umožňují testování, zda umístění v souboru má jednu hodnotu nebo jiný.

• Některé formáty dokumentů jako je PostScript , nebo maker v aplikaci Microsoft Word , mají také podmíněné konstrukty.

• Formátů souborů, které mohou obsahovat obrázky, včetně TIFF a PDF , jsou náchylné k kolize pomocí srazí hash hodnoty jako indexované barvy , tak, že text jedné zprávy je zobrazen s světlé barvy, který se hodí do pozadí, a text jiná zpráva je zobrazen s tmavou barvu.

Vybraná prefix kolize útok

Rozšíření kolize útoku je vybrán prefix kolizi útoku, který je specifický pro Merkle-Damgård hašovací funkce . V tomto případě se útočník může libovolně vybrat dvě různé dokumenty, a pak se připojit různé vypočtených hodnot, které vedou k celé dokumenty, které vykazují stejné hodnoty hash. Tento útok je mnohem silnější než klasické kolizní útok.

Matematicky řečeno, vzhledem dvou různých předpon p1, p2 , napadnout najde dva přídavky m1 a m2, tak, aby hash (p1 ∥ m1) = hash (p2 ∥ m2), (kde ∥ je zřetězení provozu).

V roce 2007, které byly vybrány předpona kolize útok byl nalezen proti MD5, která vyžaduje zhruba 2 ⁵⁰ hodnocení funkce MD5. Papír také demonstruje dva X.509 certifikáty pro různé názvy domén, s srážející se hash hodnoty. 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 by mohly být použity k vydávání se za jinou doménu. 

Snad nejznámější real-svět kolize útok byl zveřejněn v prosinci 2008, kdy skupina bezpečnostních výzkumníků zveřejněné padělané X.509 podpisový certifikát, které by mohly být použity k zahájení tuláka certifikační autoritou , s využitím předpony kolize útok proti MD5 hash funkce. To znamenalo, že by útočník mohl vydávat žádné SSL-zabezpečenou webovou stránku jako man-in-the-middle , rozvracení ověřování certifikátů ve webových prohlížečích. Co je horší, nepoctiví osvědčení by neměla být revokable skutečnými orgány, a mohl by mít libovolný kované vypršení času. I když byl MD5 známo, že je velmi slabý v roce 2004,  certifikačních autorit byly ještě ochotná podepsat MD5-ověřené certifikáty v prosinci 2008. 

Útok scénáře

Mnoho aplikací crytographic hašovací funkce se nespoléhají na kolize odpor , tak kolize nemá vliv na jejich bezpečnost. Například, hašování hesel a HMACs nejsou ohroženy. ^[ 7 ] Pro útok být užitečné, útočník musí být pod kontrolou vstup do hash funkce.

Digitální podpisy

Vzhledem k tomu, digitální podpis algoritmy nemůže podepsat velké množství dat efektivně, většina implementací používá hash funkci pro snížení ("obklad") množství dat, které musí být podepsána až do konstantní velikost. Schémata digitálního podpisu jsou často náchylné k hash kolize, pokud pomocí technik, jako je randomizovaných hašování.