MD5 prolomena

1. Úvod

Nejprve se budeme věnovat hašovací funkci MD5 [Ri92]. Na rump session konference CRYPTO 2004 v srpnu roku 2004 Wangová a kol. předložila kolidující zprávy, ale nepublikovala metodu [WFLY04]. V říjnu 2004 Hawkes a kol. [HPR04] analyzovali publikovaná data a popsali jejich vlastnosti. V březnu 2005 Klíma [Kli05a, b] metodu generování kolizí odhalil a prezentoval výsledky svého programu. Jeho metoda byla odlišná a několikrát rychlejší než původní metoda Wangové a kol., která byla publikována později [WaYu05]. Nalezení kolize trvalo v průměru osm hodin na běžném notebooku. V [WaYu05] byly také publikovány tzv. postačující podmínky, jejichž splnění zaručuje kolizi pro danou diferenční cestu. Ukázalo se, že tyto podmínky nejsou postačující a nejsou správné. Jejich částečnou opravu na základě testů v srpnu 2005 navrhli Yajima a Shimoyama [YaSh05]. V listopadu 2005 Sasaki a kol. [SNKO05] také opravili některé postačující podmínky a zavedli nové cesty mnohonásobné modifikace zpráv. Tím urychlili útok Klímy [Kli05b] zhruba osmkrát. V listopadu 2005 Liang a Lai [LiLa05] ukázali protipříklady na postačující podmínky Wangové a kol. z Eurocrypt 2005 [WaYu05]. Předložili úplnou sadu nových postačujících podmínek, která je pravděpodobně správná a konečná. (Poznamenejme, že v našem programu používáme právě tuto sadu.) Dále navrhli další cesty mnohonásobné modifikace zpráv a dosáhli času generování kolizí zhruba čtyř hodin na běžném PC. Wangová a kol. budou v dubnu 2006 prezentovat novou sadu postačujících podmínek. Problém postačujících podmínek je v tom, že musí být velmi přesně provedeno velké množství poměrně jednoduchých výpočtů a úvah. Pokud však tyto výpočty nejsou provedeny strojově, člověk v nich téměř určitě udělá chybu. Strojové zpracování zatím zřejmě narazilo na nějaké problémy a v současné době není k dispozici písemný příspěvek, který by byl připraven k nezávislé verifikaci. Mnoho týmů, které se chtěly věnovat problému kolizí MD5, skončilo svoji práci právě na tom, že neměli k dispozici pevnou oporu v postačujících podmínkách.

MD5

Současné práce, týkající se kolizí hašovací funkce MD5, zejména práce Liang -Lai [LiLa05] a Sasaki a kol. [SNKO05] nás stimulovaly k revizi našeho původního programu [Kli05b]. Nejprve jsme urychlili hledání kolizí v druhém bloku pomocí metod mnohonásobné modifikace zpráv z [YaSh05] [SNKO05] [LiLa05] [Kli05b] a udělali jsme některá drobné změny. Při urychlování metody v prvním bloku jsme zjistili určitou omezenost metod mnohonásobné modifikace zpráv a přišli jsme s myšlenkou tunelů.

Metody mnohonásobné modifikace zpráv vedou k naplňování množiny postačujících podmínek od začátku zprávy až do dosažení bodu, za nímž nejsme schopni nic změnit. Tento bod nazýváme bod verifikace (POV, a point of verification). U MD5 ho můžeme vidět na obrázku 1 - je to bod Q[24].

Těchto bodů je nutné získat velké množství, protože splnění všech postačujících podmínek za tímto bodem nejsme schopni ovlivnit. Jsou splněny náhodně. U MD5 je to 29 postačujících podmínek, a proto je potřeba vygenerovat 229 bodů POV. Jeden z nich pak bude náhodně splňovat i zbývající postačující podmínky, a tudíž bude použit ke kolizi. Metody mnohonásobné modifikace zpráv modifikují zprávu tak, aby se naplnily úvodní postačující podmínky a získali jsme bod POV.

Metoda tunelování začíná naopak v bodu POV. Několika tunely z něj geometrickou řadou postupně vytvoří dostatečné množství dalších POV, aniž by narušila počáteční podmínky před body POV. V ideálním případě potřebujeme pouze jeden bod POV. S použitím tunelu "o síle" n z něj vytvoříme 2n bodů POV. Popíšeme tunely různého typu. Tunely se dají kombinovat, takže z původního bodu POV lze jedním tunelem o síle n1 vytvořit 2n1 bodů POV a z každého z nich tunelem o síle 2n2 získat dalších 2n2 bodů, celkem 2n1+n2 bodů POV. U MD5 ukážeme několik tunelů, které spojením dávají tunel o síle 24. To znamená, že každý originální POV jsme schopni rozmnožit na 224 nových POV. U MD5 to znamená, že postačí vygenerovat pouze 25 = 32 originálních POV oproti 229 bodům u současné nejúspěšnější metody mnohonásobné modifikace zpráv. Tunelování umožňuje tímto způsobem urychlit hledání kolizí a do značné míry nahradit současné metody mnohonásobné modifikace zpráv.

Tunelování MD5 urychlilo hledání kolizí na autorově notebooku zhruba pětsetkrát oproti [Kli05a] a trvá v průměru zhruba jednu minutu. K demonstraci popíšeme několik tunelů v hašovací funkci MD5.

Bude vidět, že hledání tunelů v MD5 je poměrně obtížné, neboť jim vadí postačující podmínky v daném diferenčním schématu. Stačí si však uvědomit, že při stanovování počátečních podmínek máme značnou volnost, neboť diferenčních schémat je velmi mnoho. Diferenční schéma pro rychlý útok budeme vytvářet tak, aby v sobě obsahovalo buď jeden masivní tunel nebo více úzkých tunelů. Otevírá se tak nová možnost pro kryptoanalýzu hašovacích funkcí. Autor je přesvědčen, že se naleznou cesty, jak pro MD5, SHA-0, SHA-1, SHA-2 konstruovat diferenční schémata tak, aby v nich apriori existovaly využitelné tunely. To je směr, který může být velmi perspektivní, i když to není triviální úloha. Nyní se budeme věnovat hašovací funkci MD5.

2. Popis

V popisu budeme využívat proměnné, které jsou použity v programu. Protože v programu nelze použít symboly s hvězdičkou, předřazujeme jim písmeno H, tj. Q* bude nyní HQ (H je první písmeno slova "hvězdička" v českém jazyce, proměnné začínající H jsou tedy proměnné s hvězdičkou).

Připomeňme základní postup hledání kolizí z [WaYu05]. Kolidující zprávy se skládají ze dvou 512 bitových bloků (M, N) a (HM, HN), přičemž MD5(M, N) = MD5(HM, HN). První bloky zpráv (M, HM) se liší o předem definovaný konstantní vektor C1 (HM = M + C1) a druhé bloky (N, HN) se liší o předem definovaný konstantní vektor C2 (HN = N + C2).

Jestliže jsou splněny postačující podmínky při zpracování bloku M, výsledek po hašování bloku M a výsledek po hašování bloku HM se také liší o předem definovanou konstantu C3. Při pokračování hašováním druhých bloků se (jsou-li splněny postačující podmínky pro druhý blok N) rozdíl C3 postupem času zruší a obdržíme kolizi zpráv (M, N) a (HM, HN).

Postup zpracování bloků je podobný u obou bloků, popíšeme postup u prvního bloku (M). Blok M má 512 bitů, které jsou zpracovávány po 32bitových slovech M = (x[0], ..., x[15]) v 64 krocích. V prvním kroku vzniká meziproměnná Q[1], v druhém kroku Q[2] atd. až Q[64]. Proměnné Q[-3] (= IV[0] = 0x67452301), Q[-2] (= IV[3] = 0x10325476), Q[-1] (= IV[2] = 0x98badcfe) a Q[0] (= IV[1] = 0xefcdab89) jsou inicializační hodnotou, buď standardní nebo zvolenou. Po 64 krocích je na výsledek Q[61...64] (poslední čtyři proměnné) přičtena vstupní hodnota (IV[0..3]) a dostáváme výsledek zpracování prvního bloku IHV[0...3] (intermediate hash value). IHV pak vstupuje do druhého bloku stejně jako IV do prvního bloku a postup se opakuje.

Postačující podmínky v prvním bloku jsou podmínky na jednotlivé bity proměnných IHV[0...3] a Q[1...64], které vznikají při zpracování slov zprávy x[0...15] nelineárními funkcemi F, G, H, I. Postačující podmínky říkají, že některé bity zmíněných proměnných musí být stejné, některé různé, některé nuly a některé jedničky, zbývající bity mohou být libovolné, viz obrázek 2.

Postačující podmínky se liší v prvním a druhém bloku. V prvním bloku je jich více, neboť se týkají jak Q, tak IHV. V druhém bloku je podmínek méně. Budeme se věnovat prvnímu bloku, neboť je složitější. Postup u druhého bloku je podobný. Máme blok M = (x[0],..., x[15]) a blok HM = (Hx[0],...,Hx[15]), který se od M liší o konstantní vektor C1 = (0,...0, 0x80000000, 0,...,0, 0x00008000, 0,...,0), tj.

Hx[ 4] = x[ 4] + 0x80000000,
Hx[11] = x[11] + 0x0000800,
Hx[14] = x[14] + 0x80000000.

Nevýhoda postačujících podmínek je v tom, že je jich velmi mnoho a že zasahují příliš daleko do proměnných Q. Pokud naplníme podmínky Q[1] až Q[16] tím, že tyto hodnoty zvolíme, nemáme již žádnou volnost ve volbě zprávy x[0...15] a tudíž hodnoty Q[17..64] a IHV[0..3] jsou plně určeny. Podmínky na ně jsou splněny pouze náhodně. Pokud hodnoty Q[1] až Q[16] nestanovíme zcela, budou se nám špatně počítat hodnoty Q[17..64] a IHV[0..3], které na nich nelineárně a složitě závisí.

Metoda mnohonásobné modifikace zpráv [Kli05b] [WaYu05] [YaSh05] [SNKO05] [LiLa05] spočívala v tom, že se zvolila náhodně zpráva x[] a její modifikací se krok za krokem naplňovaly podmínky na Q[1, 2,...64]. Tento proces v různých pracích zprvu končil u Q[18], potom u Q[19] atd. V současné době je možné se nejdále dostat ke splnění podmínky na Q[24] ([SNKO05], poznamenejme však, že metoda nebyla ověřena experimentálně). Další podmínky jsou příliš daleko - až na Q[35]. V uvedených pracích se navrhovaly různé způsoby modifikace zpráv. Aby tento proces byl efektivnější, byly zavedeny další podmínky, které se nazývají "extra podmínky". Tyto podmínky jsou podobné jako postačující podmínky, ale nejsou nezbytné pro naplnění dané diferenční cesty. Umožňují však rychleji realizovat některou konkrétní metodu mnohonásobné modifikace zpráv. V praxi jde zhruba o deset až dvacet podmínek na jednotlivé bity proměnných Q[1...24]. Postačujících podmínek je zhruba 250.

Úspěšnost metod mnohonásobné modifikace zpráv v každém případě končila splněním podmínky na Q[24]. Proměnné x[] byly plně určeny a bývalo už jen ověřit, zda zbývající podmínky na Q[25...64] a IHV[0...3] jsou splněny náhodně. V případě, že nebyly splněny, metoda pokračovala dalším generováním zprávy x a její modifikací krok za krokem až do splnění podmínek Q[24]. Tento bod nazýváme bodem verifikace POV, neboť v tomto bodě nic jiného nezbývalo než pouze verifikovat, zda i ostatní podmínky na Q[25...64] a IHV[0...3] jsou splněny. Protože konkrétně u MD5 je těchto zbývajících podmínek 29, složitost metody mnohonásobné modifikace zpráv spočívala v nalezení 229 bodů POV.

Metoda tunelování spočívá v ideálním případě v nalezení pouze jednoho bodu POV. Pomocí tunelů se pak tento bod rozmnoží na potřebný počet. Jeden bod POV je v tomto případě možné udělat jakkoli i zcela náhodně s minimální složitostí. V ideálním případě tak zcela odpadá fáze přípravy bodů POV a dále v diferenčním schématu (diferenční cesta plus postačující podmínky) je možné ponechat pouze postačující podmínky a odstranit přebytečné extra podmínky.

3. Popis konkrétních tunelů v MD5

3.1. Tunel Q9, extra podmínky

Pro ty bity i, kde Q[10]i = 0 a současně Q[11]i = 1 máme tunel podle následujícího obrázku.

Na všech těchto bitech i můžeme změnit hodnotu Q[9]i, přičemž tato změna se neprojeví v rovnicích pro Q[11] a Q[10]. Projeví se v rovnicích pro Q[9], Q[10] a Q[13]. Tyto změny však kompenzujeme změnou hodnot zprávy, tj. x[8], x[9] a x[12], zatímco Q[10], Q[11], Q[12] a Q[13] zůstávají nezměněny. Na dalším obrázku vidíme, co znamenají změny hodnot x[8], x[9] a x[12] pro následující proměnné Q[14] až Q[64].

Vidíme, že změny se projeví až za bodem verifikace, takže všechny podmínky před ním zůstávají splněny. Změní se všechny proměnné Q[25] až Q[64], a to dosti složitým a náhodným způsobem (experimentálně ověřeno).

Abychom získali co nejsilnější tunel, máme zájem na nastavení co nejvíce dvojic bitů Q[10]i = 0 a současně Q[11]i = 1. Tyto podmínky nejsou součástí postačujících podmínek, pouze urychlují hledání kolizí. Nazýváme je stejně jako u metody mnohonásobné modifikace zpráv extra podmínky. Bohužel počáteční podmínky v současném diferenčním schématu umožňují jen volbu třech těchto pozic (i = 22, 23, 24), ostatní nejsou volné. Tím získáváme tunel o síle 3.

3.2. Tunel Q4, deterministické a pravděpodobnostní tunely

Pro ty bity i, kde Q[6]i = 1 a současně Q[5]i = 0 máme tunel podle následujícího obrázku.

Na bitech i můžeme tedy změnit hodnotu Q[4]i, přičemž tato změna se neprojeví v rovnicích pro Q[6] a Q[7]. Projeví se v rovnicích pro Q[4], Q[5] a Q[8]. Tyto změny kompenzujeme změnou hodnot zprávy x[3], x[4] a x[7], zatímco Q[5...8] zůstávají nezměněny. Na dalším obrázku vidíme, co znamenají změny hodnot x[3], x[4] a x[7] pro proměnné Q[9] až Q[64].

V tomto případě nám změny zasahují do proměnné Q[24], kde mohou narušit již splněnou počáteční podmínku (je to podmínka na bit 32). Pokud budeme měnit Q[4] v bitu i, pak se to dotkne x[4]i-7 a s velkou pravděpodobností i bitu x[4]i a dále dalších bitů prostřednictvím případných aritmetických přenosů (carry). Tyto přenosy jsou pravděpodobnostní s rychle klesající pravděpodobností. Bity x[4]i,i-7 mají pak vliv na bity Q[24]i+20,i+13, a na další opět prostřednictvím carry. Pokud volíme i ≠ 12, 19 a eventuelně vyloučíme i okolní bity, nebude mít změna bitu Q[4]i přímý vliv na Q[24]32 (pouze prostřednictvím carry).

Tento tunel jsme uvedli jako příklad tunelu pravděpodobnostního. Z jednoho bodu POV nemusí tunel stoprocentně (deterministicky) vést do dalších bodů POV, ale s příslušnou pravděpodobností. Tyto tunely nazýváme pravděpodobnostní. Některé tunely mohou mít pravděpodobnost nižší, například poloviční nebo čtvrtinovou. U nich vzniká otázka, zda se je vyplatí. Ve většině případů ano, ale přesnější odpověď dá analýza složitosti v konkrétní situaci. Není potřeba se bát je používat, protože to, zda získáme nový bod nebo ne, lze jednoduše ověřit pouze jednou přídavnou kontrolou splnění potenciálně ohrožené počáteční podmínky. V případě MD5 jsme tento tunel použili jako velmi úzký, protože počáteční podmínky ponechávají volný pouze bit i = 26. Tento bit ovlivňuje Q[24]32 s velmi malou pravděpodobností, takže tento konkrétní tunel má sílu téměř 1. Tunely stoprocentní nazýváme deterministické.

3.3. Tunel Q14, dynamické tunely

Tento tunel je příkladem dynamického tunelu. Postup upravujeme podle toho, jaké konkrétní hodnoty mají příslušné proměnné. Pokud bychom tyto proměnné nastavili na extra hodnoty, dostali bychom klasický stacionární tunel. Idea tohoto tunelu je využití zbytku volnosti bitů Q[3], Q[4] a induktivně i Q[14]. Vysvětlíme ho na základě změn Q[3], Q[4], i když to lze i na základě změn Q[14]. Proměnné, které se mění, jsou na následujícím obrázku tučně a proměnné, které se nesmí měnit, jsou zvýrazněny.

Cílem je najít co nejvíce bitových pozic (i) tak, abychom mohli měnit bity Q[3]i a/nebo Q[4]i tak, aby se v rovnici pro Q[6] neměnilo x[5]. To znamená, že se nesmí měnit výraz F(Q[ 5],Q[ 4],Q[ 3]). To, který bit Q[3]i nebo Q[4]i v něm změníme, rozhodujeme dynamicky podle konkrétní hodnoty Q[5]i. Kdybychom změnili oba bity současně, hodnota F by se vždy změnila. Z kandidátů na indexy (i) proto vypadávají ty pozice, kde máme postačující podmínky Q[3]i = Q[4]i (je jich poměrně hodně, viz obrázek). Zbývá dolních 6 bitů a horních 9 bitů.

Změny Q[3,4] ve zbývajících rovnicích pro Q[3, 4, 5, 7, 8] kompenzujeme změnami x[2, 3, 4, 6, 7]. Změna x[4] nám tolik nevadí, jak jsme viděli u tunelu Q4, neboť bit Q[24]32 změní většinou jen s malou pravděpodobností. Změnu v Q[18] si nemůžeme dovolit, proto změnu x[6] kompenzujeme odpovídající změnou Q[14]. Aby změna Q[14] neovlivnila rovnice Q[16, 17] nastavíme na bitech, kde se Q[14]i mění, extra podmínky Q[15]i = 0 a Q[16]i = 0. Jsou to horní bity 29, 28, 27 a dolní bity 7, 6, 5, 3, 2, 1. Pak se změna Q[14]i ve funkcích F(Q[15],Q[14],Q[13]) a G(Q[16],Q[15],Q[14]) neprojeví.
Změnu lze studovat dobře tak, pokud proměnnou x[6] z rovnic eliminujeme jak ukazuje obrázek.

Z tohoto vztahu je dobře vidět, jak změny Q[14] kompenzovat pomocí změn Q[3]/[4] tak, aby výraz F(Q[ 6],Q[ 5],Q[ 4]) + Q[ 3] - Q[14] zůstal nezměněn. Ukazuje se, že u Q[14] lze měnit bity 29, 28, 27, 7, 6, 5, 3, 2, 1. Změny lze kompenzovat změnami volných bitů Q[3]/Q[4], a to s pravděpodobností cca 1/2, neboť na šest bitů změny Q[14] v dolních bitech (7, 6, 5, 3, 2, 1) máme k dispozici jen pět volných bitů Q[3]/Q[4] (na bitech 6, 4, 3, 2, 1). Naproti tomu změnu horních třech bitů Q[14] (29, 28, 27) můžeme stoprocentně kompenzovat změnou šesti volných bitů Q[3]/Q[4] (27 až 32). Deterministický tunel, tvořený horními bity Q[14] má sílu 3. Pravděpodobnostní tunel, tvořený dolními šesti bity Q[14] má sílu cca 5. Další pravděpodobnostní tunely v MD5 si popíšeme už jen stručně 12.

3.4. Tunel Q10

Nastavíme extra podmínky Q[11]i = 0 pro i = 11, 25, 27. Můžeme měnit Q[10]i, přičemž v rovnici pro Q[12] se tato změna neprojeví. Změny v rovnici pro Q[11] jsou minimalizovány protože na bitech i= 11, 25, 27 platí Q[8]i = Q[9]i, a tudíž se F(Q[10],Q[ 9],Q[ 8]) při změně Q nemění. Změny ukazuje obrázek. Změna x[10] pravděpodobnostně může narušit podmínky Q[22-24], ale poměrně s malou pravděpodobností. Tunel má tři volné bity, ale sílu cca 2.

3.5. Tunel Q13

Tento tunel využívá volných bitů v Q[13] a toho, že na Q[2] nejsou kladeny žádné podmínky, viz obrázek. Změny Q[13]i vedou na změny x[1-5, 15] a x[15]. Vhodnou volbou indexů i lze změny Q[21-24] usměrnit. Tunel mění 12 bitů Q[13] (i = 2, 3, 5, 7, 10-12, 21-23, 28-29), přičemž úspěšných pokusů, vedoucích k POV, je zhruba jedna třetina. Síla tunelu je více než 10.

3.6. Tunel Q20

Tento tunel využívá volných bitů v Q[20] a toho, že na Q[1] a Q[2] nejsou kladeny žádné podmínky. Tím lze vyblokovat změnu x[1]. Je znázorněn na obrázku. Změny Q[20]i vedou na změny x[0] a x[2-5]. Vhodnou volbou indexů i lze tyto změny na Q[20-24] usměrnit. Tunel mění 6 bitů Q[20] (i = 1, 2, 10, 15, 22, 24), přičemž úspěšných pokusů, vedoucích k POV, je zhruba jedna sedmina. Síla tunelu je více než 3.

4. Aplikace tunelů na další hašovací funkce

Myšlenka tunelů je použitelná obecně i pro jiné hašovací funkce. Musí být pochopitelně nalezeny odpovídající konkrétní tunely.

Tunely, které jsme popsali v MD5, jsou příliš umělé, protože dané diferenční schéma [WFLY04] nebylo pro tento účel vytvořeno.

Stačí si uvědomit, jaký význam mají tunely pro hledání kolizí a je jasné, že se vyplatí změnit diferenční schéma tak, aby už v sobě možnost tunelů zahrnovalo. Rozhodně to ale není triviální úloha.

Předpokládáme, že se objeví diferenční schémata, nejen pro MD5, ale i pro SHA-1 a SHA-2, která v sobě již budou zahrnovat připravené tunely. Ukázali jsme příklady tunelů úzkých i širokých, deterministických i pravděpodobnostních, dynamických a stacionárních. Všechny tyto typy mohou být užitečné v budoucích diferenčních schématech.

Velmi zajímavé by mohlo být použití tunelů tam, kde neznáme počáteční podmínky nebo by bylo složité je odvozovat! Postačí náhodně získat bod POV a použít tunel třeba uprostřed schématu. To by mohlo být východisko pro složitá schémata. Je to pochopitelně jen idea.

Poslední poznámka je obecná. Tunely jsou velmi nenápadně skryty ve schématu, které je na první pohled homogenní a bez zadních vrátek. Ukazují, že v návrhu kryptografických schémat mohou být některé slabiny velmi dobře skryty.

5. Experimentální výsledky

Na domácí stránce projektu naleznete zdrojový kód programu. Program byl napsán pro experimentální ověření metody tunelů a k získání časových odhadů. Byl testován na mírně podprůměrném notebooku (Acer TravelMate 450LMi, Intel Pentium 1.6 GHz). Při experimentu bylo za 9 a půl hodiny získáno 381 kolizí. Průměrná doba kolize je 89 vteřin, přičemž 66 vteřin trvá nalezení kolize prvního bloku a 23 vteřin kolize druhého bloku. Když jsme odstranili některé zbytečné instrukce, dostali jsme průměrný čas 81 vteřin (281 kolizí). V druhém bloku nebyly použity tunely, postačila metoda mnohonásobné modifikace. Program nebyl optimalizován ani v prvním bloku ani v druhém bloku, takže jeho další verze mohou časy hledání kolizí mírně urychlit, odhadujeme zhruba na polovinu. Další urychlení může přinést aplikace tunelů v druhém bloku apod.

6. Závěr

V příspěvku jsme popsali novou metodu "tunelování" pro hledání kolizí hašovací funkce MD5. Tato metoda urychluje hledání kolizí exponenciálně. Její programová realizace na obyčejném notebooku umožňuje najít kolizi MD5 řádově během minuty, což je cca 500 krát méně, než předchozí výsledek [Kli05b]. Současně (pokud víme) je to nejrychlejší metoda hledání kolizí MD5 vůbec. Metoda je obecná a je otázkou dalšího výzkumu, jak ji využít u dalších hašovacích funkcí. V příspěvku poukazujeme na některé její možnosti pro hledání kolizí u dalších hašovacích funkcí.

Poděkování

Domácí stránka projektu

7. Literatura

[Ri92] Ronald Rivest: The MD5 Message Digest Algorithm, RFC1321, April 1992, ftp://ftp.rfc-editor.org/in-notes/rfc1321.txt

[WFLY04] Xiaoyun Wang, Dengguo Feng , Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, first version (August 16, 2004), second version (August 17, 2004), http://eprint.iacr.org/2004/199.pdf

[HPR04] Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. MD5 Collision, Cryptology ePrint Archive, Report 2004/264, 13 October 2004, http://eprint.iacr.org/2004/264.pdf

[Kli05a] Vlastimil Klima: Finding MD5 Collisions – a Toy For a Notebook, Cryptology ePrint Archive, Report 2005/075, http://eprint.iacr.org/2005/075.pdf, March 5, 2005

[Kli05b] Vlastimil Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, Cryptology ePrint Archive, 5 April 2005. http://eprint.iacr.org/2005/102.pdf

[WaYu05] X. Wang and H. Yu: How to Break MD5 and Other Hash Functions., Eurocrypt’05, Springer-Verlag, LNCS, Vol. 3494, pp. 19–35. Springer, 2005. [YaSh05] Jun Yajima and Takeshi Shimoyama: Wang’s sufficient conditions of MD5 are not sufficient, Cryptology ePrint Archive: Report 2005/263, 10 Aug 2005, http://eprint.iacr.org/2005/263.pdf

[SNKO05] Yu Sasaki and Yusuke Naito and Noboru Kunihiro and Kazuo Ohta: Improved Collision Attack on MD5, Cryptology ePrint Archive: Report 2005/400, 7 Nov 2005, http://eprint.iacr.org/2005/400.pdf

[LiLa05] Liang J. and Lai X.: Improved Collision Attack on Hash Function MD5, Cryptology ePrint Archive: Report 425/2005, 23 Nov 2005, http://eprint.iacr.org/2005/425.pdf.

Vlastimil Klíma
http://cryptography.hyperlink.cz
v.klima(at)volny.cz

Zdrojové kódy