Tekst źródłowy strony Kolizja (kryptografia)

'''Kolizja''' [[funkcja skrótu|funkcji skrótu]] <code>H</code> to taka para różnych wiadomości <code>m1</code>, <code>m2</code>, że mają one taką samą wartość skrótu, tj. <code>H(m1) = H(m2)</code>.

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 <code>m1</code> takiego <code>m2</code>, że <code>H(m1) = H(m2)</code>, czyli [[second preimage resistance]]
* niemożliwość znalezienia, dla danego <code>h</code> takiego <code>m</code> że <code>H(m) = h</code>, czyli [[preimage resistance]]

== Generowanie kolizji ==
Jeśli funkcja skrótu zwraca <math>k</math> bitów, to zgodnie z [[paradoks dnia urodzin|paradoksem dnia urodzin]] sprawdzenie wśród zbioru losowo wybranych wiadomości rozmiaru rzędu <math>2^{k/2}</math> prawdopodobnie istnieje jakaś kolizja. Jest to zasada działania [[atak urodzinowy|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 [[Obliczenia rozproszone|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 ==
* [http://www.faqs.org/rfcs/rfc4270.html RFC 4270 "Attacks on Cryptographic Hashes in Internet Protocols"]

[[Kategoria:Funkcje skrótu]]