Czy MD5 jest nadal wystarczająco dobry, aby jednoznacznie identyfikować pliki?

139

Czy haszowanie pliku MD5 jest nadal uważane za wystarczająco dobrą metodę jednoznacznego identyfikowania go, biorąc pod uwagę wszystkie łamanie algorytmu MD5, problemy z bezpieczeństwem itp.? Bezpieczeństwo nie jest tutaj moim głównym zmartwieniem, ale unikalna identyfikacja każdego pliku tak.

jakieś pomysły?

Ranhiru Jude Cooray
źródło
2
Obecnie sam go używam w jednej z moich aplikacji i, o ile wiem, jest to wystarczająco dobre, aby jednoznacznie identyfikować pliki.
Niedostępne
2
Prawdopodobnie okaże się przydatne to pytanie: stackoverflow.com/questions/862346/ ...
ostry ząb
Ile plików musisz zidentyfikować? Wyprowadza 128 bitów, więc jeśli próbujesz zidentyfikować kilka tysięcy plików, jest w porządku. Ale jeśli próbujesz zidentyfikować znacznie więcej, możesz wpaść na kolizje / paradoks urodzin.
Marcin
Będą to pliki graficzne, jpg, png i gif. I tak, myślę, że limit wynosiłby kilka tysięcy ... Ale jak myślisz z grubsza, ile plików przysporzy mi kłopotów?
Ranhiru Jude Cooray

Odpowiedzi:

89

Tak. MD5 został całkowicie zerwany z punktu widzenia bezpieczeństwa, ale prawdopodobieństwo przypadkowej kolizji jest nadal znikomo małe. Upewnij się tylko, że pliki nie są tworzone przez osobę, której nie ufasz i która może mieć złośliwe zamiary.

Marcelo Cantos
źródło
2
@none: Twoje pierwsze pytanie znajdziesz tutaj . Obawiam się, że nie rozumiem innych pytań.
Marcelo Cantos
9
@ 0xA3: Ani ty, ani ja nie mamy pojęcia, do jakich plików odnosi się OP, ani jak wiele szkód spowodowałby kompromis. To mogłaby być kolekcja zdjęć ich dzieci dla wszystkich, co wiemy. Moim celem jest przedstawienie faktów; to, co robi z nimi ktoś inny, to ich sprawa. Weź również pod uwagę, że Bruce Schneier zaleca zapisanie swojego hasła; nie wszystko musi być przechowywane w Fort Knox. Niektóre rzeczy będą się dobrze trzymać pod doniczką.
Marcelo Cantos
3
@Marcelo Cantos, myślę, że to, czego tu brakuje, to rozróżnienie lub rozpakowanie terminu „bezpieczeństwo”. Oczywiście ludzie zakładają „bezpieczeństwo” przy każdym użyciu sum kontrolnych, ale nomenklatura, którą Marcelo prawdopodobnie oznacza „w laboratorium”.
hpavc
5
Zdecydowanie się nie zgadzam. Inna wartość skrótu oznacza, że ​​pliki są różne. Ale dla równej wartości skrótu: nie możesz powiedzieć „jest wysoce prawdopodobne, że oba są takie same”, jeśli skrót jest taki sam: możesz porównać tylko bajt po bajcie. Skrót jest o wiele rzędów wielkości mniejszy niż liczba różnych wartości w całym pliku, więc istnieje wiele, wiele, wiele możliwych kolizji dla każdej wartości skrótu. Tylko w przypadku kopiowania znanego pliku (ze znanym hashem) identyczna wartość skrótu „prawdopodobnie oznacza”, że druga została skopiowana poprawnie (nawet wtedy nie jest to w 100% pewne, ale bardzo prawdopodobne).
Olivier Dulac
3
OK, moja matematyka jest do niczego. Identyfikatory GUID mają około 122 bitów entropii, więc prawdopodobieństwo kolizji w dowolnym miejscu miliarda plików wynosi około 2 ^ (2 * 30 - 122) = 2 ^ -62. Chociaż jest to znacznie więcej niż moje pierwotne obliczenia, wciąż jest niewielkie i wynosi mniej więcej jeden na 4 kwintyliony.
Marcelo Cantos
32

Ze względów praktycznych utworzony hash może być odpowiednio losowy, ale teoretycznie zawsze istnieje prawdopodobieństwo kolizji, ze względu na zasadę Pigeonhole . Posiadanie różnych skrótów z pewnością oznacza, że ​​pliki są różne, ale uzyskanie tego samego skrótu niekoniecznie oznacza, że ​​pliki są identyczne.

Używanie funkcji skrótu do tego celu - bez względu na to, czy bezpieczeństwo jest problemem, czy nie - powinno zatem zawsze być tylko pierwszym krokiem sprawdzania, zwłaszcza jeśli wiadomo, że algorytm skrótu łatwo tworzy kolizje. Aby wiarygodnie stwierdzić, czy dwa pliki z tym samym hashem są różne, trzeba by porównać te pliki bajt po bajcie.

stapeluberlauf
źródło
16
@Ranhiru. Nie. Skrót daje wartość „podsumowania”, która (dla MD5) ma tylko 16 bajtów. Aby zagwarantować, że pliki są identyczne, musisz sprawdzić bajt po bajcie. Dzieje się tak bez względu na wybrany algorytm skrótu, zawsze istnieje możliwość kolizji.
PaulG
6
@Ranhiru. Przeczytaj jeszcze raz tę odpowiedź, jej imho najbardziej wyczerpującą tutaj. Haszowanie może być użyte jako pierwszy krok, który daje 99,99% pewności, że pliki są identyczne, ale jeśli chcesz mieć absolutną 100% pewność, musisz sprawdzić bajt po bajcie. Dzieje się tak niezależnie od tego, czy używasz algorytmu MD5, SHA, czy innego.
PaulG
7
Ta odpowiedź jest błędna. Zapobieganie fałszowaniu i weryfikacja niepowtarzalności to to samo. Ponadto, chociaż haszowanie nie gwarantuje wyjątkowości, podobnie jak rzeczywiste porównanie. W rzeczywistości prawdopodobieństwo przypadkowego zderzenia skrótu jest w rzeczywistości mniejsze niż prawdopodobieństwo niepowodzenia porównania z powodu usterek procesora generowanych przez normalną emisję słonecznego promieniowania gamma. I nie zapominaj, że często jedyne źródło pliku znajduje się po drugiej stronie świata na serwerze sieciowym, a jedyną niezależną informacją, którą masz do celów porównawczych, jest hash.
Marcelo Cantos
8
@Marcelo. Nie można logicznie rozumować, że przypadkowa kolizja jest mniej prawdopodobna niż przypadkowe przerzucenie bitów (podczas porównywania bajt po bajcie). Nadal masz taką samą szansę na przerzucanie bitów podczas tworzenia skrótu (i prawdopodobnie więcej, ponieważ wymaga to więcej czasu przetwarzania). @Thomas początkowo podniósł tę kwestię, sugerując, że nie ma gwarantowanego sposobu identyfikacji wyjątkowości, chociaż wpływ przerzutów bitów jest wysoce dyskusyjny. Najbardziej pesymistyczne oszacowanie to 1 przerzucenie na GB / godzinę, a pamięć RAM ECC usunęłaby nawet to.
PaulG
2
„prawdopodobieństwo przypadkowego zderzenia skrótu jest w rzeczywistości mniejsze niż prawdopodobieństwo niepowodzenia porównania z powodu usterek procesora generowanych przez normalną emisję promieniowania gamma słonecznego” [potrzebne źródło]
endolit
20

MD5 wystarczy, jeśli nie masz przeciwnika. Jednak ktoś może (celowo) utworzyć dwa oddzielne pliki, które mają tę samą wartość (co nazywa się kolizją), co może, ale nie musi, stanowić problem, w zależności od konkretnej sytuacji.

Ponieważ wiedza o tym, czy znane słabości MD5 mają zastosowanie w danym kontekście, jest subtelną sprawą, nie zaleca się używania MD5. Bezpieczną odpowiedzią jest użycie odpornej na kolizje funkcji skrótu (SHA-256 lub SHA-512). Ponadto używanie MD5 to zły public relations (jeśli używasz MD5, bądź przygotowany na to, że będziesz musiał się usprawiedliwiać; podczas gdy nikt nie będzie kwestionował twojego używania SHA-256).

Thomas Pornin
źródło
2
Ta odpowiedź może być nieco myląca, jeśli czytelnik nie jest zbyt zaznajomiony z haszowaniem. Nie ma nic magicznego w SHA, co zapobiega kolizjom hash, są po prostu bardziej odporne na ataki kolizji hash . Jeśli chcesz mieć więcej niż 99,999 ^ e% pewności, że pliki są identyczne, nadal potrzebujesz sprawdzania bajt po bajcie.
PaulG
7
W rzeczywistości porównanie bajtu do bajtu może się nie powieść z powodu odbicia promienia kosmicznego (np. Przekształcenia a return 0;w a return 1;). Jest to mało prawdopodobne, ale ryzyko kolizji z SHA-256 jest jeszcze mniejsze. Z matematycznego punktu widzenia nie można być pewnym, że dwa pliki, które mają skrót do tej samej wartości, są identyczne, ale nie można być tego pewnym, porównując same pliki, o ile do porównania używasz komputera. Chodzi mi o to, że nie ma sensu wychodzenie poza jakieś 99,999 .... 9% pewności, a SHA-256 już zapewnia więcej.
Thomas Pornin,
2
Co, nie używasz pamięci ECC? ;). Dobry komentarz, bardzo ciekawe przemyślenia.
PaulG,
1
Nie zapomnij o kapeluszu z cynowanej folii! A poważniej, skąd znasz te faktoidy dotyczące kolizji i czy w jakiś sposób to zweryfikowałeś?
James P.
@ThomasPornin Przerzuty bitów promieniem kosmicznym wpłynęłyby również na metodę MD5, więc jest jeszcze gorzej.
endolit
9

MD5 może powodować kolizje. Teoretycznie, choć jest to bardzo mało prawdopodobne, milion plików z rzędu może wygenerować ten sam hash. Nie testuj swojego szczęścia i sprawdzaj kolizje md5 przed zapisaniem wartości.

Osobiście lubię tworzyć md5 z losowych ciągów, co zmniejsza narzut związany z haszowaniem dużych plików. Po znalezieniu kolizji wykonuję iterację i ponownie haszuję z dołączonym licznikiem pętli.

Możesz przeczytać o zasadzie szufladki .

afilina
źródło
6

Nie polecałbym tego. Gdyby aplikacja działała w systemie wieloużytkownikowym, mógłby być użytkownik, który miałby dwa pliki z tym samym hashem md5 (może być inżynierem i bawić się takimi plikami lub być po prostu ciekawy - można je łatwo pobrać z http: / /www2.mat.dtu.dk/people/S.Thomsen/wangmd5/samples.html , sam podczas pisania tej odpowiedzi pobrałem dwie próbki). Inną rzeczą jest to, że niektóre aplikacje mogą przechowywać takie duplikaty z dowolnego powodu (nie jestem pewien, czy istnieją takie aplikacje, ale istnieje taka możliwość).

Jeśli jednoznacznie identyfikujesz pliki wygenerowane przez twój program, powiedziałbym, że możesz użyć MD5. W przeciwnym razie poleciłbym każdą inną funkcję skrótu, w której nie są jeszcze znane żadne kolizje.

tach
źródło
2

Osobiście uważam, że ludzie używają surowych sum kontrolnych (wybierz swoją metodę) innych obiektów, aby działać jako unikalne identyfikatory o wiele za dużo, kiedy naprawdę chcą mieć unikalne identyfikatory. Pobieranie odcisków palców do tego celu nie było intencją i prawdopodobnie będzie wymagało więcej myślenia niż użycie płynu lub podobnego mechanizmu integralności.

hpavc
źródło
0

MD5 jest uszkodzony, zamiast tego można użyć SHA1 (zaimplementowany w większości języków)

Guillaume Lebourgeois
źródło
To jest bardzo dobra odpowiedź. MD5 jest niedopuszczalne w przypadkach użycia w prawie i rachunkowości w Europie od maja 2018 r.
Bert Sinnema
@BertSinnema czy mógłbyś wskazać mi źródło, które definiuje, które funkcje skrótu są dopuszczalne itp.?
berezovskyi
@GregSchmit może dlatego, że OP nie dbał o siłę kryptograficzną jako taką. Zrozumiałem pytanie jako „Używam już MD5 w kontekście niezwiązanym z zabezpieczeniami, czy muszę poświęcić czas na aktualizację kodu?” rodzaj rzeczy. W tym kontekście odpowiedź była prawdopodobnie zła i od tamtej pory SHA1 również nie działa.
berezovskyi
0

Podczas mieszania krótkich (<kilku K?) Łańcuchów (lub plików) można utworzyć dwa klucze mieszające md5, jeden dla rzeczywistego ciągu, a drugi dla rewersu ciągu połączonego z krótkim asymetrycznym ciągiem. Przykład: md5 (reverse (string || '1010')). Dodanie dodatkowego ciągu gwarantuje, że nawet pliki składające się z serii identycznych bitów generują dwa różne klucze. Proszę zrozumieć, że nawet w tym schemacie istnieje teoretyczna szansa, że ​​dwa klucze haszujące będą identyczne dla nieidentycznych ciągów, ale prawdopodobieństwo wydaje się niezwykle małe - coś w kolejności kwadratu prawdopodobieństwa kolizji pojedynczego md5 i oszczędność czasu może być znaczny, gdy liczba plików rośnie. Można również rozważyć bardziej rozbudowane schematy tworzenia drugiego ciągu,

Aby sprawdzić, czy nie występują kolizje, można uruchomić ten test na unikalność kluczy skrótu md5 dla wszystkich wektorów bitów w bazie danych:

wybierz md5 (bit_vector), count (*), bit_and (bit_vector) z db z
grupą bit_vector według md5 (bit_vector), bit_vector posiadający bit_and (bit_vector) <> bit_vector

marcopolo
źródło
Sprytny pomysł. Jeśli „atakujący” utworzy fałszywy plik z tym samym hashem md5, nic to nie pomoże, chyba że zna twoje „solenie”, a odwrócenie zawartości utworzyłoby inny hash. Korzystanie z 2 kluczy md5 w ten sposób znacznie zmniejszyłoby szanse. Jeśli tylko zapobiegnie „atakowi” przy użyciu soli przed obliczeniem lokalnym, wystarczy.
Wolf5
0

Lubię myśleć o MD5 jako wskaźniku prawdopodobieństwa podczas przechowywania dużej ilości danych w plikach.

Jeśli skróty są równe, wiem, że muszę porównywać pliki bajt po bajcie, ale może się to zdarzyć tylko kilka razy z fałszywego powodu, w przeciwnym razie (skróty nie są równe) Mogę być pewien, że mówimy o dwóch różnych plikach .

Shimmy Weitzhandler
źródło