Ist es sicher, die Möglichkeit von SHA-Kollisionen in der Praxis zu ignorieren?

Nehmen wir an, wir haben eine Milliarde einzigartiger Bilder mit jeweils einem Megabyte. Wir berechnen den SHA-256-Hash für den Inhalt jeder Datei. Die Möglichkeit einer Kollision hängt ab von:

• die Anzahl der Dateien
• die Größe der einzelnen Datei

Wie weit können wir gehen, wenn wir diese Möglichkeit ignorieren, wenn sie Null ist?

Die übliche Antwort lautet wie folgt: Wie hoch ist die Wahrscheinlichkeit, dass ein Schurken-Asteroid innerhalb der nächsten Sekunde auf der Erde abstürzt, die Zivilisation, wie wir sie kennen, auslöscht und einige Milliarden Menschen tötet? Es kann argumentiert werden, dass jedes unglückliche Ereignis mit einer geringeren Wahrscheinlichkeit nicht wirklich sehr wichtig ist.

Wenn wir eine „perfekte“ Hash - Funktion mit einer Ausgangsgröße haben n , und wir haben p - Nachrichten an hash (individuelle Nachrichtenlänge nicht wichtig ist), dann wird die Kollisionswahrscheinlichkeit , ist etwa p ² /2 ^{n + 1} (dies ist eine Annäherung , die ist gültig für "kleines" p , dh wesentlich kleiner als 2 ^{n / 2} ). Beispielsweise beträgt bei SHA-256 ( n = 256 ) und einer Milliarde Nachrichten ( p = 10 ⁹ ) die Wahrscheinlichkeit etwa 4,3 * 10 ^-60 .

Ein Massenmörder-Weltraumfelsen kommt durchschnittlich alle 30 Millionen Jahre vor. Dies führt zu einer Wahrscheinlichkeit , ein solches Ereignis in der nächsten Sekunde auftreten , zu etwa 10 ^-15 . Das sind 45 Größenordnungen wahrscheinlicher als die SHA-256-Kollision. Kurz gesagt, wenn Sie SHA-256-Kollisionen als beängstigend empfinden, sind Ihre Prioritäten falsch.

In einem Sicherheits-Setup, in dem ein Angreifer die Nachrichten auswählen kann, die gehasht werden sollen, kann der Angreifer wesentlich mehr als eine Milliarde Nachrichten verwenden. Sie werden jedoch feststellen, dass die Erfolgswahrscheinlichkeit des Angreifers immer noch gering ist. Das ist der springende Punkt bei der Verwendung einer Hash-Funktion mit einer 256-Bit-Ausgabe: Damit Kollisionsrisiken vernachlässigt werden können.

Bei alledem wird natürlich davon ausgegangen, dass SHA-256 eine "perfekte" Hash-Funktion ist, die bei weitem nicht bewiesen ist. Trotzdem scheint SHA-256 ziemlich robust zu sein.

Die Möglichkeit einer Kollision hängt nicht von der Größe der Dateien ab, sondern nur von ihrer Anzahl.

Dies ist ein Beispiel für das Geburtstagsparadoxon . Die Wikipedia-Seite gibt eine Schätzung der Wahrscheinlichkeit einer Kollision. Wenn Sie die Zahlen eingeben, werden Sie feststellen, dass alle jemals auf der Erde produzierten Festplatten nicht genügend 1-MB-Dateien enthalten können, um eine Kollisionswahrscheinlichkeit von sogar 0,01% für SHA-256 zu erhalten.

Grundsätzlich können Sie die Möglichkeit einfach ignorieren.

Erstens ist es nicht Null, sondern sehr nahe bei Null .

Die Schlüsselfrage ist, was passiert, wenn tatsächlich eine Kollision auftritt ? Wenn die Antwort lautet "Ein Kernkraftwerk wird explodieren", sollten Sie die Kollisionsmöglichkeit wahrscheinlich nicht ignorieren. In den meisten Fällen sind die Folgen nicht so schlimm, sodass Sie die Kollisionsmöglichkeit ignorieren können.

Vergessen Sie auch nicht, dass Ihre Software (oder ein winziger Teil davon) möglicherweise in einer Unmenge von Computern bereitgestellt und gleichzeitig verwendet wird (einige winzige eingebettete Mikrocomputer, die heutzutage fast überall enthalten sind). In diesem Fall müssen Sie die Schätzung mit der größtmöglichen Anzahl von Kopien multiplizieren.