Ile przypadkowych elementów, zanim MD5 spowoduje kolizje?

164

Mam bibliotekę obrazów na Amazon S3. Dla każdego obrazu md5 adres URL źródła na moim serwerze oraz znacznik czasu, aby uzyskać unikalną nazwę pliku. Ponieważ S3 nie może mieć podkatalogów, muszę przechowywać wszystkie te obrazy w jednym płaskim folderze.

Czy muszę się martwić o kolizje w generowanej wartości skrótu MD5?

Bonus: ile plików mogę mieć, zanim zacznę widzieć kolizje w wartości skrótu generowanej przez MD5?

random md5 hash Ben Throop
źródło
1
Powiązane: Czy istnieją dwa znane ciągi, które mają tę samą wartość skrótu MD5?
kenorb
2
Dosłowna odpowiedź brzmi, że drugi plik może mieć to samo MD5 co pierwszy. Jednak szanse są bardzo małe.
Rick James

Odpowiedzi:

307

Prawdopodobieństwo przypadkowego zderzenia tylko dwóch haszów wynosi 1/2 128, czyli 1 na 340 undecillion 282 decillion 366 nonillion 920 oktylion 938 septillion 463 sekstyliony 463 biliardów 374 biliardów 607 bilionów 431 miliardów 768 milionów 211 tysięcy 456.

Jeśli jednak zachowasz wszystkie skróty, prawdopodobieństwo jest nieco większe dzięki paradoksowi urodzinowemu . Aby mieć 50% szans, że jakikolwiek hash koliduje z innym hashem, potrzebujesz 2 64 hashów. Oznacza to, że aby uzyskać kolizję, musisz średnio haszować 6 miliardów plików na sekundę przez 100 lat .

Kornel
źródło
20
"prawdopodobieństwo kolizji wynosi 1/2 ^ 64" - co? Prawdopodobieństwo kolizji zależy od liczby zahaszowanych elementów, nie jest to liczba stała. W rzeczywistości jest równe dokładnie 1 - sPn/s^n, gdzie sjest rozmiarem przestrzeni wyszukiwania ( 2^128w tym przypadku) i njest liczbą zahaszowanych elementów. Prawdopodobnie myślisz o tym 2^64, że jest to przybliżona liczba elementów, których potrzebujesz do mieszania MD5, aby mieć 50% szans na kolizję.
BlueRaja - Danny Pflughoeft
19
+1, ponieważ zawsze chciałem wiedzieć, jak liczyć ponad 999 bilionów lolów (i tak, twoja odpowiedź była pouczająca)
Kmeixner
7
Niestety nadal nie masz racji. Zakładasz, że funkcja skrótu jest naprawdę losowa. Nie jest. Oznacza to, że prawdopodobieństwo kolizji jest wyższe.
Jørgen Fogh
22
JørgenFogh: I wszystkie prawa fizyki też są „niepoprawne”. Taki poziom pedantyzmu jest niepotrzebny, ponieważ nie zmienia odpowiedzi w żaden znaczący sposób.
Kornel
20
Więc mówisz, że jest szansa!
vargonian
27

S3 może mieć podkatalogi. Po prostu umieść „/” w nazwie klucza, aby uzyskać dostęp do plików tak, jakby znajdowały się w oddzielnych katalogach. Używam tego do przechowywania plików użytkowników w oddzielnych folderach na podstawie ich identyfikatora użytkownika w S3.

Na przykład: „mybucket / users / 1234 / somefile.jpg”. Nie jest dokładnie tym samym, co katalog w systemie plików, ale interfejs API S3 ma pewne funkcje, które pozwalają mu działać prawie tak samo. Mogę poprosić o wyświetlenie wszystkich plików zaczynających się od „users / 1234 /” i pokaże mi wszystkie pliki w tym „katalogu”.

davr
źródło
7
Myślę, że to powinna być treść, ponieważ tak naprawdę nie odpowiada na pytanie o prawdopodobieństwo kolizji
Ian Clark
18

Więc czekaj, czy to jest:

md5(filename) + timestamp

lub:

md5(filename + timestamp)

W pierwszym przypadku większość drogi do identyfikatora GUID znajduje się na drodze i nie martwiłbym się o to. Jeśli to drugie, zobacz post Karga o tym, jak w końcu wpadniesz w kolizje.

Ryan
źródło
1
Opisz, jak włączenie sygnatury czasowej zwiększa ryzyko kolizji
Brad Thomas,
14
@BradThomas: Nie. Ryzyko kolizji MD5 jest takie samo, niezależnie od tego, czy występuje w nazwie pliku, czy w kombinacji nazwa pliku + znacznik czasu. Ale w pierwszym scenariuszu musiałbyś mieć zarówno kolizję MD5, jak i kolizję znacznika czasu.
Vincent Hubert
2
To nadal pozostawia 2 ^ (128 ^ 60) szansy na kolizję z dwoma użytkownikami na minutę. Dosłownie bezużyteczne.
Berry M.,
2
@BradThomas Żeby było jaśniej: md5(filename) + timestampznacznie zmniejsza ryzyko kolizji, ponieważ aby mieć kolizję ogólną, musiałbyś mieć kolizję md5 dla dokładnie tego samego sygnatury czasowej. md5(filename + timestamp)działa tak samo, jak md5(filename)zakładając, że nazwa pliku jest losowa na początku (ponieważ dodanie większej liczby losowości do czegoś losowego zmienia tylko indywidualny wynik md5, a problem z datą urodzenia nadal istnieje we wszystkich hashach md5).
robocat
10

Ogólną praktyczną zasadą dotyczącą kolizji jest pierwiastek kwadratowy z zakresu wartości. Twój znak MD5 ma prawdopodobnie 128 bitów, więc prawdopodobnie zobaczysz kolizje powyżej i powyżej 2 ^ 64 obrazów.

Will Dean
źródło
1
Prawdopodobnie masz na myśli 128 bitów, a nie 2 ^ 128. :-)
JesperE
5
pl.wikipedia.org/wiki/Birthday_Problem Więcej informacji o problemie.
Georg Schölly,
7

Chociaż przypadkowe kolizje MD5 są niezwykle rzadkie, jeśli użytkownicy mogą dostarczyć pliki (które będą przechowywane dosłownie), mogą zaprojektować kolizje. Oznacza to, że mogą celowo utworzyć dwa pliki z tą samą sumą MD5, ale różnymi danymi. Upewnij się, że Twoja aplikacja może obsłużyć ten przypadek w rozsądny sposób, lub może użyj silniejszego skrótu, takiego jak SHA-256.

bdonlan
źródło
użycie soli rozwiązałoby problem inżynieryjny użytkownika, prawda?
StackOverflowed
To zależy od sposobu nałożenia soli. Musiałby to być przedrostek danych dostarczonych przez użytkownika lub jeszcze lepiej klucz do HMAC. Jednak nadal dobrym pomysłem jest pogłębione ćwiczenie obrony.
bdonlan,
Zauważ, że chociaż SHA256 ma 256 bitów długości, możesz zrezygnować z ryzyka kolizji z długością przechowywanego klucza, skracając SHA256 do mniejszej liczby bitów, np. Użyj SHA256, ale skróć go do 128 bitów (co jest bezpieczniejsze niż użycie MD5, nawet chociaż mają taką samą liczbę bitów).
robocat
5

Chociaż pojawiły się dobrze nagłośnione problemy z MD5 spowodowane kolizjami, NIEZAMIERZONE kolizje między przypadkowymi danymi są niezwykle rzadkie . Z drugiej strony, jeśli haszujesz nazwę pliku, nie są to dane losowe i szybko spodziewałbym się kolizji.

acrosman
źródło
Jedyny problem, jaki mam z przykładem taylors, to to, że jeśli ktoś otrzyma kopię twojej bazy danych, prawdopodobnie mógłby obliczyć numery kart kredytowych za pomocą tęczowej tabeli ...
Sam Saffron
1
Chociaż nie zdecydowałbym się używać MD5 dla kart kredytowych, tabela Rainbow wszystkich ważnych numerów kart kredytowych od 10000000 (8 cyfr to najmniejsza karta kredytowa, jaką widziałem) do 9 999 999 999 999 999 (największa 16-cyfrowa liczba) jest nadal duża tabela do wygenerowania. Prawdopodobnie są łatwiejsze sposoby na kradzież tych liczb.
acrosman
1

Nie ma znaczenia, jakie to jest prawdopodobne; to jest możliwe. Może się to zdarzyć w przypadku pierwszych dwóch rzeczy, które haszujesz (bardzo mało prawdopodobne, ale możliwe), więc będziesz musiał obsługiwać kolizje od początku.

Karg
źródło
36
Oczywiście może być wiele innych złych rzeczy, które mogą się zdarzyć z prawdopodobieństwem 1/2 ^ 128. Możesz nie chcieć wyróżniać tego, aby się martwić.
Will Dean
2
Najgorsze, co może się tutaj zdarzyć, to zrobić sobie zdjęcie. Dla stosunkowo niewielkiej liczby nie martwiłbym się. Jeśli twoje oprogramowanie steruje autopilotem lądującym samolotem, to już inna historia.
Jim C
9
Nie możesz być poważny. Będziesz musiał haszować 6 miliardów plików na sekundę, co sekundę przez 100 lat, aby uzyskać dużą szansę na kolizję. Nawet jeśli masz pecha, prawdopodobnie zajmie to więcej niż całą pojemność S3 używaną dłużej niż ludzkie życie.
Kornel
12
Jest miliardy razy bardziej prawdopodobne, że baza danych i jej kopie zapasowe ulegną awarii. Nie warto się martwić o kolizje.
Artelius,
5
Wykorzystaj czas zapobiegania kolizjom, budując bunkier, aby umieścić serwer! Te brzydkie meteory mogą cię uderzyć (bardzo mało prawdopodobne, ale możliwe), więc będziesz musiał wspierać schronienie przed meteorytami od samego początku.
polvoazul
1

Kolizja MD5 jest bardzo mało prawdopodobna. Jeśli masz 9 bilionów MD5, jest tylko jedna szansa na 9 bilionów , że dojdzie do kolizji.

Rick James
źródło
1
Wiele innych odpowiedzi mówi o prawdopodobieństwie kolizji podczas dodawania jeszcze jednego elementu. Myślę, że moja odpowiedź jest bardziej przydatna, ponieważ mówi o tym, że prawdopodobnie cały stół ma dupę.
Rick James,
1
Nie ma to nic wspólnego z MD5 i nie jest poprawne. To tak, jakby powiedzieć, że jeśli masz 9 bilionów kotów, istnieje szansa 1 na 9 bilionów, że ktoś inny ma identycznego kota. Kluczowy problem polega na tym, że możesz uzyskać ten sam hash z więcej niż jedną wartością.
Joonas Alhonen
@JoonasAlhonen - Tak, to prawda. I wielu biednych ludzi używa tego jako wymówki, aby kupić kolejny los na loterię, na który ich nie stać.
Rick James
Dzięki, to w rzeczywistości bardzo przydatna statystyka. Szanse na kolizję przy wstawieniu 9 bilionów pozycji. Dzięki.
Tom P.