Útok nalezením kolize

V kryptografii je kolizní útok (anglicky collision attack) na kryptografické hašovací funkci pokusem o nalezení dvou vstupů produkujících stejnou haš hodnotu, tedy kolizi. Na rozdíl od útoku na jednocestnost (preimage attack) není haš hodnota předem dána.

Existují dva typy kolizních útoků:

Klasický kolizní útok: Nalézá takové dvě rozdílné zprávy m1 a m2, aby platlo hash(m1) = hash(m2).
Kolizní útok se zvoleným prefixem: Jsou dány dva rozdílné prefixy p1 a p2, ke kterým jsou nalézány takové dvě zprávy m1 a m2, aby platilo hash(p1 || m1) = hash(p2 || m2) (kde || je značka pro operaci zřetězení).

Klasický útok

Matematicky řečeno, tento útok nalezne takové dvě rozdílné zprávy m1 a m2, aby platilo hash(m1) = hash(m2). Při klasickém útoku nemá útočník žádnou kontrolu nad obsahem jakékoliv zprávy. Obsah zpráv je náhodně vybírán algoritmem.

Stejně jako jsou symetrické šifry napadnutelné útokem hrubou silou, jsou i kryptografické hašovací funkce ze své podstaty napadnutelné narozeninovým útokem. Díky narozeninovému problému jsou tyto útoky mnohem rychlejší nežli útok hrubou silou. Haš hodnota o velikosti n bitů může být prolomena za 2^n/2 pokusů (vyhodnocení hašovací funkce).

Útok je možné zefektivnit aplikací kryptoanalýzy na konkrétní hašovací funkci. Pokud je objeven kolizní útok rychlejší než narozeninový útok, je hašovací funkce často označena za "prolomenou"'. Zveřejnění kolizních útoku na běžně používané hash funkce MD5 a SHA-1 vedlo k vyhlášení soutěže NIST hash function compeptition. Kolizní útok na MD5 byl vylepšen do té míry, že na běžném počítači trvalo prolomení jen několik sekund. Takto vytvořené kolizní haš klíče jsou obvykle konstantní délky a do značné míry nestrukturované, takže je nelze přímo použít k rozsáhlejšímu útoku na formáty dokumentů nebo protokoly.

Nicméně jisté řešení umožňují dynamické konstrukce přítomné v mnoha formátech. Tímto způsobem mohou být vytvořeny dva velmi podobné dokumenty se stejnou haš hodnotou. Jeden z dokumentů je podepsán autoritou a tento podpis je zkopírován na druhý dokument. Takto podvržený dokument může obsahovat dvě různé zprávy a zobrazit jednu nebo druhou v závislosti na drobných změnách v souboru:

Některé formáty dokumentů jako například PostScript, nebo makra v Microsoft Word, mají podmínkové konstrukce (if-then-else). Podmínka otestuje, zda je někde v dokumentu ta nebo ona hodnota, a tím je možné řídit, co se v dokumentu zobrazí.
TIFF soubory mohou zobrazovat různou část oříznutého obrázku bez změny haš hodnoty souboru
PDF soubory mohou být napadnuty kolizním útokem tak, že se změnou barvy textu změní obsah dokumentu. (text jedné zprávy je zobrazen bíle, tak aby splynul s bílým pozadím, a druhá zpráva je zobrazena tmavou barvou)

Reference

V tomto článku byl použit překlad textu z článku Collision attack na anglické Wikipedii.