Jak dokładny jest `md5sum`?

W przypadku md5sumweryfikacji integralności pliku, jak dokładny jest ten proces?

Czy zweryfikowany MD5 oznacza, że KAŻDY bit jest dokładnie taki sam, czy też istnieje próg, który należy przekroczyć, zanim zmiany binarne zostaną odzwierciedlone w MD5?

Doceniona zostanie również wszelka dokumentacja generowania md5.

linux md5sum

— Konner Rasmussen
źródło

en.wikipedia.org/wiki/MD5

— choroba

@choroba, jeśli czytam to wszystko poprawnie, wówczas prawdopodobieństwo niewykrycia zmiany wzrasta wraz ze wzrostem wielkości weryfikowanego pliku. Jest to jednak nadal prawdopodobne i 100% pewności można uzyskać tylko w przypadku pliku 16-bajtowego. Mam rację?

— Konner Rasmussen

@Konner Przeczytałem twoje pytanie dotyczące transferu plików. W tym celu jest bezpieczny. Szanse na uszkodzenie podczas transferu są niewielkie i bardziej prawdopodobne jest, że stracisz część skopiowanego pliku podczas transferu, zakładając, że zrozumiałem twoją poprzednią sytuację . MD5 jest wysiłkiem równoważnym z porównywaniem obu plików, z pewną zaletą polegającą na tym, że nie trzeba uzyskiwać dostępu do obu plików jednocześnie.

— Doktoro Reichard

„Czy zweryfikowany MD5 oznacza, że KAŻDY bit jest dokładnie taki sam”. Pamiętaj, że jest to niemożliwe dzięki Zasadzie Pigeonhole. en.wikipedia.org/wiki/Pigeonhole_principle

— Plutor

Nie sądzę, żebyś otrzymał gwarancję na pliki 16-bajtowe.

— Mooing Duck

Odpowiedzi:

MD5 został złamany w tym celu przeciwko inteligentnemu przeciwnikowi. Możliwe jest złośliwe skonstruowanie dwóch różnych bloków danych, które wytwarzają ten sam skrót MD5.

Jednak jest całkowicie odpowiednie (choć są prawie na pewno lepsze sposoby) użycie MD5 w celu ochrony przed przypadkowym uszkodzeniem danych podczas transportu lub przechowywania. Chociaż możliwe jest, że takie zdarzenie może spowodować, że skrót MD5 będzie taki sam, prawdopodobieństwo jest tak niskie, że prawie niewyobrażalne jest prawdopodobieństwo, o które warto się martwić. Awarie spowodowane przez promieniowanie tła, tunelowanie, statyczne i dziesiątki innych źródeł byłyby bardziej prawdopodobne o rząd wielkości.

Nawet jeśli masz kwadrylion jednostek danych, prawdopodobieństwo, że niedopasowane MD5 wytworzy skrót MD5 należący do jednej z tych kwadrylionów, jest znacznie mniejsze niż jeden na kwadrylion.

— David Schwartz
źródło

Chociaż teoretycznie możliwe jest wygenerowanie dwóch plików z tym samym hashem, może to być praktycznie niemożliwe. Zwłaszcza jeśli plik zastępczy również powinien mieć sens. Jeśli na przykład oryginalny plik był tekstem w języku angielskim, może nie być innego dopasowania, które byłoby także w języku angielskim. Lub jeśli jest to arkusz kalkulacyjny Excel, żaden inny plik z tym samym hashem nie będzie poprawnym arkuszem kalkulacyjnym.

— Barmar

@Barmar: win.tue.nl/hashclash/Nostradamus ci faceci utworzyli wiele plików pdf z tym samym hasłem MD5, aby udowodnić, że jest to praktycznie wykonalne.

— philfr

MD5 to skrót. Zasadniczo odwzorowuje całą zawartość pliku na niewielki ciąg o długości 16 bajtów IIRC.

Oczywiście będzie wiele plików z tą samą sumą MD5. Dlatego zgodna suma MD5 nie gwarantuje dokładnego dopasowania między plikami.

Jako taki nie ma progu, ponieważ sposób działania skrótów działa. Tak więc suma MD5 może wykryć nawet jedną zmianę bitową. Jednak wiele zmian pojedynczych bitów razem może spowodować, że skrót MD5 będzie taki sam. Dlatego rozsądnie jest używać MD5 do sprawdzania integralności pliku pod kątem przypadkowego uszkodzenia, ale nie, jeśli złośliwe zamiary są możliwe, ponieważ ktoś może zmodyfikować plik, upewniając się, że skrót MD5 jest taki sam.

— Itai
źródło

tak krótka historia jest taka, że md5 to tylko szybki i brudny sposób weryfikacji integralności pliku i powinien być używany tylko wtedy, gdy niewykryty błąd nie spowodowałby katastrofalnych następstw ... prawda?

— Konner Rasmussen

najlepszym jego zastosowaniem jest wykrycie uszkodzenia podczas transferu lub kopiowania. nie tak naprawdę dla bezpieczeństwa.

— Michael Martinez

@KonnerRasmussen - to nie jest kwestia stopnia reperkusji, to natura zagrożenia. Jeśli obawiasz się, że dwa dokumenty mogą przypadkowo mieć ten sam MD5, przestań się martwić: szanse są znacznie wyższe, że komputery spontanicznie staną w płomieniach; jeśli obawiasz się, że inteligentny napastnik może stworzyć dokument, który pasuje do tego, który już masz, jest to poważny problem i powinieneś uzyskać lepszy skrót; jeśli martwisz się, że inteligentny napastnik może stworzyć dwa identyczne dokumenty, nie martw się: na pewno się zdarzy.

— Malvolio

Oczywiście, chociaż generowanie kolizji skrótu MD5 jest teoretycznie możliwe, generowanie użytecznej kolizji (jak w, plik kolizji jest tego samego typu, a jego zawartość jest co najmniej wiarygodna) jest o wiele trudniejszy ...

— Shadur

@Shadur: Tak było kiedyś, ale trwające badania bezpieczeństwa odkryły nowe sposoby generowania kolizji MD5, które to ułatwiają. W szczególności, jeśli Twój format pliku pozwala na fragmenty danych „komentujących” w dowolnym formacie, możesz dopasować dowolny skrót MD5, wstawiając odpowiedni komentarz.

— MSalters

Skrót MD5 składa się ze 128 bitów. Pojedynczy przerzucony bit w źródle przerzuca (średnio) 64 bity w haszu.

Prawdopodobieństwo przypadkowego zderzenia dwóch skrótów wynosi 1/2 ^ 128, co stanowi 1 na 340 undecillion 282 decylion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quillillion 374 quillion 607 bilionów 431 miliardów 768 milionów 211 tysięcy 456.

Jeśli jednak zachowasz wszystkie wartości skrótu, dzięki paradoksowi urodziny prawdopodobieństwo jest nieco wyższe. Aby mieć 50% szans na zderzenie dowolnego skrótu, potrzebujesz 2 ^ 64 skrótów. Oznacza to, że aby uzyskać kolizję, średnio trzeba będzie mieszać 6 miliardów plików na sekundę przez 100 lat.

Źródło: porneL, /programming/201705/how-many-random-elements-before-md5-produces-collisions

— Zsolt Szilagy
źródło

Więc mówisz, że wciąż jest szansa? : p

— Holloway,

Problem polega na tym, że chociaż POTRZEBUJESZ mieszać 6 miliardów plików na sekundę przez 100 lat, aby mieć pewność, że znajdziesz kolizję; może się to zdarzyć w ciągu pierwszej sekundy.

— deroby

To prawda, że może się to zdarzyć w pierwszej sekundzie. Ale jak zawsze chodzi o przyczyny równoważenia. Mogą to być zastosowania wojskowe, w których ryzyko to jest nie do przyjęcia, ale wynajmowałbym samochód bez zastanowienia, gdzie czujniki poduszek powietrznych używają md5. Pamiętaj, że istnieje prawdopodobieństwo, że zostaniesz trafiony piorunem wiele razy, czekając na kolizję MD5.

— Zsolt Szilagy

Przykro mi, ale połowa 2 ^ 128 to 2 ^ 127, a nie 2 ^ 64.

— fischi

@fischi, przeczytaj link na temat paradoksu urodzinowego, a także en.wikipedia.org/wiki/Birthday_attack - nie jest to po prostu zmniejszenie o połowę całkowitej liczby skrótów. Biorąc pod uwagę przestrzeń poszukiwań H, liczba skrótów, które musisz wygenerować przed uzyskaniem 50% szansy na kolizję, to w przybliżeniu sqrt ((pi / 2) * H). Jeśli wykonasz tę matematykę za pomocą 2 ^ 128, otrzymasz liczbę około 2 ^ 64

— Paul Dixon