Wahrscheinlichkeit von SHA1-Kollisionen

68

Wie können Sie bei einem Satz von 100 verschiedenen Zeichenfolgen gleicher Länge die Wahrscheinlichkeit quantifizieren, dass eine SHA1-Digest-Kollision für die Zeichenfolgen unwahrscheinlich ist ...?

hash sha1 probability eastafri
quelle
Klären Sie, wie können Sie Zeichenfolgen mit unterschiedlicher, aber gleicher Länge haben?
KevinDTimm
5
@kevindtimm "a", "b", "c" sind gleich lang, aber unterschiedliche Zeichenfolgen
Joe Phillips
4
@anthony, warum ist das so offensichtlich? Ich weiß nicht, ob das stimmt
Joe Phillips
3
Doh, beim erneuten Lesen ist es vollkommen klar.
KevinDTimm
1
Dies ist für diese Frage relevant: sites.google.com/site/itstheshappening Es wurde mindestens eine Kollision gefunden.
Christophe De Troyer

Antworten:

144

Alt-Text

Sind die von SHA-1 generierten 160-Bit-Hashwerte groß genug, um sicherzustellen, dass der Fingerabdruck jedes Blocks eindeutig ist? Unter der Annahme zufälliger Hashwerte mit einer gleichmäßigen Verteilung, einer Sammlung von n verschiedenen Datenblöcken und einer Hash-Funktion, die b Bits erzeugt, ist die Wahrscheinlichkeit p, dass es zu einer oder mehreren Kollisionen kommt, durch die Anzahl der Blockpaare multipliziert mit der Wahrscheinlichkeit, dass Ein bestimmtes Paar kollidiert.

(Quelle: http://bitcache.org/faq/hash-collision-probabilities )

Peter
quelle
12
Zusammenfassend liegt die Wahrscheinlichkeit einer Kollision in der Größenordnung von 10 ^ -45. Das ist sehr, sehr unwahrscheinlich.
Paul Lammertsma
4
Aber SHA-1 ist keine gleichmäßige Verteilung, es könnte größer sein als diese Obergrenze. Ich bezweifle, dass diese Gleichung nicht korrekt ist. Zumindest das GLEICHE.
Kamel
1
Diese Antwort berücksichtigt nicht die chinesische Entdeckung im Jahr 2005, bei der Kollisionen in 2 ^ 69 Iterationen erzeugt werden können, anstatt der von Brute Force schneier.com/blog/archives/2005/02/sha1_broken.html
Djarid
5
@Djarid Es ist wichtig, versehentliche Hash-Kollisionen und die Suche nach gegnerischen Kollisionen nicht zu verwechseln. Ersteres ist die Wahrscheinlichkeit, dass der Hash zweier Elemente kollidiert, und folgt der obigen Formel (obwohl, wie von Kamel festgestellt, die Verteilung nicht perfekt gleichmäßig ist und daher die Wahrscheinlichkeit wahrscheinlich höher ist). Letzteres wird verwendet, um absichtlich zu versuchen, Kollisionen zu finden, und beruht darauf, Schwachstellen im Hash zu entdecken und auszunutzen. Kryptografische Hashes versuchen, gegen solche Angriffe robust zu sein, sind jedoch häufig für einfachere Hashing-Anwendungen (die keine Geheimnisse übertragen) übertrieben.
Pierre D
Diese Formel ist genau, wenn 2 ^ b >> n ^ 2 (und wenn 2 ^ b sehr groß ist). Ich weiß, es ist die Bürgermeisterschaft (wenn nicht alle) die Fälle für sha1 ... aber für die Aufzeichnung!
MrIo
7

Nun, die Wahrscheinlichkeit einer Kollision wäre:

1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)

Denken Sie an die Wahrscheinlichkeit einer Kollision von 2 Elementen in einem Raum von 10. Das erste Element ist mit einer Wahrscheinlichkeit von 100% eindeutig. Die zweite ist mit einer Wahrscheinlichkeit von 9/10 eindeutig. Die Wahrscheinlichkeit, dass beide eindeutig sind 100% * 90%, ist also und die Wahrscheinlichkeit einer Kollision ist:

1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)

Es ist ziemlich unwahrscheinlich. Sie müssten viel mehr Zeichenfolgen haben, um eine entfernte Möglichkeit zu sein.

Schauen Sie sich die Tabelle auf dieser Seite auf Wikipedia an . Interpolieren Sie einfach zwischen den Zeilen für 128 Bit und 256 Bit.

Anthony Mills
quelle
3

Das ist Geburtstagsproblem - der Artikel enthält nette Annäherungen, die es ziemlich einfach machen, die Wahrscheinlichkeit abzuschätzen. Die tatsächliche Wahrscheinlichkeit wird sehr, sehr gering sein - siehe diese Frage als Beispiel.

scharfer Zahn
quelle