Czy identyczny kryptograficzny skrót lub suma kontrolna dla dwóch plików oznacza, że ​​są one identyczne?

57

Mam 2 dokumenty programu Excel i chcę sprawdzić, czy są dokładnie takie same, oprócz nazwy pliku.

Na przykład pliki są nazywane fileone.xlsi filetwo.xls. Oprócz nazw plików zakłada się, że ich zawartość jest identyczna, ale to chcę sprawdzić.

Szukałem sposobów na sprawdzenie tego i bez instalowania wielu wtyczek. Nie ma prostej drogi.

Próbowałem wygenerować skróty MD5 dla obu plików. Kiedy skróty są identyczne, czy to oznacza, że ​​zawartość pliku jest taka sama 1: 1?

sam
źródło
8
szyfrowanie, a czasem nawet zwykłe skróty mogą być przydatne do porównywania plików w różnych systemach lub wyszukiwania dużej liczby plików, ale jeśli dwa pliki znajdują się w tym samym systemie, możesz je łatwo porównać z cmpsystemem Unix lub fc(porównanie plików) w systemie Windows.
dave_thompson_085
10
shattered.io - SHA1 jest „silniejszym” algorytmem mieszającym niż md5 i nadal jest shattered.io/static/shattered-1.pdf i shattered.io/static/shattered-2.pdf mają tę samą wartość skrótu, a jednocześnie są zupełnie inne.
mucha styropianowa
30
Uwaga dodatkowa: najpierw sprawdź ich rozmiary. Jeśli mają różne rozmiary, nie zawracaj sobie głowy otwieraniem plików, są różne.
Emilio M Bumachar,
42
Wersja uproszczona: skrót MD5 jest wystarczająco dobry, aby chronić przed wypadkiem , nie jest wystarczająco dobry, aby zapobiec złośliwemu programowi . Czy to ci wystarczy, musisz podjąć decyzję na podstawie swoich okoliczności.
Euro Micelli,
9
diff -s file1 file2jeśli mówi, że są identyczne, są identyczne (faktycznie porównuje pliki bajt po bajcie, więc wykluczone są nawet kolizje mieszające). sumy kontrolne są używane, gdy masz tylko jeden skrót i element, który uważa się za identyczny z autorem tego skrótu.
Bakuriu

Odpowiedzi:

93

Kiedy skróty są identyczne, czy to oznacza, że ​​zawartość pliku jest taka sama 1: 1?

Wszystkie pliki są zbiorem bajtów (wartości 0–255). Jeśli dwa pliki skrótów MD5 są zgodne, oba zbiory bajtów są bardzo prawdopodobne dokładnie takie same (ta sama kolejność, te same wartości).

Istnieje bardzo mała szansa, że ​​dwa pliki mogą wygenerować ten sam MD5, czyli 128-bitowy skrót. Prawdopodobieństwo to:

Prawdopodobieństwo przypadkowego zderzenia tylko 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 quillillion 607 bilionów 431 miliardów 768 milionów 211 tysięcy 456. (z odpowiedzi na StackOverflow ).

Skróty mają działać w „tylko jednym kierunku” - tzn. Bierzesz zbiór bajtów i dostajesz skrót, ale nie możesz wziąć skrótu i ​​odzyskać zbiór bajtów.

Kryptografia zależy od tego (w ten sposób można porównać dwie rzeczy bez wiedzy, co to są.)

Około roku 2005 odkryto metody pobierania skrótu MD5 i tworzenia danych pasujących do tego skrótu, aby utworzyć dwa dokumenty, które miały ten sam skrót MD5 ( atak kolizyjny ). Zobacz komentarz @ user2357112 poniżej. Oznacza to, że osoba atakująca może utworzyć na przykład dwa pliki wykonywalne, które mają ten sam MD5, a jeśli zależysz od MD5 w celu ustalenia, któremu zaufać, zostaniesz oszukany.

Dlatego MD5 nie powinien być używany do kryptografii lub bezpieczeństwa. Na przykład źle jest opublikować MD5 na stronie pobierania, aby zapewnić integralność pobierania. W zależności od skrótu MD5 nie wygenerowałeś się, aby sprawdzić, czy zawartość pliku lub danych jest tym, czego chcesz uniknąć.

Jeśli wygenerujesz własny, wiesz, że nie jesteś wobec siebie złośliwy (mam nadzieję). Tak więc do użytku jest w porządku, ale jeśli chcesz, aby ktoś inny mógł go odtworzyć i chcesz publicznie opublikować skrót MD5, należy użyć lepszego skrótu.


Należy pamiętać, że dwa pliki Excel mogą zawierać te same wartości w tych samych wierszach i kolumnach, ale bajt pliku może być zupełnie inny z powodu różnych formatów, stylów, ustawień itp.

Jeśli chcesz porównać dane w pliku, najpierw wyeksportuj je do pliku CSV z tymi samymi wierszami i kolumnami, aby usunąć całe formatowanie, a następnie haszować lub porównać pliki CSV.

LawrenceC
źródło
107
Pliki programu Excel i inne dokumenty biurowe mogą również mieć różne wartości skrótu, ponieważ zostały one otwarte i ponownie zapisane bez zmiany niczego, ponieważ metadane w pliku mają tam nową wartość przechowywaną dla ostatniej zapisanej daty i godziny.
BeowulfNode42
29
Bonus: jeśli eksportowałeś do CSV, możesz użyć czcigodnego difflub podobnego narzędzia, aby faktycznie potwierdzić, że pliki są bajt po bajcie identyczne, a nie tylko mieć ten sam skrót.
Monty Harder
18
Wykonywanie skrótu i ​​tworzenie danych pasujących do skrótu jest atakiem przedobrazowym. Uważam, że MD5 jest obecnie podatny na ataki kolizyjne, ale nie sądzę, aby ataki typu preimage lub Second -image były obecnie wykonalne.
user2357112
2
@ Tymczas co mówisz? Powiedział: wyeksportuj je do CSV i użyj, diff -saby sprawdzić, czy CSV są identyczne. W rzeczywistości możesz diff -snawet pliki Excela: jeśli diffmówi, że są identyczne, nie musisz przechodzić do porównania CSV.
Bakuriu
2
@ Bakuriu Najwyraźniej mój komentarz był bardzo źle sformułowany - miałem na myśli, że eksport do CSV spowoduje utratę wielu informacji - zwłaszcza formuł, wykresów, formatowania warunkowego i standardowego.
Tim
37

W praktyce tak, identyczny skrót kryptograficzny oznacza, że ​​pliki są takie same, o ile pliki nie zostały spreparowane przez osobę atakującą lub inną złośliwą jednostkę. Szanse na przypadkowe kolizje z dowolną dobrze zaprojektowaną funkcją skrótu kryptograficznego są tak małe, że są nieistotne w praktyce i przy braku aktywnego atakującego.

Ogólnie jednak nie, nie możemy powiedzieć, że dwa dowolne pliki posiadające ten sam skrót zdecydowanie oznaczają, że są one identyczne.

Sposób działania funkcji skrótu kryptograficznego polega na pobieraniu danych wejściowych o dowolnej długości i wyprowadzaniu wartości wejściowej o stałej długości obliczonej na podstawie danych wejściowych. Niektóre funkcje skrótu mają wiele długości wyjściowych do wyboru, ale dane wyjściowe nadal są w pewnym stopniu wartością o stałej długości. Wartość ta może wynosić do kilkudziesięciu bajtów; Algorytmy mieszające o najdłuższej obecnie powszechnie używanej wartości wyjściowej mają 512-bitową moc wyjściową, a 512-bitowa moc wyjściowa to 64 bajty.

Jeśli wejście funkcji skrótu jest dłuższe niż wyjście funkcji skrótu, należy usunąć pewną wierność, aby dopasować dane wejściowe do wyniku. W związku z tym musi istnieć wiele danych wejściowych o długości większej niż długość danych wyjściowych, które generują takie same dane wyjściowe.

Weźmy jako przykład obecny koń pociągowy, SHA-256. Wysyła skrót 256 bitów lub 32 bajty. Jeśli masz dwa pliki o długości dokładnie 32 bajtów, ale różne, powinny one (zakładając brak błędów w algorytmie) mieszać różne wartości, bez względu na zawartość plików; pod względem matematycznym skrót jest funkcją odwzorowującą 2 256 przestrzeni wejściowej na 2 256 przestrzeni wyjściowej, co powinno być możliwe bez kolizji. Jednakże, jeśli masz dwa pliki, które są długo każde 33 bajtów, musi istnieć jakiś kombinacji wejść, które dają ten sam 32-bajtowy wartość hash wyjście dla obu plików, ponieważ jesteśmy teraz odwzorowanie 2 264 miejsca wejścia na o 2 256przestrzeń wyjściowa; tutaj możemy łatwo zauważyć, że średnio powinno być 2 8 wejść dla każdego wyjścia. Przejdźmy dalej, a przy plikach 64-bajtowych powinno być 2 256 wejść dla każdego wyjścia!

Kryptograficzne funkcje skrótu są tak zaprojektowane, że obliczeniowo trudno jest skomponować dane wejściowe, które dają określone dane wyjściowe, lub skomponować dwa dane wejściowe, które dają takie same dane wyjściowe. Jest to znane jako preimage resistance odporność lub ataku kolizja oporu . Nie jest niemożliwe znalezienie takich kolizji; po prostu ma być naprawdę, bardzo, bardzo, bardzo trudny. (Trochę szczególnym przypadkiem ataku kolizyjnego jest atak urodzinowy ).

Niektóre algorytmy są lepsze od innych w przeciwstawianiu się atakującym. MD5 jest obecnie ogólnie uważany za całkowicie zepsuty, ale ostatnio spojrzałem, nadal miał całkiem niezłą odporność na pierwszy obraz . SHA-1 jest podobnie skutecznie łamany; ataki preimage zostały wykazane, ale wymagają określonych warunków, choć nie ma powodu, aby sądzić, że tak będzie w nieskończoność; jak mówi przysłowie, ataki zawsze się poprawiają, nigdy się nie pogarszają. SHA-256/384/512 są obecnie nadal uważane za bezpieczne dla większości celów. Jeśli jednak chcesz tylko sprawdzić, czy dwa nie-złośliwie spreparowane, prawidłowepliki są takie same, to każdy z nich powinien być wystarczający, ponieważ przestrzeń wejściowa jest już wystarczająco ograniczona, aby najbardziej interesowały Cię losowe kolizje. Jeśli masz powód, by sądzić, że pliki zostały spreparowane złośliwie, musisz przynajmniej użyć kryptograficznej funkcji skrótu, która jest obecnie uważana za bezpieczną, co stawia dolny pasek na SHA-256.

Pierwszym przykładem jest znalezienie danych wejściowych, które dają określoną wartość skrótu wyjściowego; drugim obrazem jest znalezienie jednego wejścia, które daje takie samo wyjście, jak inne, określone wejście; kolizja polega na znalezieniu dwóch danych wejściowych, które dają takie same dane wyjściowe, bez względu na to, co to jest, a czasami bez względu na to, jakie są dane wejściowe.

To powiedziawszy, ważne jest, aby pamiętać, że pliki mogą mieć bardzo różne reprezentacje danych i nadal wyświetlać dokładnie to samo. Mogą więc wydawać się takie same, mimo że ich skróty kryptograficzne się nie zgadzają, ale jeśli skróty się zgadzają, bardzo prawdopodobne jest, że będą takie same.

CVn
źródło
2
Jeśli skróty są zgodne, wówczas albo pliki są wynikiem celowej kolizji, albo nie są, a gwarantujemy, że będą takie same. Prawdopodobieństwo przypadkowego zderzenia jest czysto teoretyczne. Mówienie, że „jeśli skróty się zgadzają, najprawdopodobniej będą wyglądać tak samo” jest mylące: jeśli dochodzi do złośliwości i jest to sytuacja kolizyjna, prawdopodobnie nie będą one takie same, a w przeciwnym razie prawdopodobieństwo wynosi zero, to nie jest jakieś zdarzenie o niskim prawdopodobieństwie, przed którym należy się bronić.
Gilles „SO- przestań być zły”
9
@Gilles: Przeciwnie. Sformułowanie Michaela jest dokładnie poprawne, a „gwarantowane” wprowadza w błąd (lub, cóż, faktycznie błędne). Prawdopodobieństwo, że dwa pliki z identycznymi skrótami nie pasują do siebie (pomimo złośliwej modyfikacji) jest bardzo niskie i można je w praktyce pominąć. Nie jest to jednak zero . Jest ogólnie szansa, że z jakiegoś powodu różnych wejść będzie produkować ten sam hash, a być może nawet z prawdopodobieństwem znacznie wyższa niż 2 ^ -128 (algorytmy kryptograficzne są czarne Sztuki, algortihm mogą być wadliwe w subtelny sposób i nieznani nie jesteśmy w stanie być w 100% pewni).
Damon
5
@Gilles „ efektywnie zero ” wciąż nie jest równe zero , co oznacza, że ​​istnieje pewne (co prawda niewielkie) prawdopodobieństwo, że dwa różne zestawy danych spowodują ten sam skrót. Nie możesz się z tym sprzeczać.
Attie
5
@Attie: Prawdopodobieństwo skrócenia dwóch niepowiązanych plików do tej samej wartości jest znacznie poniżej prawdopodobieństwa wielu innych rzeczy, które mogą pójść nie tak (np. Błędy bitów losowych powodujące uszkodzenie plików na dysku), że nie warto chronić się przed przypadkowymi dopasowaniami. Ochrona przed celowo zaprojektowanymi meczami może być opłacalna, ale przypadkowe mecze są tak nieprawdopodobne, że każdy wysiłek włożony w ochronę przed nimi może być lepiej wydany gdzie indziej.
supercat
3
@ Gilles źle. Nie możesz jednym tchem powiedzieć, że istnieje szansa, bez względu na to, jak niewielka jest twoja ocena, że ​​może dojść do przypadkowej kolizji, to w następnej stypendium nie może dojść do kolizji. Mówienie to jest bardzo mylące, ponieważ implikuje właściwość algorytmu haszującego, o którym wiadomo, że jest całkowicie fałszywa.
iheanyi
10

To gra prawdopodobieństwa ... skróty mogą reprezentować skończoną liczbę wartości.

Jeśli weźmiemy pod uwagę hipotetyczny (i bardzo słaby) 8-bitowy algorytm mieszający, wówczas może to reprezentować 256 różnych wartości. Gdy zaczniesz uruchamiać pliki za pomocą algorytmu, zaczniesz wyrzucać skróty ... ale wkrótce zaczniesz widzieć „ kolizje skrótów ”. Oznacza to, że do algorytmu zostały wprowadzone dwa różne pliki, które wygenerowały tę samą wartość skrótu co wynik. Oczywiście tutaj skrót nie jest wystarczająco silny i nie możemy twierdzić, że „ pliki z dopasowanymi skrótami mają tę samą zawartość ”.

Zwiększenie rozmiaru skrótu i ​​użycie silniejszych algorytmów szyfrowania kryptograficznego może znacznie pomóc w ograniczeniu kolizji i zwiększyć naszą pewność, że dwa pliki z tym samym skrótem mają tę samą zawartość.

To powiedziawszy, nigdy nie możemy osiągnąć 100% pewności - nigdy nie możemy twierdzić , że dwa pliki z tym samym hashem naprawdę mają tę samą zawartość.

W większości / wielu sytuacjach jest to w porządku, a porównywanie skrótów jest „ wystarczająco dobre ”, ale zależy to od modelu zagrożenia.

Ostatecznie, jeśli musisz podnieść poziomy pewności, zalecam wykonanie następujących czynności:

  1. Używaj silnych algorytmów mieszających ( MD5 nie jest już uważany za odpowiedni, jeśli chcesz chronić się przed potencjalnie złośliwymi użytkownikami)
  2. Użyj wielu algorytmów mieszających
  3. Porównaj rozmiar plików - dodatkowy punkt danych może pomóc w identyfikacji potencjalnych kolizji, ale zauważ, że demonstrowana kolizja MD5 nie musiała zmieniać długości danych.

Jeśli musisz być w 100% pewien, to na pewno zacznij od skrótu, ale jeśli skróty pasują, kontynuuj porównanie bajtów po bajcie dwóch plików.


Ponadto, jak zauważyli inni ... złożoność dokumentów tworzonych przez aplikacje takie jak Word i Excel oznacza, że ​​tekst, liczby i widoczny układ mogą być takie same, ale dane przechowywane w pliku mogą być inne.

Excel jest w tym szczególnie zły - po prostu otwierając arkusz kalkulacyjny zapisując go ( nic nie robiąc ), możesz utworzyć nowy plik o innej zawartości.

Attie
źródło
6
MD5 nie jest już uważane za odpowiednie, jest bardzo prawdziwe pod względem kryptograficznym, ale do sprawdzania unikalności (w przypadku braku złośliwości, np. Jeśli kontrolujesz dane wejściowe), jest przyjemne i szybkie (a 128 bitów powinno wystarczyć)
Chris H
4
kontynuuj porównanie bajtów po bajcie dwóch plików. ” Jeśli masz zamiar dokonać porównania plików, równie dobrze możesz to zrobić najpierw ... nie ma sensu czytać wszystkich plików, aby obliczyć ich hashe, aby ponownie odczytać oba pliki, aby je porównać!
TripeHound
3
@TripeHound To zależy, czy pliki są zarówno lokalne, czy nie ... jeśli masz już skrót jednego i wprowadzasz nowy plik do systemu, jeśli nowy plik i tak wymaga skrótu przechowywanego w bazie danych itp. Wykonaj połączenie, które pasuje do Twojej sytuacji.
Attie
5
Nie, to nie jest gra prawdopodobieństwa. Nie doceniasz, jak mało prawdopodobne jest przypadkowe zderzenie. To się po prostu nie zdarzy. Odwrócenie nieco podczas porównania jest bardziej prawdopodobne. Z drugiej strony, w niektórych scenariuszach może dojść do celowej kolizji, co wcale nie jest grą prawdopodobieństwa.
Gilles „SO- przestań być zły”
3
@mbrig: 32-bitowy skrót miałby znaczne ryzyko przypadkowego niedopasowania. Jednak przejście do 128 lub 256 bitów robi ogromną różnicę. Przy 128 bitach miliard małp, z których każdy wpisuje miliard autentycznie losowych dokumentów o przyzwoitych rozmiarach, miałby około 0,3% szansy na utworzenie dwóch dokumentów z tym samym hashem. Przy 256 bitach, nawet gdyby miliardy małp mogły pisać miliard losowych dokumentów na sekundę przez miliard lat, prawdopodobieństwo, że którykolwiek z tych niewielu dokumentów będzie miał przypadkowo dopasowane wartości skrótu, byłoby znikomo małe.
supercat
6

Jeśli dwa pliki mają ten sam skrót MD5 i oba nie zostały specjalnie spreparowane, to są one identyczne. Jak trudno jest tworzyć pliki z tym samym hashem MD5, zależy od formatu pliku, nie wiem, jak łatwo jest z plikami Excel.

Więc jeśli masz własne pliki, które po prostu leżą i chcą znaleźć duplikaty, MD5 jest bezpieczny. Jeśli napisałeś jeden z plików, a drugi plik ma podejrzane pochodzenie, MD5 jest nadal bezpieczny (jedynym sposobem na uzyskanie różnych plików z tą samą sumą kontrolną MD5 jest utworzenie obu plików). Jeśli ktoś, komu nie ufasz, prześle Ci propozycję budżetu, a później wyśle ​​inny plik, który, jak twierdzą, jest taki sam, MD5 może nie wystarczyć.

Aby uniknąć ryzyka, użyj SHA-256 lub SHA-512 zamiast MD5. Jeśli dwa pliki mają taki sam skrót SHA-256, to są one identyczne. To samo dotyczy SHA-512. (Istnieje teoretyczna możliwość, że mogą być różne, ale prawdopodobieństwo tego przypadkowego zdarzenia jest o wiele mniejsze niż prawdopodobieństwo, że Twój komputer trochę się przewróci podczas weryfikacji, niż to po prostu nie ma znaczenia. Jeśli chodzi o kogoś, kto celowo tworzy dwa pliki za pomocą ten sam skrót, nikt nie wie, jak to zrobić dla SHA-256 lub SHA-512).

Jeśli dwa pliki Excel mają różne skróty, to są różne, ale nie ma sposobu, aby dowiedzieć się, jak bardzo się różnią. Mogą mieć identyczne dane, ale różne formatowanie, mogą po prostu różnić się właściwościami lub mogą zostać zapisane w różnych wersjach. W rzeczywistości, jeśli Excel przypomina Worda, to samo zapisanie pliku aktualizuje jego metadane. Jeśli chcesz tylko porównać dane liczbowe i tekstowe oraz zignorować formatowanie i właściwości, możesz wyeksportować arkusze kalkulacyjne do pliku CSV, aby je porównać.

Jeśli masz dostępne narzędzia Unix / Linux, możesz użyć cmpdo porównania dwóch plików. Aby porównać dwa pliki na tym samym komputerze, sumy kontrolne tylko komplikują sprawę.

Gilles „SO- przestań być zły”
źródło
Jeśli dwa pliki mają ten sam skrót MD5 i oba nie zostały specjalnie spreparowane, to są one identyczne. To jest niepoprawne Istnieje nieskończona liczba możliwych wiadomości, ale jest tylko 2 ^ 64 możliwych 64-bitowych skrótów. Nazywa się to „zasadą szuflady” : „zasada szuflady mówi, że jeśli nprzedmioty są wkładane do mpojemników n > m, to co najmniej jeden pojemnik musi zawierać więcej niż jeden przedmiot”. Jeśli utworzysz więcej niż 2 ^ 64 wiadomości, będziesz mieć kolizje bez żadnego „specjalnego tworzenia”. I możesz mieć tylko 2 lata
Andrew Henle
@AndrewHenle, MD5 nie ma 64 bitów, to 128. Jeśli wygenerowanie przypadkowej kolizji wpędzi nas w ramy czasowe śmierci-ciepła-wszechświata, jest to „możliwe” tylko w przypadku bardzo akademickiej (stąd bezużytecznej) definicji.
Charles Duffy
@CharlesDuffy Zakładasz, że skrót jest losowo dystrybuowany. To nie jest.
Andrew Henle
Skuteczne równoważenie losowej dystrybucji jest częścią definicji dobrego kryptograficznego skrótu - masz wiele rund mieszania z jakiegoś powodu. Oczywiście istnieją słabe algorytmy mieszania, ale skupienie się na tych słabościach prowadzi nas do wcześniej określonych zastrzeżeń dotyczących celowych ataków. (Czy mówisz, że wykazano, że MD5 ma tylko 64 bity, które są faktycznie losowe? Przyznam, że nie nadążałem, więc jest to prawdopodobne - proszę link?)
Charles Duffy
@AndrewHenle Nie twierdzę, że kolizja jest matematycznie niemożliwa, co byłoby błędne, ale tutaj nie ma znaczenia. Oświadczam, że tak się nie stało, co jest prawdą. Twój komentarz jest niepoprawny w sposób, który całkowicie zmienia ofertę. Możliwe są 2 ^ 128 możliwych skrótów MD5, a nie 2 ^ 64. Oznacza to, że musisz wygenerować 2 ^ 128 skrótów, aby mieć pewność, że wygenerujesz kolizję. W rzeczywistości, według paradoksu urodzinowego, 2 ^ 64 dałoby makroskopową szansę kolizji między wygenerowanymi skrótami (nie z wcześniej wygenerowanym skrótem). Ale jest to kwestia sporna, ponieważ wiemy, jak stworzyć kolizję.
Gilles „SO- przestań być zły”
6

Krótka odpowiedź: kryptograficzną hash ma pomóc Ci być rozsądnie pewni, że pliki z pasującymi mieszań są takie same. O ile nie zostały celowo spreparowane, szanse na dwa nieznacznie różne pliki o podobnych wartościach skrótu są absurdalnie małe. Ale jeśli chodzi o porównywanie i weryfikację plików, które mogłyby być celowo modyfikowane, MD5 jest złym wyborem. (Użyj innej funkcji skrótu, takiej jak SHA3 lub BLAKE2.)

Długa odpowiedź: idealna funkcja skrótu to taka, która tworzy prawie unikalny skrót kryptograficzny dla każdego unikalnego elementu danych. Innymi słowy, zdecydowanie wiemy, że w tym wszechświecie istnieją dwa pliki, których wartości mieszające się kolidują, szansa na naturalne połączenie tych dwóch plików jest absurdalnie mała.

Dziesięć lat temu zdecydowałem, że muszę trzymać się jak najdalej od MD5. (Oczywiście, aż do wczoraj pamiętałem zły powód, dla którego to robię; dziesięć lat to dużo czasu, rozumiesz. Ponownie odwiedziłem moje poprzednie notatki, aby zapamiętać dlaczego i zredagowałem tę odpowiedź.) Widzicie, w 1996 roku znaleziono MD5 być podatnym na ataki zderzeniowe. 9 lat później badacze byli w stanie stworzyć pary dokumentów PostScript i (ouch!) Certyfikatów X.509 z tym samym hasłem! MD5 był wyraźnie zepsuty. (Megaupload.com używało również MD5, a wokół kolizji haszujących było wiele cholernie chudych, co sprawiało mi wtedy problemy).

Doszedłem więc do wniosku, że chociaż MD5 był (i nadal jest) niezawodny w porównywaniu łagodnych plików, należy go całkowicie zaprzestać. Uznałem, że poleganie na nim może przerodzić się w pobłażanie i fałszywe zaufanie: gdy zaczniesz porównywać pliki za pomocą ich skrótów MD5, pewnego dnia zapomnisz o drobnym zabezpieczeniu i porównasz dwa pliki, które są celowo stworzone, aby mieć ten sam skrót. Ponadto mało prawdopodobne jest, aby procesory i procesory kryptograficzne dodawały obsługę tego systemu.

Oryginalny plakat ma jednak jeszcze mniej powodów, aby używać MD5, ponieważ:

  1. Tak długo, jak porównuje się tylko dwa pliki, porównanie bajt po bajcie jest w rzeczywistości szybsze niż generowanie własnych skrótów MD5. Dla porównania trzech lub więcej plików ... cóż, teraz masz uzasadnioną przyczynę.
  2. OP określił „sposoby na sprawdzenie tego i bez instalowania kilku wtyczek”. Polecenie Get-FileHash programu Windows PowerShell może generować skróty SHA1, SHA256, SHA384, SHA512 i MD5. Na nowoczesnych komputerach ze sprzętową obsługą funkcji skrótu SHA generowanie ich jest szybsze.

źródło
6
Możesz stworzyć własną kryptograficzną funkcję skrótu o dowolnej długości, prawda; ale wtedy ma ustaloną długość i zasada szuflady ma zastosowanie. Ogólna odpowiedź brzmi: „porównując tylko ich skróty, nie możesz być pewien, że oba pliki są identyczne”.
Kamil Maciorowski
2
@KamilMaciorowski Teoretycznie tak, mogę. Moja niestandardowa funkcja skrótu może po prostu wygenerować kopię największego pliku. Ale nie jestem zainteresowany dalszą dyskusją na ten temat; prawda jest taka, że ​​zlekceważyłeś z powodu, który sprowadza się do podstępu tylko po to, aby udowodnić, że jesteś mądrzejszy i to cię obróciło. Teraz nie możesz cofnąć głosu.
Zgadzam się z @KamilMaciorowski ... To jest gra prawdopodobieństwa ... używając jednego skrótu, możesz być „ dość pewny ”, że pliki z dopasowanymi skrótami są takie same, ale nie ma 100% gwarancji. Korzystanie z lepszych algorytmów lub stosowanie wielu algorytmów może zwiększyć twoją pewność siebie - nawet porównanie rozmiarów plików może pomóc ... ale nigdy nie możesz być w 100% pewny bez sprawdzania bajt po bajcie.
Attie
1
@Attie Huh! To pierwotnie miałem na myśli. Dzięki. 🙏 Tylko, że nie znam eleganckich zwrotów typu „możesz być dość pewny siebie”. Przepraszam. 😜 Mimo to mamy przycisk edycji. Osobiście nigdy nie zniszczyłbym dobrej odpowiedzi tylko dlatego, że jedno słowo w niej jest nieprawidłowe. Ja to edytuję.
1
O „wyrzucaniu dobrej odpowiedzi”: pamiętaj, że najpierw upewniłem się, że nie jest to literówka i naprawdę to masz na myśli; następnie przegłosowałem, a jednocześnie wyraziłem opinię, podałem swój powód w nadziei, że Twoja odpowiedź będzie lepsza. Tak, więc już nie mam mojego zdania. Zasadniczo powiedziałem ci, co uważam za złe w twojej odpowiedzi, Attie pomógł wyjaśnić, poprawiłeś odpowiedź. Z mojego punktu widzenia wszyscy dobrze poradziliśmy sobie z tą sytuacją i cała historia potoczyła się bardzo dobrze. Dziękuję Ci.
Kamil Maciorowski
5

Mam 2 dokumenty programu Excel i chcę sprawdzić, czy są dokładnie takie same, oprócz nazwy pliku.

Z praktycznego punktu widzenia bezpośrednie porównywanie plików w celu ustalenia, czy są one inne, będzie szybsze niż obliczenie skrótu dla każdego pliku, a następnie porównanie tego skrótu.

Aby obliczyć skróty, musisz przeczytać całą zawartość obu plików.

Aby ustalić, czy są one identyczne poprzez bezpośrednie porównanie, wystarczy przeczytać zawartość obu plików, dopóki się nie zgadzają. Gdy znajdziesz różnicę, wiesz, że pliki nie są identyczne i nie musisz czytać więcej danych z żadnego z plików.

Zanim to zrobisz, możesz po prostu porównać rozmiary dwóch plików. jeśli rozmiary się różnią, zawartość nie może być taka sama.

Andrew Henle
źródło
Podczas korzystania z dwóch plików na jednym dysku fizycznym użycie funkcji skrótu, która może nadążać za prędkością we / wy każdego pliku osobno, może być nieco szybsze niż porównywanie plików, ponieważ nie byłoby potrzeby przełączania się między odczytem dwóch plików. Skróty miejsca naprawdę świecą, gdy próbujesz porównać wiele plików, które są zbyt duże, aby zmieścić się w pamięci. Nawet jeśli chcesz się tylko dowiedzieć, czy wszystkie pasują do siebie, porównując plik 1 z plikiem 2, a następnie plik 1 z plikiem 3, a następnie plik 1 z plikiem 4 itd. Może być prawie dwa razy wolniejszy niż obliczanie wszystkich skrótów.
supercat
@ superuper Jeśli pliki są odczytywane w kawałkach większych niż około MB, przełączanie między plikami nie będzie zauważalne. A jeśli przepływ pracy wymaga porównywania wielu plików w celu znalezienia duplikatów, skrót może być obliczany tak samo, jak każdy plik jest zapisywany - ponieważ wykonanie tego można wtedy zrobić prawie za darmo.
Andrew Henle
Jeśli ktoś ma wystarczająco dużo miejsca, aby buforować duże porcje plików, czasy przełączania nie muszą stanowić problemu, ale w przeciwnym razie mogą być. Jeśli chodzi o obliczanie skrótów podczas zapisywania plików, może być w porządku, jeśli można zagwarantować, że plików nie można zmodyfikować bez zmiany lub przynajmniej unieważnienia przechowywanych skrótów. Jeśli ktoś próbuje uniknąć tworzenia kopii zapasowej plików nadmiarowo, przeglądanie tylko przechowywanych wartości skrótu może spowodować, że ktoś utworzy kopię zapasową przypadkowo uszkodzonego pliku, ale nie będzie musiał zadawać sobie trudu, aby wykonać kopię zapasową nieuszkodzonych plików, które uszkodzony plik powinien pasować, ale nie .
supercat
„Gdy znajdziesz różnicę, wiesz, że pliki nie są identyczne” - niekoniecznie. Pliki XLSX to pliki ZIP, które potencjalnie mogą przechowywać zawartość w innej kolejności, wciąż mając tę ​​samą zawartość. Ale nawet jeśli je zdekompresujesz i porównasz każdy plik, plik XLSX zawiera dokumenty XML, które mogą mieć np. Różne zakończenia linii bez wpływu na treść.
Thomas Weller
5

Skróty takie jak MD5 lub SHA mają ustaloną długość, powiedzmy, że to 300 znaków alfanumerycznych (w rzeczywistości są one krótsze i nie używają całego zestawu znaków alfanumerycznych).

Powiedzmy, że pliki składają się ze znaków alfanumerycznych i mają rozmiar do 2 GB.

Możesz łatwo zobaczyć, że istnieje znacznie więcej plików (o rozmiarze do 2 GB) niż możliwe wartości skrótu. Zasada szuflady mówi, że niektóre (różne) pliki muszą mieć te same wartości skrótu.

Ponadto, jak pokazano na shattered.io 1 , możesz mieć dwa różne pliki: shattered.io/static/shattered-1.pdf i shattered.io/static/shattered-2.pdf, które mają tę samą wartość skrótu SHA-1, będąc jednocześnie zupełnie inny.

1 SHA1 jest „silniejszym” algorytmem mieszającym niż md5

mucha styropianowa
źródło
Prawdopodobieństwo przypadkowych kolizji jest zbyt niskie, aby je uwzględnić. Ryzyko celowej kolizji istnieje również w przypadku MD5 i jest większe niż w przypadku SHA-1, co nie jest tutaj szczególnie istotne.
Gilles „SO- przestań być zły”
4

NIE. Różne wartości gwarantują, że pliki są różne. Te same wartości nie gwarantują, że pliki są takie same. Stosunkowo łatwo jest znaleźć przykłady przy użyciu CRC16.

W równowadze prawdopodobieństwa ze współczesnymi schematami mieszania są one takie same.

mckenzm
źródło
1
Pytanie dotyczy MD5, który nie ma ryzyka przypadkowych kolizji. Istnieje ryzyko celowych kolizji, ale to nie jest kwestia prawdopodobieństwa.
Gilles „SO- przestań być zły”
1
Chodzi również o arkusze kalkulacyjne Excel o różnych nazwach. Jak duże mogą one być, aby bajt do porównania bajtów nie mógł być opcją? Dwa schematy mieszania razem zapewniłyby pewność.
mckenzm
2
@Gilles Wszystkie kody skrótu mają z definicji ryzyko przypadkowych kolizji. Jedynym wyjściem z tego jest użycie całego pliku jako kodu skrótu. Twój komentarz nie ma sensu.
user207421
3

Twoje pytanie jest jednak odwrócone - załóżmy, że skrót oznacza, że ​​mają te same dane (co nie jest w 100% gwarantowane, ale wystarcza na całe życie porównywania plików co sekundę, aby nie dojść do kolizji). Nie musi to oznaczać, że posiadanie tych samych danych oznacza, że ​​będą mieli ten sam skrót. Więc nie - nie można porównywać danych w pliku programu Excel z danymi w innym pliku programu Excel, mieszając plik, ponieważ istnieje wiele sposobów, w jakie dwa pliki mogą się różnić bez różnic między danymi bazowymi. Jeden oczywisty sposób - dane są przechowywane w formacie XML, każda komórka ma własny węzeł XML. Jeśli te węzły są przechowywane w różnych porządkach, dane są takie same, ale plik jest inny.

David Rice
źródło
3

Aby dodać pozostałe odpowiedzi, oto wiele przykładów par plików z tym samym skrótem MD5 i inną zawartością.

Giulio Muscarello
źródło
Odpowiedź dość prosta, ale interesująca.
Thomas Weller
2

Odpowiedź na ten PO została podana, ale może skorzystać z podsumowania.

Jeśli chcesz sprawdzić, czy dwa pliki są takie same, wiele zależy od tego, czy pliki i skróty są pod twoją kontrolą.

Jeśli generujesz skróty samodzielnie z plików i jesteś prawie pewien, że nikt inny nie miał okazji / umiejętności / motywacji, aby celowo dojść do niewłaściwego wniosku, to prawie każdy skrót - nawet „znane zepsute” skróty, takie jak MD5 i SHA1, są prawie na pewno wystarczy. Ale to znaczy, że możesz generować pliki z dużą prędkością przez miliony lat i nadal nie jest prawdopodobne, aby skończyły się jakiekolwiek dwa pliki, które są faktycznie różne, ale mają ten sam skrót. Jest prawie na pewno bezpieczny.

Jest to scenariusz, w którym chcesz szybko sprawdzić, czy dwa katalogi na komputerze lub serwerze plików mają tę samą zawartość, czy jakieś pliki w katalogu są dokładnie duplikatami itp., I masz pewność, że pliki nie mają został zaprojektowany / nielegalnie zmodyfikowany i ufasz, że Twoja aplikacja / narzędzie haszujące da prawidłowe wyniki.

Jeśli znajdujesz się w scenariuszu, w którym jeden z plików - lub wstępnie obliczony skrót - mógł zostać zmanipulowany lub zmodyfikowany w celu oszukiwania cię w niewłaściwym wniosku, potrzebujesz silniejszego (nieprzerwanego) skrótu i ​​/ lub innego zabezpieczenia. Na przykład, jeśli pobierzesz plik i sprawdzisz, czy jest poprawny, sprawdzając skrót, wówczas osoba atakująca może być w stanie skonstruować zły plik z poprawnym skrótem lub zaatakować witrynę internetową, aby umieścić nieprawidłowy skrót, gdy szukasz „właściwego” " (wartość oczekiwana. Sprowadza się to do szerszych problemów bezpieczeństwa.

Stilez
źródło
2

W wierszu polecenia systemu Windows można użyć compnarzędzia do ustalenia, czy dwa pliki są dokładnie takie same. Na przykład:

comp fileone.xls filetwo.xls
Czad
źródło
1

Kiedy skróty są identyczne, czy to oznacza, że ​​zawartość pliku jest taka sama 1: 1?

Nie. Jeśli hashe są różne, to nie znaczy, że zawartość są różne. Jednakowe kody skrótu nie oznaczają jednakowej zawartości. Hashcode to redukcja dużej domeny do mniejszego zakresu, z definicji: implikacja jest taka, że ​​hascodes nad nierównymi treściami mogą być równe. W przeciwnym razie ich obliczenie nie miałoby sensu.

użytkownik207421
źródło
W przeciwnym razie ich obliczenie nie miałoby sensu. Jeśli złamałeś prawa matematyki i wynalazłeś bezstratną funkcję kompresji, która może kompresować losowe dane, naruszając zasadę szufladki, bardzo przydatne byłoby jej użycie! Byłoby bardzo wygodne, gdy 128-bitowy hash było wyjątkowo reprezentować całą zawartość pliku. Nawet gdyby nie było funkcji dekompresyjnej, która zamieniłaby skrót z powrotem w plik, dobrze byłoby mieć matematycznie niemożliwy, pozbawiony kolizji skrót, np. Aby przyspieszyć wyszukiwanie duplikatów w niezaufanych danych, jak na obrazach VM.
Peter Cordes
„Jeśli skróty są różne, oznacza to, że zawartość jest inna”. Niekoniecznie. Pliki XLSX są plikami ZIP i byłoby możliwe, aby ta sama treść była przechowywana w innej kolejności plików.
Thomas Weller
1

Ta odpowiedź ma być poręczną mapą scenariuszy, które mogą się zdarzyć lub nie, oraz uzasadnienia, które możesz zastosować. Zobacz inne odpowiedzi, aby dowiedzieć się, dlaczego funkcje skrótu działają w ten sposób.


Po wybraniu funkcji skrótu i ​​trzymaniu się jej, należy rozważyć wszystkie te kombinacje:

          |    identical   |   different    |
          |   hash values  |  hash values   |
----------+----------------+----------------+
identical |   can happen,  | cannot happen, |
  files   |     common     |   impossible   |
----------+----------------+----------------+
different |   can happen,  |   can happen,  |
  files   |      rare*     |     common     |
----------+----------------+----------------+

* rare, unless whoever generates (at least one of) the files
  purposely aims at this scenario

Scenariusz, w którym identyczne pliki generują różne wartości skrótu, jest jedynym, który jest absolutnie niemożliwy.


Dwa rozumowania, które zawsze obowiązują:

  • Jeśli pliki są identyczne, wartości skrótu na pewno są identyczne .
  • Jeśli wartości skrótu są różne, pliki na pewno się różnią .

Dwa argumenty, które nieścisłe :

  • Jeśli pliki są różne, wartości skrótu są prawdopodobnie różne.
  • Jeśli wartości skrótu są identyczne, pliki prawdopodobnie są identyczne.
Kamil Maciorowski
źródło
0

Dla twoich celów tak, identyczne skróty oznaczają identyczne pliki.

Jak wyjaśniają inne odpowiedzi, możliwe jest zbudowanie 2 różnych plików, które skutkują tym samym hashem, a MD5 nie jest szczególnie solidny pod tym względem.

Użyj więc silniejszego algorytmu mieszającego, jeśli planujesz porównać dużą liczbę dokumentów programu Excel lub jeśli uważasz, że ktoś może chcieć manipulować porównaniem. SHA1 jest lepszy niż MD5. SHA256 jest znowu lepszy i powinien dać ci całkowitą pewność co do konkretnego zastosowania.

jah
źródło
-1

Pliki są prawdopodobnie identyczne, jeśli ich skróty są identyczne. Możesz zwiększyć zaufanie, modyfikując oba pliki w identyczny sposób (np. Umieszczając tę ​​samą wartość w tej samej nieużywanej komórce), a następnie porównując skróty zmodyfikowanych plików. Trudno jest stworzyć celową kolizję dla pliku, który jest zmieniany w sposób nieznany wcześniej.

ibft2
źródło
To nie zadziała z powodu dodatkowych danych przechowywanych w plikach biurowych. Musisz np. Umieścić kursor w tej samej komórce przed zapisaniem, zapisać dokładnie w czasie itp. Ale nawet wtedy pliki XLSX są wewnętrznie plikami zip, więc jeśli ten algorytm przechowuje poszczególne pliki w innej kolejności (w dowolnym celu), plik jest identyczny, ale skrót nie jest
Thomas Weller
-2

Spójrzmy na to w praktyczny sposób. Zamiast powiedzieć „skróty są identyczne” powiem „napisałem program komputerowy, który oblicza skróty dwóch plików i drukuje, czy są one takie same, czy nie”, i uruchamiam program z dwoma plikami, i mówi: "identyczny". Istnieje kilka powodów, dla których może to zrobić:

Pliki mogą być identyczne. Mój kod może zawierać błędy (jednym, który faktycznie zdarzył się w praktyce, było porównywanie dwóch długich (256-bajtowych) skrótów nie z memcmp, ale z strcmp: Porównanie zwróci „to samo”, jeśli pierwszy bajt w każdym skrócie jest równy zero, a szansa na to jest 1 na 65536. Może występować błąd sprzętowy (promień kosmiczny uderza w komórkę pamięci i przełącza ją) lub może wystąpić rzadki przypadek dwóch różnych plików z identycznym hashem (kolizja skrótu).

Powiedziałbym, że w przypadku nieidentycznych plików zdecydowanie najbardziej prawdopodobną przyczyną jest błąd programisty, potem pojawia się promień kosmiczny, który zmienił zmienną boolowską w wyniku porównania skrótów z „fałszywych” na „prawdziwe”, a znacznie później przychodzi przypadek zderzenia mieszającego.

Istnieją korporacyjne systemy tworzenia kopii zapasowych, które unikają tworzenia kopii zapasowych identycznych plików od 10.000 użytkowników, mieszając każdy plik i sprawdzając, czy plik o identycznym haszu jest już przechowywany na serwerze. Dlatego w przypadku kolizji plik nie zostanie utworzony, co może prowadzić do utraty danych. Ktoś obliczył, że znacznie bardziej prawdopodobne jest, że meteoryt uderzy w twój serwer i zniszczy wszystkie kopie zapasowe niż utratę pliku, ponieważ jego suma kontrolna pasuje do innego pliku.

gnasher729
źródło