Kolizja (kryptografia)
Z Wikipedii
Kolizja funkcji haszującej H to taka para różnych wiadomości m1, m2, że mają one taką samą wartość hasza, tj. H(m1) = H(m2).
Ponieważ funkcja haszująca 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 haszującej jakieś kolizje istnieją.
W wielu zastosowaniach zależy nam na tym, żeby nie znana była żadna kolizja funkcji haszującej. 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
[edytuj] Generowanie kolizji
Jeśli funkcja haszująca zwraca k bitów, to zgodnie paradoksem dnia urodzin sprawdzenie wśród zbioru losowo wybranych wiadomości rozmiaru rzędu 2k / 2 prawdopodobnie istnieje jakaś kolizja. Jest to zasada działania ataku urodzinowego.
Najprostszy sposób, czyli pamiętanie wszystkich dotychczas sprawdzonych haszy, 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 haszującej (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, RIPEMD160) jest równie trudne jak łamanie 80-bitowego szyfru symetrycznego, i jest na dzień dzisiejszy uważane za zbyt trudne.
Liczby te dotyczą tylko sytuacji w której funkcją haszującą 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 haszującej, 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.
