Atak urodzinowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Celem ataku urodzinowego jest znalezienie kolizji funkcji haszującej. Jest to atak siłowy. U jego podstaw leży jednak paradoks dnia urodzin, który pozwala oczekiwać, że kolizja zostanie znaleziona znacznie szybciej niż sugerowałby to rozmiar przeciwdziedziny funkcji haszującej. Liczba potrzebnych do tego sprawdzeń rośnie bowiem proporcjonalnie do pierwiastka z liczby wszystkich możliwych wyników funkcji haszującej.

Przykład: Algorytm haszujący MD5 generuje 128-bitowe skróty. Daje nam to 2^{128} różnych skrótów. Aby jednak trafić na dwa identyczne skróty z 50% prawdopodobieństwem, wystarczy wygenerować ok. 1,1774\cdot 2^{64} skrótów.

Szczegółowe wyprowadzenie znajduje się w artykule paradoks dnia urodzin.