W jaki sposób funkcje hashowe, takie jak MD5, są unikalne?

Masz absolutną rację. Ale hasze nie są o "unikalny", są o "wystarczająco unikalny".

Jak zauważyli inni, celem funkcji skrótu, takiej jak MD5, jest zapewnienie sposobu łatwego sprawdzenia, czy dwa obiekty są równoważne, bez wiedzy, czym pierwotnie były (hasła) lub porównywania ich w całości (duże pliki).

Powiedz, że masz obiekt O i jego hash h _O . Otrzymujesz inny obiekt P i chcesz sprawdzić, czy jest równy O. Może to być hasło lub plik, który pobrałeś (w takim przypadku nie będziesz miał O, ale raczej hash tego h _O , który przyszedł z P, najprawdopodobniej). Najpierw hash P, Aby uzyskać h _P .

Są teraz 2 możliwości:

1. h _O i h _P są różne. To musi oznaczać, że O i P są różne, ponieważ użycie tego samego hasha na 2 wartościach / obiektach musi dać tę samą wartość. Hasze są deterministyczne. Nie ma fałszywych negatywów.

2. H _O i h _P są równe. Jako stwierdziłeś, że ze względu na zasadę Pigeonhole to może oznaczać, że różne obiekty zahaszowane są do tej samej wartości, a dalsze działania mogą wymagać podjęcia.

   A. Ponieważ liczba możliwości jest tak duża, jeśli masz wiarę w swoją funkcję haszującą, może wystarczyć powiedzieć: "Cóż, było 1 w 2¹²⁸ szansa kolizji( przypadek idealny), więc możemy założyć O = P. Może to działać w przypadku haseł, jeśli ograniczysz długość i złożoność znaków, na przykład. Dlatego widzisz hasze haseł przechowywanych w bazach danych, a nie same hasła. b. możesz zdecydować, że tylko dlatego, że hash wyszedł równy, nie oznacza, że obiekty są równe, i zrobić bezpośrednie porównanie O i P. Możesz mieć fałszywy wynik.

Więc chociaż możesz mieć fałszywie pozytywne dopasowania, nie będziesz miał fałszywie negatywnych. W zależności od aplikacji i od tego, czy obiekty mają być zawsze równe, czy zawsze różne, haszowanie może być zbędnym krokiem.

Kryptograficzne jednokierunkowe funkcje skrótu są z natury definicji nie injekcyjne . Jeśli chodzi o funkcje hashowe, "unique" jest dość bezsensowne. Funkcje te są mierzone przez inne atrybuty, co wpływa na ich siłę, utrudniając stworzenie wstępnego obrazu danego hasha. Na przykład możemy dbać o to, na ile bitów obrazu wpływa zmiana pojedynczego bitu w obrazie wstępnym. Może nam zależeć, jak trudno jest przeprowadzić atak brute force (znalezienie prie-image dla given hash image). Może nam zależeć, jak trudno jest znaleźć kolizję: znalezienie dwóch obrazów wstępnych, które mają ten sam obraz hash, do użycia w ataku urodzinowym .

Chociaż jest prawdopodobne, że uzyskasz kolizje, jeśli wartości, które mają być hashowane, są znacznie dłuższe niż wynikowy hash, liczba kolizji jest nadal wystarczająco niska dla większości celów (istnieją 2¹²⁸ możliwe hashe razem, więc szansa na dwa losowe ciągi wytwarzające ten sam hash jest teoretycznie blisko 1 w 10³⁸).

MD5 został stworzony przede wszystkim do sprawdzania integralności, więc jest bardzo wrażliwy na minimalne zmiany. Drobna modyfikacja wejścia spowoduje skutkować drastycznie inną wydajnością. Dlatego trudno odgadnąć hasło na podstawie samej wartości hash.

Chociaż sam hash nie jest odwracalny, nadal można znaleźć możliwą wartość wejściową za pomocą czystej brutalnej siły. Dlatego zawsze powinieneś dodać salt, jeśli używasz MD5 do przechowywania hashów haseł: jeśli umieścisz salt w łańcuchu wejściowym, pasujący łańcuch wejściowy musi zawierać dokładnie ten sam salt, aby uzyskać ten sam łańcuch wyjściowy, ponieważ w przeciwnym razie surowy łańcuch wejściowy, który pasuje do wyjścia, NIE będzie pasował po automatycznym soleniu (tzn. nie możesz po prostu "odwrócić" MD5 i użyć go do logowania, ponieważ odwrócony Skrót MD5 najprawdopodobniej nie będzie solonym łańcuchem, który pierwotnie spowodował utworzenie skrótu).

Więc hasze nie są unikalne, ale mechanizm uwierzytelniania może być wykonany tak, aby uczynić go wystarczająco unikalnym (co jest jednym z dość wiarygodnych argumentów za ograniczeniami haseł zamiast saltowania: zestaw łańcuchów, które powodują ten sam hash, będzie prawdopodobnie zawierał wiele łańcuchów, które nie spełniają ograniczeń hasła, więc trudniej jest odwrócić hash brutalną siłą - oczywiście sole są nadal dobrym pomysłem).

Większe skróty oznaczają większy zestaw możliwych skrótów dla tego samego zestawu wejściowego, więc mniejsza szansa na nakładanie się, ale dopóki moc obliczeniowa nie zwiększy się wystarczająco, aby wymuszanie brutalne MD5 stało się trywialne, nadal jest to przyzwoity wybór dla większości celów.

(wydaje się, że jest to funkcja Hash Sunday.)

Kryptograficzne funkcje skrótu są zaprojektowane tak, aby charakteryzowały się bardzo, bardzo, bardzo niskim współczynnikiem powielania. Z oczywistego powodu, który Pan stwierdza, stawka nigdy nie może być zerowa.

Strona Wikipedii ma charakter informacyjny.

Jak powiedział Mike (i w zasadzie każdy inny), nie jest idealny, ale wykonuje swoją pracę ,a wydajność kolizji naprawdę zależy od algo (który jest właściwie całkiem dobry).

Jak odpowiedzieli inni, funkcje skrótu z definicji nie mają gwarancji zwracania unikalnych wartości, ponieważ istnieje stała liczba skrótów dla nieskończonej liczby wejść. Ich kluczową cechą jest to, że ich kolizje są nieprzewidywalne .

Innymi słowy, nie są one łatwo odwracalne -- więc chociaż może być wiele różnych danych wejściowych, które będą produkować ten sam wynik hash ("kolizja"), znalezienie dowolnych dwóch z nich jest obliczeniowo niewykonalne.