Praktické útoky na digitální podpisy používající hašovací funkci MD5

V oblasti hašovacích funkcí je od srpna t.r. neustále živo. Článek Hašovací funkce MD5 a další prolomeny! přinesl výsledky čínského útoku a ohromný zájem o toto téma (přes 10 000 čtenářů rootu). Stejné téma jsem 22. 11. referoval také na nově vzniklém semináři Bezpečnost Informačních Systémů v praxi na MFF UK, kde určitě najdete i jiná zajímavá témata. Pár dní před ním byla publikována další závažná práce (Kelsey-Schneier) ukazující možnosti konstrukce multikolizí, tj. mnoha zpráv vedoucích na tutéž haš (může jich být nalezeno skutečně neuvěřitelně mnoho). Hlavní výsledky a linky jsem uvedl v závěru přednáškyUkázal jsem tam možnosti a vyzval ke konstrukci praktického příkladu využití kolizí. Během diskuse byly ihned předloženy asi čtyři nápady. Ondra svůj nápad během následujících dní popsal v článku a naprogramoval fungující praktickou ukázku, k níž vše potřebné naleznete na stránce tohoto projektu.

Ondrův článek bude v nejbližších dnech publikován také na webu ePrintu IACR a obsahuje více myšlenek. Zde uvedeme hlavní ideu využití oné jediné kolize MD5, která je k dispozici. Zvolme si libovolné soubory X a Y. Uživateli 1 zašleme soubory data.pak a self-extract.exe, uživateli 2 zašleme soubory data.pak a self-extract.exe. Soubory self-extract.exe jsou stejné, zatímco data.pak různé, ale mají stejnou MD5 haš. Oba uživatelé nyní mohou zkontrolovat haše obdržených souborů nebo jejich digitální podpisy proti sobě. Protože budou totožné, očekávají, že i soubory, které z nich extrahují po spuštění self-extraktoru, budou totožné. Avšak jeden extrahuje X, zatímco druhý Y.

Příspěvek obsahuje konkrétní příklad dvou různých smluv X a Y i postup jak si pomocí příslušných programůvytvořit dvojice self-extract.exe a data.pak pro vlastní soubory X a Y.

Pointa je v tom, že jeden kolidující řetězec MD5 je umístěn na začátku jednoho souboru data.pak a druhý na začátku druhého. Oba dva soubory data.pak obsahují data obou souborů X a Y. Extraktor rozhoduje, která z dat se extrahují podle jednoho bitu souboru data.pak – toho bitu, kde se kolidující řetězce MD5 liší.

Určitou nevýhodou je, že se uživatelům neodesílá jen jeden soubor. Jakmile však bude zveřejněn postup, jak získávat kolize pro libovolnou inicializační hodnotu MD5, je v příspěvku uveden postup, jak uživatelům distribuovat pouze soubor self-extract.exe. I když budou mít stejnou haš, budou extrahovat jiné soubory. Mohou ovšem extrahovat i více souborů a také se nemusí jednat o samorozbalovací archiv. Stejně tak dobře lze vytvořit kolize jiných spustitelných souborů se zcela jinou činností (!). Postup je také možné použít pro libovolnou platformu, která má nějaký druh binárního spustitelného formátu.

Ve světě Linuxu, na rozdíl od Windows, nejsou samorozbalovací (samoinstalovací) archivy tak běžné a používají se hlavně tar.gz, tar.bz2, zip a různe balíčky (rpm, deb atd.). Důležité je, že všechny jsou v podstatě v binárním formátu a instalační skript (configure, Makefile, instalační scriptlet z rpm atd.) může právě užít stejného triku jako u samorozbalovacích archivů.

U archivů zip, tar.gz a tar.bz2 nastávají dvě potíže, za prvé, jak dostat kolidující blok dovnitř nezkomprimován, a za druhé, jak zařídit současnou kolizi u MD5 a CRC32, neboť tyto formáty používají CRC32 na test integrity kvůli detekci chyb. První problém se řeší technicky, neboť všechny formáty to umožňují, druhý problém se řeší kryptograficky. Využijeme narozeninového paradoxu: jestli máme 2³² možných hodnot (CRC32) a každá z nich je stejně pravděpodobná, pak při náhodném výběru 2^(32/2) hodnot máme 50% pravděpodobnost, že dvě hodnoty budou stejné. To znamená, že potřebujeme 2¹⁶ bloků se stejnou haší MD5. Nebudeme však počítat všech 2¹⁶ kolizí, ale doporučil jsem najít pouze 16 kolizí a použít Jouxův trik s multikolizemi (viz prezentaci, abychom obdrželi 2¹⁶ kolidujících bloků. V nich pak nalezneme dvojici bloků, které mají jak stejnou haš, tak CRC32.

Generování 16 kolizí by trvalo odhadem 161 hodinu na ibm p690 = cca 1620=320 hodin na lepším PC, při distribuovaném řešení se to dá stihnout za jeden den na 16 počítačích.

Podrobnosti a dále, jak uvedené potíže obejít u rpm a deb balíčků, popisuje Ondra na stránce projektu. Není bez zajímavosti, že právě v těchto dnech se objevil nezávisle také další příspěvek na toto téma využití nalezené kolize MD5 (Ondra ten svůj poslal na web ePrint o několik dní dříve, což bude tamtéž také potvrzeno).