59
Biorąc pod uwagę zestaw 100 różnych ciągów o równej długości, jak można obliczyć prawdopodobieństwo, że kolizja skrótu SHA1 dla ciągów jest mało prawdopodobna ...?Prawdopodobieństwo zderzeń SHA1
A
Odpowiedz
137
Czy wartości hash 160 bitowe generowane przez SHA-1 na tyle duże, aby zapewnić fingerprint każdego bloku jest wyjątkowy? Zakładając losowych wartości hash rozkładu jednolite, zbiór n różnych bloków danych i mieszania funkcja wytwarza bitów B, pod prawdopodobieństwo p, że będzie jeden lub bardziej kolizji jest ograniczona przez liczbę par z bloków pomnożonych przez przez prawdopodobieństwo zderzenia danej pary .
(źródło: http://bitcache.org/faq/hash-collision-probabilities)
+9
Podsumowując, prawdopodobieństwo kolizji jest rzędu 10^-45. To bardzo, * bardzo * mało prawdopodobne. –
+3
Ale SHA-1 nie jest jednolitym rozkładem, może być większy niż ta górna granica. Wątpię, by to równanie nie było prawidłowe. A przynajmniej EQUAL. – Kamel
+1
Ta odpowiedź nie uwzględnia chińskiego odkrycia w 2005 r., W którym są one w stanie produkować kolizje w iteracjach 2^69, a nie 2^80 rzutowanych przez brutalną siłę https://www.schneier.com/blog/archives /2005/02/sha1_broken.html – Djarid
2
To jest Birthday Problem - artykuł zawiera ładne przybliżenia, które pozwalają dość łatwo oszacować prawdopodobieństwo. Rzeczywiste prawdopodobieństwo będzie bardzo bardzo niskie - patrz np. this question.
3
Cóż, prawdopodobieństwo zderzenia będzie 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * ((2^160 - 99)/2^160).
Pomyśl o prawdopodobieństwie zderzenia 2 elementów w przestrzeni 10. Pierwszy element jest unikalny z prawdopodobieństwem 100%. Drugi jest unikalny z prawdopodobieństwem 9/10. Więc prawdopodobieństwo, że obie są unikalne wynosi 100% * 90%, a prawdopodobieństwo kolizji wynosi 1 - (100% * 90%) lub 1 - ((10 - 0)/10) * ((10 - 1)/10) lub 1 - ((10 - 1)/10).
Jest to mało prawdopodobne. Musiałbyś mieć wiele więcej ciągów, aby była to odległa możliwość.
Spójrz na tabelę na this page on Wikipedia; po prostu interpoluj między wierszami dla 128 bitów i 256 bitów.
wyjaśnienie, w jaki sposób można mieć 'różne', ale równej długości struny? – KevinDTimm
@kevindtimm "a", "b", "c" są jednakowej długości, ale różne ciągi znaków –
Domyślam się, że ciągi mają długość co najmniej 20 bajtów. W przeciwnym razie, oczywiście szanse byłyby większe od kolizji. :) –