Názory k článku Bezpečnostní střípky za 46. týden

Vlastimil Klíma

21. 11. 2005 10:23 Nový

Stach a Liu realizovali moji metodu

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