Během týdne se objevily hned dvě důležité Novinky (s velkým N) z oblasti bezpečnosti hashovacích funkcí.
Sbohem SHA-1 …
Nejprve Akashi Satoh publikoval návrh hardware, který by nalezl kolize SHA-1 (podle původního návrhu Wangové se složitostí 269). Podle jeho studie lze nyní již za 10 milionů dolarů sestavit zákaznický hardwarový systém, který by sestával z 303 PC, každý s 16 deskami (na každé je 32 jader SHA-1), pracujícími paralelně. Útok by trval 127 dní …
Vzhledem k tomu, že v létě tým čínské profesorky Wangové publikoval útok, který snížil složitost 64 krát (na 263), se dá očekávat, že bude možné navrhnout hardware, který bude realizovat hledání kolizí SHA-1 (při obdobných nákladech) ve dvou dnech!
Akashi Satoh: Hardware Architecture and Cost Estimates for Breaking SHA-1 ISC 2005.
Útok na MD5 ještě rychlejší …
V publikováné práci japonského týmu (Sasaki, Naito, Kunihiro, Ohta) se zlepšuje kolizní útok MD5 týmu Wangové (se složitostí 237) a útok Klímy (se složitostí 233) na útok se složitostí 230. Pokud český kryptolog Vlastimil Klíma prokázal, že lze na obyčejném notebooku najít kolize v řádu hodin, je pak tato nová metoda ještě cca 8× účinnější a lze vlastně kolize hledat „na počkání“.
Japonský tým je čtvrtý na světě, který umí kolize hledat. Jejich zlepšení vychází přdevším z postačujících podmínek Wangové a některých myšlenek Klímy. Podařilo se jim odstranit některé chyby v předchozí práci Wangové a dotáhnout náročné „hraní“ s podmínkami až do konce …
Komentář Vlastimila Klímy v NEWS na Crypto-Worldu. Práce japonského týmu: Improved Collision Attack on MD5.
