Czy w praktyce można bezpiecznie zignorować możliwość kolizji SHA?

209

Załóżmy, że mamy miliard unikalnych obrazów, każdy o wielkości jednego megabajta. Obliczamy skrót SHA-256 dla zawartości każdego pliku. Możliwość kolizji zależy od:

liczba plików
~~rozmiar pojedynczego pliku~~

Jak daleko możemy posunąć się, ignorując tę możliwość, zakładając, że jest to zero?

hash sha Hristo Hristov
źródło

To zależy od tego, do czego używasz klawiszy skrótu. Jeśli jest to pewnego rodzaju identyfikacja pliku, kolizja może również oznaczać, że pliki są identyczne, dlatego też musisz porównać pliki w przypadku kolizji. Powiedziałbym, że porównywanie rozmiarów plików byłoby dość bezpieczne.

mojuba

Tak, w tym przypadku, jeśli porównasz rozmiary plików, możliwość drastycznie spada. Możesz także użyć dwóch algorytmów mieszających i połączyć wyniki. Wtedy możliwość zderzenia obu jednocześnie zmniejsza się bardziej. Ale pytanie brzmi: ile jest „dość” bezpieczne? Może potrzebujemy formuły i liczb.

Hristo Hristov

@Hristo Hristov: jeśli założymy, że klucz skrótu jest pseudolosową liczbą (która teoretycznie jest poprawna), wówczas miliard kluczy 128-bitowych daje prawdopodobieństwo kolizji 2,9 * 10 ^ -30. Nie można nawet nazwać tego „maleńkim”, to mniej niż to;)

mojuba,

@mojuba: jeszcze lepiej, pyta o 256-bitowy skrót.

Michael Borgwardt,

FWIW: system kontroli wersji GIT identyfikuje pliki według ich zawartości SHA.

snemarch

Odpowiedzi:

385

Zwykła odpowiedź brzmi: jakie jest prawdopodobieństwo, że nieuczciwa asteroida rozbije się na Ziemi w ciągu najbliższej sekundy, niszcząc cywilizację taką, jaką znamy i zabijając kilka miliardów ludzi? Można argumentować, że każde nieszczęśliwe zdarzenie z prawdopodobieństwem niższym niż to nie jest tak naprawdę bardzo ważne.

Jeśli mamy „Perfect” funkcji skrótu z wielkości wyjściowej n , i mamy p wiadomości hash (indywidualna długość komunikatu nie jest ważne), to prawdopodobieństwo kolizji jest o p ² /2 ^{n + 1} (jest to przybliżenie, które jest ważne dla „małego” p , tj. znacznie mniejszego niż 2 ^{n / 2} ). Na przykład w przypadku SHA-256 ( n = 256 ) i miliarda wiadomości ( p = ¹⁰⁹ ) prawdopodobieństwo wynosi około 4,3 * ^10–60 .

Kosmiczna skała masowego mordercy zdarza się średnio raz na 30 milionów lat. Powoduje to prawdopodobieństwo takiego zdarzenia występującego w następnej sekundy do około 10 ^-15 . To 45 rzędów wielkości bardziej prawdopodobne niż kolizja SHA-256. Krótko mówiąc, jeśli uznasz, że kolizje SHA-256 są przerażające, twoje priorytety są błędne.

W ustawieniach zabezpieczeń, w których atakujący wybiera wiadomości, które zostaną zaszyfrowane, atakujący może użyć znacznie więcej niż miliarda wiadomości; przekonasz się jednak, że prawdopodobieństwo sukcesu atakującego będzie nadal znikomo małe. Taki jest sens używania funkcji skrótu z 256-bitowym wyjściem: aby ryzyko kolizji można było pominąć.

Oczywiście wszystkie powyższe założenia zakładają, że SHA-256 jest „idealną” funkcją skrótu, której daleko jeszcze do udowodnienia. Mimo to SHA-256 wydaje się dość solidny.

Thomas Pornin
źródło

To bardzo dobra odpowiedź, dzięki! Ale jeśli w przypadku zderzenia elektrownia jądrowa wybuchnie, a to zależy od ciebie, czy podejmiesz to ryzyko? Jeśli masz całkowitą rację, możemy podjąć ryzyko, ponieważ jest o 45 rzędów wielkości bardziej prawdopodobne, że cywilizacja zostanie zniszczona. Dobrze?

Hristo Hristov

@Hristo Myślę, że tak, można by podjąć to ryzyko. Elektrownia jądrowa ma już znacznie większą szansę na eksplozję z powodu innych przyczyn, takich jak awaria mechaniczna, błąd ludzki przy budowie lub błąd operatora podczas jej eksploatacji, a my już ryzykujemy. Gdyby kolizje SHA-256 były jedynymi przyczynami incydentów nuklearnych, prawie na pewno mielibyśmy ich dokładnie zero.

Roman Starkov,

foxnews.com/science/2013/02/11/ ... Zacznę myśleć o SHA512.

Dustin Oprea

Mogę teraz spokojnie odpoczywać, wiedząc, że prawdopodobnie asteroida zostanie zlikwidowana na długo przed tym, zanim przeżyję zderzenie SHA-256.

AaronLS,

Przepraszamy, brakuje Ci tak zwanego „paradoksu urodzinowego”. Przyjrzyj się lepiej „ładnemu stołowi”, nie działa to tak, jak myślisz. Dla liczb, które podam, w tej tabeli byłaby to wartość „10 ^ 9” w kolumnie oznaczonej „4.3 * 10 ^ -60” i wierszu „128 bitów” (ale tabela nie spada poniżej 10 ^ -18 ).

Thomas Pornin

Możliwość kolizji nie zależy od wielkości plików, tylko od ich liczby.

To jest przykład paradoksu urodzinowego . Strona Wikipedii podaje szacunkowe prawdopodobieństwo kolizji. Jeśli uruchomisz liczby, zobaczysz, że wszystkie dyski twarde kiedykolwiek wyprodukowane na Ziemi nie mogą pomieścić wystarczającej ilości plików 1 MB, aby uzyskać prawdopodobieństwo kolizji nawet 0,01% dla SHA-256.

Zasadniczo możesz po prostu zignorować tę możliwość.

Michael Borgwardt
źródło

Nie mogę się zgodzić z wnioskiem. Tak, żadne dyski twarde nie mogą przechowywać takiej liczby plików, ale IMO źle interpretuje sytuację. Do powstania kolizji potrzeba tylko dwóch plików. Chociaż możliwość jest bardzo niska, wciąż może się zdarzyć.

sharptooth

@sharptooth: nie, nie wprowadzam w błąd w tej sytuacji. Prawdopodobieństwo, że ty i wszyscy, których znasz, zginie w wyniku wypadku drogowego tego samego dnia, jest bardzo niskie, ale nadal może się zdarzyć (i jest znacznie wyższe niż w przypadku kolizji SHA-256). Jednak ignorujesz tę możliwość.

Michael Borgwardt,

@sharptooth: Mówiłem o osobnych , równoczesnych wypadkach drogowych kilkuset konkretnych osób. Naprawdę nie możesz zrobić żadnych kroków, aby obniżyć to. Byłoby to bezcelowe, ponieważ jest już dziwnie niskie. Ale nadal jest o wiele bardziej prawdopodobne niż zderzenie SHA-256, że nawet nie możesz sobie wyobrazić, ile. To ten sam argument, co Thomas.

Michael Borgwardt,

@sharptooth: Nie, szanse nie rosną znacząco, ponieważ liczba ta wciąż jest absolutnie mniejsza niż rozmiar przestrzeni mieszania SHA-256. To jedna rzecz, której nie bierzesz pod uwagę we właściwy sposób - wszystkie czynniki muszą być ważone na podstawie ich rzeczywistej wielkości, a nie jednakowo. Jeśli wygenerowałbyś miliard skrótów na sekundę dla każdej osoby na Ziemi i robiłbyś to przez tysiąc lat, nadal miałbyś mniej niż 1% szansy na kolizję.

Michael Borgwardt

Jeśli nie sprawdzisz możliwości wystąpienia nieskorygowanego błędu przy każdym pobieraniu z pamięci lub czytaniu z dysku (które mają znacznie większe prawdopodobieństwo niż kolizja SHA-256), możesz nie w pełni zrozumieć prawdopodobieństwa.

Christophe

Przede wszystkim nie jest to zero, ale bardzo blisko zera .

Kluczowe pytanie brzmi: co się stanie, jeśli rzeczywiście nastąpi kolizja ? Jeśli odpowiedź brzmi „wybuch elektrowni jądrowej”, prawdopodobnie nie powinieneś ignorować możliwości kolizji. W większości przypadków konsekwencje nie są tak straszne, więc możesz zignorować możliwość kolizji.

Nie zapominaj również, że twoje oprogramowanie (lub jego niewielka część) może zostać wdrożone i jednocześnie użyte w gazillionach komputerów (niektóre małe wbudowane mikrokomputery, które są obecnie prawie wszędzie obecne). W takim przypadku należy pomnożyć szacunkową liczbę uzyskanych danych przez możliwie największą liczbę kopii.

sharptooth
źródło

... nie według liczby kopii, ale liczby zestawów danych wszystkich skrótów.

Andreas Spindler

To źle, liczba kopii uruchomionego oprogramowania jest nieistotna. Liczy się tylko liczba unikatowych plików, które są przetwarzane, a paradoks urodzinowy to matematyka do obliczeń.

Dirk Bester,

Słyszałem, jak ktoś inny wspomniał, że prawdopodobieństwo awarii sprzętu - tj. Trochę przewrócenia gdzieś z powodu promieniowania itp. - jest bardziej prawdopodobne niż kolizja skrótu, a zatem martwienie się o kolizję skrótu jest głupie. Osobiście staram się objąć oba przypadki, aby być bezpiecznym (im większe bezpieczeństwo w elektrowni jądrowej, tym lepiej), ale kolizje hashowe byłyby prawdopodobnie bardzo niskie na liście potencjalnych zagrożeń (zakładając, że przestrzeń hasha jest wystarczająco duża) . Jednak wszystko to zakłada, że w funkcji skrótu nie ma ukrytego zachowania, które częściej powoduje kolizje.

Chris Middleton,

„0” ma swój obszar

Green Tree

@GreenTree Rzecz, z którą się łączysz, polega na celowym tworzeniu kolizji.

sharptooth