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. Jejich autoři (Wangová a kol.) však utajili metodu nalézání kolizí a zveřejnili pouze strohá data a informace. V říjnu 2004 se australský tým (Hawkes a kol.) pokusil tuto metodu zrekonstruovat ve skvělé práci. Nejdůležitější "čínský trik" se nepodařilo objevit, ale na základě dat Wangové bylo dobře popsáno diferenční schéma, kterým uveřejněné čínské kolize vyhovují. Naplnění podmínek tohoto schématu bylo však ještě příliš náročné a výpočetně složitější, než ukazovaly výsledky. V našem výzkumu jsme také analyzovali dostupná data diferenční kryptoanalýzou. Nalezli jsme 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 32-procesorovém serveru IBM p690.

Rychlé nalezení kolizí je velmi zneužitelné pro falšování podpisů SW balíků nebo padělání certifikátů. Když jsem o tomto výsledku informoval na "českém internetu", netušil jsem, že mě o vánocích problém natolik chytne, že mu věnuji další dva měsíce. Výsledkem je, že také umím nalézat kolize MD5 pro jakoukoli inicializační hodnotu, a 3 - 6 krat rychleji než čínský tým...

MD5 kolize - podrobnosti PDF IACR