Obsahuje:
  • všechny e-ziny od 9/1999
  • celou databázi NEWS
  • soutěže 2000-2011
  • další články a BONUSY

Crypto - News

http://crypto-world.info

Crypto - News | Security - News

08 / 2005
Vybrali pro vás: TR - Tomáš Rosa, JP - Jaroslav Pinkava, PV - Pavel Vondruška, VK - Vlastimil Klíma

Japonci jsou třetím týmem na světě, který umí generovat kolize MD5

11.08.2005
Jun Yajima a Takeshi Shimoyama představili 10. srpna opravenou verzi postačujících podmínek Wangové, což jim umožňuje generovat kolize MD5 s nově dosaženou jistotou.

O algoritmus hledání kolizí se po čínském týmu prof. Wangové (srpen 2004) a po publikaci mého algoritmu (březen 2005) pokoušelo několik týmů. Jedním z nich je i český diplomant z MFFUK, spolupracoval jsem také s francouzským týmem, který se snažil kolize zreprodukovat, i s dalšími jednotlivci. První zklamání těchto lidí bylo vždy to, že něco na čínském útoku nefunguje. Ano, na to narazili všichni, kdo se snažili s MD5 něco dělat. Během krátkého zkoumání MD5 jsem také použil několik silných slov na adresu čínského týmu. Jejich podmínky pro fungování útoku byly totiž nepřesné, i když to jistě neudělali záměrně. Wangová byla v květnu překvapena faktem, že podmínky, které vydává za postačující pro fungování útoku, postačující nejsou. To jí bylo vytknuto na konferenci Eurocrypt, i když to ostatní účastníci nesli nelibě. Je fakt, že z hlediska jejího přínosu k hledání kolizí je to zanedbatelná prkotina. Tak to chápou všichni. Pro toho, kdo by chtěl kolize generovat svým algoritmem, je ale seznam podmínek na jednotlivé bity to nejzásadnější, co může být. Neboť změníte-li někde bitík nebo ho naopak někde nezměníte, dostanete zcela náhodné výsledky. Tak to u hašovacích funkcí chodí. Pokud tedy někdo chtěl najít skutečné postačující podmínky, musel vlastně celou práci Wangové pochopit a opravit nebo vylepšit po svém. Cesta Wangové není totiž jediná možná. To jsem nakonec demonstroval na svém algoritmu, který jsem vyvinul nezávisle na Wangové v době, kdy ten svůj ještě nezveřejnila. Z práce Wangové jsem tehdy nemohl použít více než dva kolidující řetězce. Prodělal jsem tedy stejný postup jako Australský tým Hawkese, který se snažil algoritmus také odhalit. Nepodařilo se jim to sice, ale popsali diferenční schéma, kterému vyhovovala kolidující data. Mě se podařilo s jejich výsledky postoupit dále a nezávisle objevit metodu mnohonásobné modifikace zpráv, kterou Wangová (v jednodušší formě), jak se ukázalo později, použila také. Pro počáteční podmínky jsem použil data Wangové a demonstroval na nich svoji metodu. Udělal jsem to víceméně z lenosti, protože jsem měl v programu k dispozici ony kolidující řetězce Wangové, které splňovaly počáteční postačující podmínky. Z mého hlediska jsem splnil cíl, protože jsem buď odhalil do té doby neznámou utajenou metodu Wangové nebo přišel na jinou. Kolize jsem generovat uměl a to i pro libovolný inicializační vektor. Na základě toho bylo možné předvést i názorné příklady možného využití. Metodu i program jsem popsal, ale zdrojový text jsem nezveřejnil (víceméně proto, že je to ošklivý céčkový slepenec a abych nebyl osočen z pomoci ošklivým hochům). Poté, co Wangová svoji metodu publikovala, se ukázalo, že jsou to vlastně metody v základní myšlence totožné, lišící se účinností a složitostí. Ve skutečnosti ale Wangová nepublikovala v mnohonásobných modifikacích nic konkrétního, co by se dalo použít pro programování. Proto ten, kdo chtěl naprogramovat algoritmus, který jsem popsal, mohl vyjít pouze z postačujících podmínek Wangové (později také publikovaných) nebo z podmínek Hawkese nebo nalézt svoji tzv. diferenční cestu. To bylo zhruba v dubnu. Navzdory tomu, že se o to pokoušelo více pracovišť, Japonci to jako jediní dotáhli (chtělo to velkou trpělivost a pracovitost). V práci Wang’s sufficient conditions of MD5 are not sufficient, kterou publikovali na serveru eprintu 10. srpna pak Jun Yajima a Takeshi Shimoyama představili opravenou verzi postačujících podmínek Wangové. To jim umožnilo za prvé generovat kolize a za druhé je generovat s jistotou, neboť jejich podmínky byly hledány tak, aby postačující skutečně byly. Je nutné to ještě ověřit, nicméně to bude už jen formální. Konečně tedy je v postačujících podmínkách udělán elementární pořádek. Nejedná se o žádný nový převratný výsledek v oblasti kolizí, ale o záslužnou špatně odměňovanou práci, při níž jednoho dne můžete zjistit, že před týdnem jste udělali chybu v jakémsi bitu jedné rovnice a tudíž můžete ten týden práce škrtnout a začít znovu od předchozího bodu. A těch závěrů, které musíte udělat naprosto přesně jsou spíše stovky.... Japonci Jun Yajima a Takeshi Shimoyama si proto zaslouží uznání. Pochopitelně citují moji práci, přičemž uvádí fakt, že ve slovech 6 - 15 prvního bloku zpráv jsme s Wangovou stejní. Na vysvětlenou, je to důsledek oné mojí lenosti, kdy jsem využil počátečních (i když nepřesných) podmínek Hawkese, vycházejících z dat Wangové. Protože cílem mojí práce nebylo stanovení postačujících podmínek ale nalezení metody generování kolizí, můj algoritmus fuzngoval navzdory nepřesnostem v postačujících podmínkách. Teď by to chtělo dát obojí dohromady a přidat ještě nějaké urychlení pomocí nových mnohonásobných modifikací. Doufám, že se na tom pracuje :-) a držím všem palce.

Relevantní odkazy naleznete na stránce, věnované kolizím.
Zdroj: http://eprint.iacr.org/2005/263
Autor: VK


<<- novější - MD5 prohrává u soudu
Burt Kaliski (RSA) - co dál s hashovacími funkcemi - starší ->>
Design: Webdesign