Vlastimil Klíma, Tunely v hašovacích funkcích: kolize MD5 do minuty
Abstrakt
V tomto p?ísp?vku uvádíme novou myšlenku tunelování hašovacích funkcí. Tunely umož?ují nahradit sou?asné metody mnohonásobné modifikace zpráv a exponenciáln? zkrátit ?as hledání kolizí. Dále popisujeme n?kolik konkrétních tunel? v hašovací funkci MD5. S jejich využitím zkracujeme ?as hledání kolize hašovací funkce MD5 z p?vodních osmi hodin na minutu na b?žném notebooku (Intel Pentium, 1.6 GHz). Metoda je použitelná pro libovolnou inicializa?ní hodnotu. Tunely mohou být využity k urychlení hledání kolizí i jiných hašovacích funkcí. Metoda byla experimentáln? ov??ena. Pro demonstraci útoku je p?ipojen zdrojový kód programu.
A n?co osobního
Touhle zprávou snad už s MD5 skon?ím. Stala se tém?? neuv??itelná v?c. V sobotu odpoledne jsem práv? kon?il p?eklad svojí tunelovací metody. Nahrazuje a urychluje mojí p?vodní metodu mnohonásobné modifikace zpráv, kterou jsem objevil p?ed rokem. Když tu p?išel mail, že Marc Stevens ud?lal totéž. No není to tak úpln? totéž :-), ale uznejte, že to je p?kná kolize! Asi nejzajímav?jší je srovnání obou metod. Stru?n? ?e?eno Marc vychází z mojí metody mnohonásobné modifikace zpráv. Tunelování vícemén? za?íná tam, kde možnosti metody mnohonásobné modifikace zpráv kon?í.
Zvláštní upozorn?ní k programu: jsem špatný programátor, m?j program je pouze ilustrativní (je hrozný). Nikoli díky programování, ale díky metod? tunel?, je dvakrát rychlejší než Marc?v (mám minimáln? stejné nebo lepší ?asy na dvakrát pomalejším stroji). Marc?v je také ?ádov? pomalejší pro jiné inicializa?ní vektory (pr?m?rn? to trvá cca 6 minut - tady se práv? projevuje rozdíl tunel? a metody mnohonásobných modifikací), ale to nic neubírá na jeho p?kném výsledku.
U MD5 jsem tunely musel pomalu ru?n? dolovat. Bylo tomu tak proto, že staré diferen?ní schéma Wangové, na kterém je to postaveno, s žádnými tunely pochopiteln? nepo?ítalo. Trik je v tom, že pravd?podobn? p?jde navrhnout jiné diferen?ní schéma, kde budou tunely jak hrom. Návrh jiných diferen?ních schémat není problém, problém je skloubení s tunelem. I když to není triviální, mohlo by to jít i u MD5, SHA-1 a SHA-2. V tom jsou tunely perspektivní kryptoanalytickou metodou.
Sou?asn? s kryptoanalýzou je vyvíjena národní i mezinárodní aktivita na získání bezpe?ných hašovacích funkcí. Je pot?eba vyvinout zcela nový koncept hašovacích funkcí, na ?emž také usilovn? pracuji, a z ?ehož je vlastn? tahle práce vedlejší výsledek.
Poznamenávám, že ?ást práce na kolizích pro MD5 vznikla v rámci výzkumného projektu pro Národní bezpe?nostní ú?ad, kterému tímto d?kuji za podporu.
Domácí stránka projektu
je zde.
