Hlavní navigace

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

Vlastimil Klíma 9. 12. 2004

Student MFF UK Ondrej Mikle ukázal, že lze využít i jedinou publikovanou kolizi MD5 ke konstrukci reálných útoků. Jakékoliv dva různé soubory předáte pomocí určitého postupu dvěma uživatelům, a přitom si oba dva na základě vzájemné kontroly digitálních otisků MD5 budou myslet, že mají tentýž soubor...

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 232 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 216 bloků se stejnou haší MD5. Nebudeme však počítat všech 216 kolizí, ale doporučil jsem najít pouze 16 kolizí a použít Jouxův trik s multikolizemi (viz prezentaci, abychom obdrželi 216 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).

Našli jste v článku chybu?

23. 8. 2013 12:35

Lacik (neregistrovaný)

... a říká se tomu synchronicita. Pozoruhodné.

14. 12. 2004 18:43

Václav Vondra (neregistrovaný)

KOnečně jsem sehnal logo skupiny CZert na:
http://sweb.cz/neknihy


Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Vitalia.cz: Nestlé vyvinula nový typ „netloustnoucího“ cukru

Nestlé vyvinula nový typ „netloustnoucího“ cukru

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Lupa.cz: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Podnikatel.cz: Babiš: E-shopy z EET možná vyjmeme

Babiš: E-shopy z EET možná vyjmeme

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky