Názory k článku Bezpečnostní střípky za 46. týden
-
Nedalo mi to a o víkendu jsem se podíval na (první veřejně dostupné) zdrojové kódy na hledání kolizí MD5, viz odkaz výše a web http://www.stachliu.com/collisions.html .
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, http://eprint.iacr.org/2005/102.pdf.
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:
http://cryptography.hyperlink.cz/2005/Vlastimil_klima_SPI_2005.ppt 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. Od března jsem na to nešáhnul, ale kdyby se našel dobrovolník...
VK, 21.11.2005
