Jest to zasada działania ataku urodzinowego.
Najprostszy sposób, czyli pamiętanie wszystkich dotychczas sprawdzonych skrótów, wymaga bardzo dużo pamięci, istnieją jednak algorytmy "bezpamięciowe" o szybkości gorszej tylko o czynnik stały.
Tak więc znalezienie kolizji 128-bitowej funkcji skrótu (takiej jak MD5) jest zadaniem o trudności porównywalnej ze znalezieniem klucza 64-bitowego szyfru symetrycznego. Nie jest to zadanie trywialne, aczkolwiek znajduje się w zasięgu możliwości współczesnego sprzętu i sieci rozproszonych. Znajdowanie kolizji funkcji 160-bitowych (SHA1, RIPEMD-160) jest równie trudne jak łamanie 80-bitowego szyfru symetrycznego, i jest obecnie uważane za zbyt trudne.
Liczby te dotyczą tylko sytuacji w której funkcją skrótu posługujemy się jako "czarną skrzynką", tzn. nie korzystamy z wiedzy o jej strukturze. Wykorzystując słabości struktury możemy często znajdować kolizje o wiele szybciej (np. dla MD4 kolizje można znaleźć w czasie rzeczywistym).
Znajdowanie przeciwobrazu czy drugiego przeciwobrazu jest równoważne atakowi na wszystkie bity funkcji skrótu, dlatego też 128-bitowe MD5 jest uważane za bezpieczne jeśli zależy nam tylko na tych właściwościach, choć nie chroni przed kolizjami.
Linki zewnętrzne RFC 4270 "Attacks on Cryptographic Hashes in Internet Protocols"
Kategoria:Funkcje skrótu