Wie sollte ich Prüfsummenkollisionen in meiner Anwendung behandeln?

Question

Ich habe einen Teil meiner Anwendung, der Dateien speichert. Da wir möglicherweise viele der gleichen Datei hinzufügen könnten, speichere ich zunächst einen Hash für jede Datei. Wenn zwei Dateien denselben Hash haben, wird eine verworfen, und beide "Verweise" auf diese Datei verweisen auf dieselbe physische Datei.

1. Inwieweit sollte ich mir Sorgen über Hash-Kollisionen machen?

2. Was sollte ich im Falle eines Zusammenstoßes tun? Der ganze Kern meines Codes hängt bisher davon ab, dass es nicht zwei verschiedene Dateien mit demselben Hash gibt. Im Falle einer Kollision im Moment würde meine App eine legitim unterschiedliche Datei ausgeben und auf die Datei mit dem gleichen Hash verweisen.

3. Sollte ich etwas anderes als MD5 verwenden? Hat SHA-1 eine bessere Kollisionsrate?

Answer 1

Sofern es sich nicht um eine WIRKLICH kritische Anwendung handelt, sollten Sie sich keine Gedanken über Hash-Kollisionen machen. Sie sind so selten, dass viele Dinge davon ausgehen, dass sie nicht vorkommen, und wenn sich diese Annahme nur einmal als falsch erweist, kann das katastrophale Folgen für diese Dinge haben.

SHA1 hat einen größeren Ausgaberaum als MD5 (und es sind auch weniger Angriffe auf ihn bekannt), so dass er definitiv keine schlechtere Wahl ist. Wenn Sie befürchten, dass jemand Ihre Hashes aktiv kollidieren könnte, wäre vielleicht eine spätere Variante von SHA, wie SHA-256, eine gute Idee.

Answer 2

Die Wahrscheinlichkeit einer Kollision zwischen den Hashes zweier zufällig ausgewählter Bitströme ist umgekehrt proportional zur Anzahl der unterschiedlichen Zustände, die der Hash repräsentiert. Ein 64-Bit-Hash kodiert also 2 ** 64 Staaten und hat eine Chance auf 1 / (2**64) einer Kollision für ein beliebiges Dateipaar. In Wirklichkeit geht es aber um die Wahrscheinlichkeit von Kollisionen bei einer (großen) Menge von Dateien. Daher müssen Sie das "Geburtstagsparadoxon" berechnen, indem Sie die Wahrscheinlichkeit einer paarweisen Kollision und die erwartete Anzahl von Dateien einsetzen.

Ich denke aber, dass es unterm Strich unsicher ist, eine Datei ohne einen Vergleich wegzuwerfen, auch wenn die Wahrscheinlichkeit eines Zusammenstoßes nach den Zahlen gering ist.

Answer 3

In dem vorgesehenen Szenario brauchen Sie sich keine Sorgen zu machen. Es ist nicht möglich, dass 2 verschiedene Dokumente die gleiche Prüfsumme haben, es sei denn, sie sind identisch. Stellen Sie sich das vor:

var a = 1; var b = 2;

b + 3 = 5; // true yay! a + 3 != 5; // keine Kollision möglich, solange var a nicht gleich 2 ist

var 'a' mit einem anderen Wert als 2 kann niemals zu 5 berechnet werden, so dass keine Kollision möglich ist. Da Sie einen 1-Wege-Prüfsummen-Hash-Algorithmus verwenden (oder verwenden sollten), wird der resultierende Hash immer von den Eingaben abhängig sein

Hash-Kollisionen treten auf, wenn man es mit zufällig generierten Hashes zu tun hat, die aufgrund ihrer zufälligen, nicht spezifizierten Eingaben kollidieren könnten, obwohl dies sehr unwahrscheinlich ist.

Bitte beachten Sie, dass ich keineswegs behaupte, dass Einweg-Hashing-Algorithmen durch einfache Addition erreicht werden. Ich verwende lediglich die Addition als einfaches Beispiel, das auf der einfachen Vorstellung beruht, dass beide eine Reihe von Werten nehmen und eine andere Reihe von Werten ausgeben, die auf diesen Werten basieren.