V novince
Zdrojové kódy pro kolizi MD5 za 45 minut a MD4 za 5 sekund
jsem upozornil na
první ve?ejn? dostupné zdrojové kódy na hledání kolizí MD5.
Nedalo mi to a o víkendu jsem se na n? podíval. Protože psali, že jim to trvá cca 45 minut na PC 1.6GHz a m? to trvalo cca 8 hodin na notebooku 1.6GHz, byl jsem zv?dav, kde je to urychlení. Prošel jsem první blok a zjistil, že pánové použili moji (první ve?ejn? publikovanou) metodu z ?lánku
Vlastimil Klima:
Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications , April 5, 2005, IACR ePrint archive,
Pokud se budete chtít podívat, sta?í si vzít slajd ?íslo 11 z
prezentace té metody na 3rd Int. Conference Security and Protection of Information 2005, Brno, Czech Republic, May 3 - 5,
2005 a porovnat :
první cyklus for(;;) = krok 1 mojí metody
LOOP_11 = krok 2 mojí metody
LOOP_12 = krok 3 mojí metody
Stach a Liu citují práci Wangové. V té se ovšem objevují pouze stacionární podmínky, ale nikoli tahle metoda, která je dokonce nohonásobn? rychlejší, než metoda, kterou použila Wangová.
V algoritmu hledání kolizí v druhém bloku nevidím nic zvláštního, takže abych pravdu ?ekl, nevím, kde je to urychlení... T?eba mám v tom svém programu n?jakou zpomalovací smy?ku :-)
Je to hrozný program, proto jsem ho také necht?l uve?ejnit. Cht?l jsem ho zve?ejnit až ho dod?lám a cca 100x urychlím, metody jsem popsal viz výše a n?jaké ješt? jsou v zásob?, sta?í to jen dosochat. Kdyby m?l n?jaký dobrovolník programátor zájem o spolupráci...
VK, 21.11.2005
