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

Powiedzmy, że mamy miliard unikalnych obrazów, jeden megabajt każdy. Obliczamy hash SHA-256 dla zawartości KAŻDEGO pliku. Możliwość kolizji zależy od:

  • liczba plików
  • Rozmiar pojedynczego pliku

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

 180
hashsha
Author: Flimzy, 2010-10-25
Source

3 answers

Zwykła odpowiedź brzmi tak: jakie jest prawdopodobieństwo, że zbuntowana asteroida rozbije się na ziemi w ciągu następnej sekundy, niszcząc cywilizację taką, jaką znamy i zabijając kilka miliardów ludzi? Można twierdzić, że każde pechowe Zdarzenie z prawdopodobieństwem niższym niż to nie jest w rzeczywistości bardzo ważne.

Jeśli mamy "idealną" funkcję hashową o wyjściowym rozmiarze n i mamy P Wiadomości do hasha( indywidualna długość wiadomości nie jest ważna), to prawdopodobieństwo kolizja jest o p2/2n+1 (jest to przybliżenie ważne dla "małego" p , tzn. znacznie mniejszego niż 2n/2). Na przykład, z SHA-256 (n=256) i miliard wiadomości (p=109) wtedy prawdopodobieństwo wynosi ok.4.3*10-60.

Kosmiczna skała masowych morderców zdarza się średnio raz na 30 milionów lat. Prowadzi to do prawdopodobieństwa wystąpienia takiego zdarzenia w Następna sekunda o 10-15. To 45 rzędy wielkości bardziej prawdopodobne niż zderzenie SHA-256. Krótko mówiąc, jeśli uważasz, że kolizje SHA-256 są przerażające, Twoje priorytety są błędne.

W konfiguracji zabezpieczeń, w której atakujący wybiera wiadomości, które zostaną zahaszowane, atakujący może użyć znacznie więcej niż miliarda wiadomości; jednak okaże się, że prawdopodobieństwo sukcesu atakującego nadal będzie znikome. To jest cały punkt korzystania z funkcji hash z 256-bitowym wyjściem: tak, że ryzyko kolizji można pominąć.

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

 330
Author: Thomas Pornin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-29 11:04:37

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

Oto przykład paradoksu urodzinowego . Strona Wikipedii podaje oszacowanie prawdopodobieństwa kolizji. Jeśli uruchomisz numery, zobaczysz, że wszystkie dyski twarde kiedykolwiek produkowane na ziemi nie mogą pomieścić wystarczającej ilości plików 1MB, aby uzyskać prawdopodobieństwo kolizji nawet 0.01% dla SHA-256.

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

 43
Author: Michael Borgwardt,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-10-25 11:39:08

Po Pierwsze, nie jest to zero, ale bardzo blisko zera .

Kluczowe pytanie brzmi co się stanie, jeśli dojdzie do kolizji ? Jeśli odpowiedź brzmi "elektrownia jądrowa wybuchnie" to prawdopodobnie nie powinieneś ignorować możliwości kolizji. W większości przypadków konsekwencje nie są tak tragiczne, więc można zignorować możliwość kolizji.

Również nie zapominaj, że oprogramowanie (lub jego niewielka część) może być wdrożone i jednocześnie używane w gazillion Komputery (niektóre małe wbudowane mikrokomputery, które są obecnie prawie wszędzie włączone). W takim przypadku należy pomnożyć oszacowanie, które posiadasz przez jak największą liczbę kopii.

 15
Author: sharptooth,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 11:47:22