Kolizje hashy są matematycznie nieuniknione — bezpieczeństwo polega na czymś innym
Funkcja hashująca zamienia dane o potencjalnie dowolnej długości na wynik o stałej liczbie bitów. To oznacza, że możliwych wejść jest więcej niż możliwych hashy, więc zgodnie z zasadą szufladkową co najmniej dwa różne wejścia muszą kiedyś prowadzić do tego samego wyniku. „Collision resistant” nie oznacza zatem „bez kolizji”. NIST definiuje odporność na kolizje jako obliczeniową trudność znalezienia dwóch różnych wejść z tym samym hashem. Dla idealizowanego n-bitowego hasha atak urodzinowy sugeruje poziom bezpieczeństwa kolizyjnego około n/2 bitów; dlatego np. 256-bitowy output odpowiada w przybliżeniu 128-bitowej sile przeciw ogólnemu szukaniu kolizji.
Nieskończenie wiele wiadomości, skończenie wiele skrótów
Hash kryptograficzny może przyjąć wiadomości o bardzo wielu długościach, a wynik ma ustalony rozmiar — np. 256 bitów. To daje 2^256 możliwych wyników. Liczba możliwych wiadomości jest jednak większa. Gdy mapujemy większy zbiór do mniejszego, różne elementy muszą trafić do tych samych „szuflad”. NIST w materiałach o funkcjach hashujących wprost wskazuje, że z powodu zasady szufladkowej istnienie kolizji jest nieuniknione.
Z tego powodu żaden poprawny projekt kryptograficznego hasha o stałej długości nie może obiecać matematycznej unikalności dla wszystkich możliwych wejść. To byłoby niemożliwe niezależnie od jakości algorytmu.
„Odporność” oznacza trudność znalezienia, nie brak istnienia
NIST definiuje collision resistance jako obliczeniową niepraktyczność znalezienia dwóch różnych wejść mapowanych do tego samego wyniku. Kolizje istnieją, lecz dobry hash ma sprawić, że ich wyszukanie metodą ogólną wymaga niewyobrażalnie dużej pracy.
To subtelne, ale fundamentalne rozróżnienie między własnością matematyczną a bezpieczeństwem obliczeniowym. Kryptografia bardzo często nie mówi „atak jest niemożliwy”, tylko „najlepszy znany atak przy założonym modelu wymaga zasobów przekraczających praktyczne możliwości”. Dlatego zwiększanie długości wyniku ma znaczenie: powiększa przestrzeń, którą atakujący musi eksplorować.
Paradoks urodzin obcina efektywny wykładnik o połowę
Jeśli chcemy znaleźć wejście pasujące do konkretnego z góry ustalonego 256-bitowego hasha, naturalna ogólna skala wyszukiwania to około 2^256 prób. Dla kolizji zadanie jest inne: wystarczy dowolna para dwóch różnych wiadomości o tym samym wyniku. Możemy porównywać hashe wszystkich wygenerowanych wiadomości ze sobą, więc liczba możliwych par rośnie kwadratowo.
To analog paradoksu urodzin. W grupie ludzi nie szukamy osoby urodzonej konkretnego dnia; szukamy dowolnej pary ze wspólnymi urodzinami. Dla idealizowanego n-bitowego hasha ogólny koszt znalezienia kolizji jest rzędu 2^(n/2). NIST podaje dla SHA-256 siłę odporności na kolizje równą 128 bitom, podczas gdy odporność na preimage jest oceniana na 256 bitów.
Kolizja w tablicy hashującej i kolizja kryptograficzna to nie to samo
Słowo „hash” występuje także w zwykłych tablicach hashujących. Tam kolizje są normalnym zjawiskiem obsługiwanym przez chaining, open addressing lub inne techniki. Głównym celem jest równomierne rozłożenie kluczy i szybkie operacje, a nie odporność na przeciwnika próbującego celowo znaleźć szczególne pary.
Hash kryptograficzny ma inne wymagania: preimage resistance, second-preimage resistance i collision resistance. Ta sama matematyczna nieuchronność kolizji występuje w obu przypadkach, ale znaczenie praktyczne jest inne. W tablicy hashującej kolizję trzeba poprawnie obsłużyć. W kryptografii trzeba sprawić, by przeciwnik nie umiał jej efektywnie skonstruować.
Dlaczego jedna znaleziona metoda ataku ma znaczenie
Jeżeli badacze znajdują atak, który pozwala tworzyć kolizje dużo szybciej niż ogólne 2^(n/2), nie oznacza to, że dopiero wtedy „odkryto istnienie kolizji”. O ich istnieniu wiadomo od początku. Nowością jest algorytmiczny skrót pozwalający je znaleźć w praktycznie istotniejszym czasie.
To zmienia sposób patrzenia na bezpieczeństwo funkcji hashujących. Celem nie jest magiczne uniknięcie zasady szufladkowej, lecz utrzymanie wystarczająco wysokiego kosztu najlepszego znanego ataku. Matematyka gwarantuje, że kolizje gdzieś są; kryptografia stara się sprawić, by droga do nich była obliczeniowo poza zasięgiem.
Więcej bitów nie usuwa kolizji, tylko przesuwa granicę praktyczności
Jeśli funkcja zwraca 256 bitów, liczba możliwych skrótów wynosi 2^256 — astronomicznie dużo, ale nadal skończenie wiele. Zasada szufladkowa nadal obowiązuje dokładnie tak samo jak dla 32 bitów. Różnica jest ilościowa: ogólny atak urodzinowy potrzebuje skali około 2^128 prób, co ma być poza praktycznym zasięgiem. Dlatego NIST określa dla SHA-256 odporność na kolizje na poziomie 128 bitów bezpieczeństwa, a odporność na preimage na poziomie 256 bitów przy założeniu braku lepszego ataku. Zwiększenie długości skrótu nie zmienia faktu matematycznego, lecz koszt poszukiwania. To bardzo typowe dla kryptografii: „bezpieczne” oznacza, że najlepsza znana droga do złamania własności wymaga nieosiągalnych zasobów w zakładanym modelu, a nie że zdarzenie jest logicznie niemożliwe.