Vlákno názorů k článku Praktické útoky na digitální podpisy používající hašovací funkci MD5 od kciii - Neviem ci tomu dobre rozumiem, podla mna: Pre lubovolny...

Neviem ci tomu dobre rozumiem, podla mna:

Pre lubovolny n-bitovy hash existuje kolizia na n+1 bitoch. Teda aj pre SHA by bolo mozne zopakovat v clanku popisany posup, alebo nie ? Akurat sa zatial nikomu ,,nechcelo'' hladat dva taketo 161 bitove retazce.

Nerozumieš. Kolize je pro MD5 možné hledat _mnohem rychleji_.

To mi je jasne. (rozumiem tomu tak, ze maju sposob generovania dvojic (s rovnakym hash-om) ale uz nie najdenie paru k existujucemu retazcu)

Ide mi len o to, ze ci v pripade ze mam nejaku koliziu mozem pouzit postup popisany v clanku.

Presne tak. Genericky utok (funkcny na kazdu hashovaciu funkciu) je mozne spravit narodeninovym paradoxom. Ak ma hash n-bitov, tak otestovanim 2^(n/2) sprav mame pravdepodobnost 50%, ze najdeme koliziu. Ale je to vypocetne velmi narocne (pri MD5 2^64 operacii, pri SHA-1 2^80 operacii, zhruba radovo tolko je treba aj pamate na ulozene uz vypocitanych hodnot).

Hashovacia funkcia sa povazuje sa prelomenu, ak sa najde utok, ktory to dokaze pocitat rychlejsie ako genericky utok. Utokov su hlavne dva druhy:

-first order collision: je mozne najst dve spravy s rovnakym hashom (to je prave pripad MD5)
-second order preimage collision - k lubovolnej pevne danej sprave je mozne najst inu spravu s rovnakym hashom

Je jasne, ze second order preimage collision znamena uz uplne zlomenie, ale uz first order bohate staci.