Jak wyjątkowe są sumy kontrolne?

11

Mam dużo plików, które muszę posortować; i niestety jest wiele plików o tej samej nazwie, ale o innej zawartości, i jest taka sama treść o różnych nazwach plików.

Zastanawiam się nad użyciem md5sumdo generowania sum kontrolnych dla plików, ale muszę wiedzieć - czy możliwe jest, że dwa różne pliki (tj. Inna zawartość) wygenerują tę samą sumę kontrolną?

Jeśli tak, to jak prawdopodobne jest?

Czy byłoby możliwe użycie dwóch różnych niepowiązanych (tj. Nie należących do tej samej „rodziny”) programów sum kontrolnych do wygenerowania dwóch sum kontrolnych - przy założeniu, że chociaż dwa różne pliki mogą generować tę samą sumę kontrolną dla jednego z programów sum kontrolnych, nigdy nie zdarzy się to obu naraz?

Baard Kopperud
źródło
2
Pamiętaj, że md5 / sha2 / etc to HASH danych, który mapuje wiele bitów informacji na mniejszą przestrzeń bitową, co może powodować kolizje. HASH nie jest unikalnym kluczem i jeśli to jest twój cel ... zdecydowanie polecam zrobienie czegoś innego.
mdpc
Do sortowania plików MD5 jest w porządku. Z crypto.stackexchange.com/a/18337/49945 prawdopodobieństwo zderzenia sumy kontrolnej dwóch różnych treści wynosi 1 na 2 ^ 128, czyli około 1 na 10 ^ 43. To naprawdę bardzo rzadkie. Jeśli wykonasz jedno porównanie na mikrosekundę, średnio otrzymasz zderzenie raz na 10 ^ 20 lat. Minęło tylko ~ 10 ^ 9 lat od Wielkiego Wybuchu, więc szanse na kolizję JESZCZE JEDEN CZAS, w jednym porównaniu na mikrosekundę od Wielkiego Wybuchu do tej pory, nadal wynoszą tylko 1 na 10 ^ 11. Biorąc pod uwagę sto miliardów komputerów jednocześnie, tylko jeden widziałby kolizję.
ToolmakerSteve
... chociaż nie jest jasne, dlaczego miałbyś używać dowolnego algorytmu mieszającego podczas sortowania plików. Jeśli istnieją pliki o tej samej nazwie, muszą być możliwe do zidentyfikowania według innych kryteriów; np. musi istnieć jakaś unikalna ścieżka do pliku, a może przesunięcie bajtów w jakimś urządzeniu pamięci masowej? Każda z nich byłaby bardziej użytecznym sposobem na unikalne odniesienie do pliku.
ToolmakerSteve

Odpowiedzi:

11

Dwa pliki o tej samej zawartości, ale różnych nazwach plików: ( plik1 i plik2 ):

cat file1
this is a simple file

cat file2
this is a simple file

md5sum file1
7de45bf879db49de7e2eacea23e6c165  file1
md5sum file2
7de45bf879db49de7e2eacea23e6c165  file2

Dwa pliki o różnej zawartości, ale o tych samych nazwach plików: ( plik1 i plik1 )

cat file1
this is a simple file
cat file1
this is a simple file with extra contents
md5sum file1 #first file1
7de45bf879db49de7e2eacea23e6c165  file1
md5sum file1 #second file1
c7c8f3fd9ddd7a926c31416a69063e4e  file1

Z wiki wpisu,

Jednak jest bardzo mało prawdopodobne, aby jakiekolwiek dwa nieidentyczne pliki w świecie rzeczywistym miały ten sam skrót MD5, chyba że zostały utworzone specjalnie z myślą o tym samym skrócie.

Ale algorytm MD5 ma swoje wady.

Jednak teraz, gdy generowanie kolizji MD5 jest łatwe, osoba, która utworzyła plik, może utworzyć drugi plik z tą samą sumą kontrolną, więc ta technika nie może zabezpieczyć się przed niektórymi formami złośliwego manipulowania. Ponadto w niektórych przypadkach suma kontrolna nie może być zaufana (na przykład, jeśli została uzyskana w tym samym kanale co pobrany plik), w którym to przypadku MD5 może zapewnić jedynie funkcję sprawdzania błędów: rozpozna uszkodzone lub niekompletne pobieranie, co staje się bardziej prawdopodobne podczas pobierania większych plików.

Poleciłbym użycie sha1 do obliczenia sumy kontrolnej, ponieważ tworzenie kolizji nie jest takie łatwe przy użyciu algorytmów sha1 . Generowanie sumy kontrolnej sha1 jest dość łatwe, jak widać tutaj .

Ramesh
źródło
UWAGA: pytanie dotyczy sortowania plików; zalecenie użycia sha1nie jest istotne dla tego zadania; ma to znaczenie tylko w przypadku obaw o bezpieczeństwo .
ToolmakerSteve