Atak urodzinowy

Ten artykuł od 2020-06 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle 2^{128}}$ różnych skrótów. Aby jednak trafić na dwa identyczne skróty z 50% prawdopodobieństwem, wystarczy wygenerować ok. ${\displaystyle 1,1774\cdot 2^{64}}$ skrótów.

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