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