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
Generowanie kolizji[edytuj | edytuj kod]
Jeśli funkcja skrótu zwraca bitów, to zgodnie z paradoksem dnia urodzin sprawdzenie wśród zbioru losowo wybranych wiadomości rozmiaru rzędu 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.