Atak urodzinowy

Atak urodzinowy w kryptoanalizie

Atak urodzinowy ma na celu znalezienie kolizji w funkcjach haszujących, korzystając z paradoksu dnia urodzin. Technika ta jest formą ataku siłowego, która pozwala na oczekiwanie szybszego odkrycia kolizji niż sugerowałby to rozmiar przeciwdziedziny funkcji haszującej.

Paradoks dnia urodzin

Paradoks ten wskazuje, że liczba prób potrzebnych do znalezienia kolizji rośnie proporcjonalnie do pierwiastka z liczby możliwych wyników funkcji haszującej. Oznacza to, że znalezienie dwóch identycznych skrótów wymaga znacznie mniej prób, niż mogłoby się wydawać.

Przykład zastosowania

Rozważmy algorytm haszujący MD5, który generuje 128-bitowe skróty, co daje $2^\{128\}$ różnych możliwości. Aby osiągnąć 50% prawdopodobieństwo znalezienia kolizji, wystarczy wygenerować około $1,1774\; \backslash cdot\; 2^\{64\}$ skrótów.

Więcej informacji na temat tego zagadnienia można znaleźć w artykule poświęconym paradoksowi dnia urodzin.