Kolizja (kryptografia)

Kolizja funkcji skrótu H to taka para różnych wiadomości m1, m2, że mają one taką samą wartość skrótu, tj. H(m1) = H(m2).

Ponieważ funkcja skrótu zwraca skończenie wiele wartości, a przestrzeń argumentów jest nieskończona (w przypadku funkcji akceptujących dowolnie długie argumenty), lub przynajmniej znacznie większa od przestrzeni wyników, dla każdej funkcji skrótu istnieją kolizje.

W wielu zastosowaniach zależy nam na tym, żeby nie była znana żadna kolizja funkcji skrótu. Jest to jednak bardzo silne wymaganie, i często zależy nam na słabszej właściwości funkcji (od silniejszych do słabszych właściwości):

• niemożliwość łatwego generowania nowych kolizji
• niemożliwość znalezienia, dla danego m1 takiego m2, że H(m1) = H(m2), czyli second preimage resistance
• niemożliwość znalezienia, dla danego h takiego m że H(m) = h, czyli preimage resistance

Jeśli funkcja skrótu zwraca ${\displaystyle k}$ bitów, to zgodnie z paradoksem dnia urodzin sprawdzenie wśród zbioru losowo wybranych wiadomości rozmiaru rzędu ${\displaystyle 2^{k/2}}$ prawdopodobnie istnieje jakaś kolizja. 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.

• RFC 4270 "Attacks on Cryptographic Hashes in Internet Protocols"