Nalézání kolizí MD5 - hra?ka pro notebook
Vlastimil Klíma
5. b?ezna 2005
Abstrakt: Jednou z nejvýznamn?jších kryptologických událostí posledních let bylo objevení kolizí pro sérii hašovacích funkcí MD4, MD5, HAVAL-128 a RIPEMD ?ínským týmem v srpnu 2004 [1]. Jejich auto?i (Wangová a kol.) však utajili metodu nalézání kolizí a zve?ejnili pouze strohá data a informace. Nalezl jsem však cestu, jak generovat kolize prvního bloku 1000 - 2000 krát rychleji než ?ínský tým, což odpovídá nalezení jedné kolize prvního bloku na b?žném notebooku za 2 minuty. ?ínskému týmu tato fáze trvá jednu hodinu na superpo?íta?i IBM P690, naproti tomu jsou 2 - 80 krát rychlejší p?i vyhledávání kolizí druhého bloku. Ob? metody se proto mohou lišit nejen ?asov?, ale i obsahov?. Celkov? je moje metoda 3 - 6 krát rychlejší.
Konkrétn? nalezení první kolize na notebooku (Intel Pentium 1.6 GHz) mi trvalo pouze 8 hodin. Poznamenávám, že nová metoda pracuje pro jakoukoli zvolenou inicializa?ní hodnotu. To by m?lo být varováním p?ed dalším používáním této hašovací funkce. V p?íloze uvádím nové p?íklady kolizí MD5 pro standardní a zvolenou inicializa?ní hodnotu.
Podrobnosti naleznete
zde.
