Zu Kollisionen in Hashfunktionen und dem (Un)sinn, sie zur Suche zu verwenden.

by Linus Neumann on März 14, 2012

Heute habe ich im Logbuch Netzpolitik eine kurze Einführung gegeben, was kryptografische Hashfunktionen sind, und welchen Zweck sie bei der Integritätsprüfung von Dateien erfüllen. Dabei kam ich auch auf Kollisionen zu sprechen, den Fall, dass 2 Dateien einen gleichen Hash haben.

Per Twitter fragte mich gerade @LucasF:

Im Bezug auf LNP, müsste es nicht theoretisch unendlich viele Dateien mit gleichem Hashwert geben, und nicht nur zwei?

Die kurze Antwort:

Theoretisch ja, aber wenn
nDateien -> ∞ und
Dateigröße -> ∞,
dann brauchst du immer noch
t -> ∞
um gezielt Dateien mit gleichem Hash, also eine Kollision zu finden / zu konstruieren.

Das ist nämlich der Sinn von Hashfunktionen, die zum Beispiel bei PGP-Emailsignaturen zum Einsatz kommen: Es soll dem Angreifer unmöglich sein, eine Nachricht zu konstruieren, die den gleichen Hash produziert, dabei aber immer noch sinnvoll überzeugend ist, um beim Empfänger kein Misstrauen zu wecken. Gleiches gilt bei der Datei-Integritätsprüfung bei Software-Downloads: Es ist eine Sache, evtl. eine kollidierende Datei mit gleichem Hash zu konstruieren, aber ungleich schwieriger, dafür zu sorgen, dass diese dann auch eine ausführbare, (schadhafte) Datei ist.

Das gilt aber nur so lange, wie die Hashfunktion “ideal” ist, deshalb gibt es hier

Die lange Antwort:

Eine gute Hashfunktion zum Generieren von Datei-Fingerabdrücken muss folgende Anforderungen erfüllen: 

  1. Gleichverteilung der Hashwerte auf die Eingabewerte, d.h. jeder Hash ist gleich wahrscheinlich
  2. Hohe Sensitivität für Veränderungen, so dass das Umkippen eines Bits im Schnitt die Hälfte aller Bits im Hash verändert (Chaos und schwere Vorhersagbarkeit)
  3. Jeder mögliche Hash kann auch tatsächlich vorkommen (Surjektivität)
  4. Schnelle Berechenbarkeit (Effizienz)
  5. Datenreduktion – Der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener des Eingabewert.

Dabei stehen natürlich Datenreduktion und Effizienz in Widerspruch zur Einzigartigkeit eines Hashes, es findet also ein Trade-off statt. Die chaotische Eigenschaft der Hashfunktion ist uns dabei im Prinzip die wichtigste, denn sie soll es unmöglich machen, gezielt eine Kollision zu konstruieren oder bei einem Integritätscheck kleine Fehler zu “übersehen”.

Die Anforderungen werden meist mehr oder weniger gut erfüllt, so dass mögliche Angriffe wie

  1. das Finden von n unterschiedlichen Dateien mit identischem Hash
  2. das Finden von n Dateien zu einem vorgegebenen Hash
  3. das Finden von n Dateien zu einem Hash, der von einer vorgegebenen Datei stammt

nur mit Ratewahrscheinlichkeit ausgeführt werden können, d.h. ich kann eine Kollision nicht gezielt konstruieren, sondern nur so lange Würfeln, wie ich durch Zufall eine finde.

Randbemerkung 1: Es ist leider so, dass nicht alle Hashfunktionen den o.g. Anforderungen ideal gerecht werden, was dann jeweils die Möglichkeit öffnet, die beschriebenen Angriffe effizienter durchzuführen, als mit Ratewahrscheinlichkeit.

Randbemerkung 1.1: Bei unserem Beispiel md5 ist zum Beispiel auch das gezielte Konstruieren schon gelungen.

Randbemerkung 2: Wenn die Hashfunktion einen kleinen Ergebnisraum hat, dann geht natürlich auch das Raten schneller. Stellen wir uns zur Vereinfachung eine Hashfunktion mit nur 10 möglichen Hashes vor. Deshalb haben wir uns von SHA-1 über SHA-256 zu SHA-512 entwickelt.

Randbemerkung 3: Wenn beides zusammen kommt, weil die Hashfunktion eher Wert auf Effizienz gelegt hat, weil sie nämlich für Hashtabellen genutzt wird, dann kommen so schöne Dinge wie #Hashdos dabei heraus (hier werden schnelle (schwache) Hashfunktionen als Index für Speicher-Tabellen genutzt und der Code reagiert ineffiziernt bei Kollisionen, die man sich aber mit wenig Aufwand konstruieren kann, um dann gezielt eine Overload herbeizuführen)

Gehen wir aber mal davon aus, unsere Hashfunktion sei ideal und habe einen Ergebnisraum von 128bit (wie zum Beispiel md5). Wenn sie also alle oben genannten Anforderungen erfüllt, dann kann sie genau

nhashes = 2128 = 3,4 × 1038

unterschiedliche Dateien abbilden und ich habe – beim Raten – eine Wahrscheinlichkeit von

pkollision = 1/(2128) = 2.9 × 10-39

mit der ich eine kollidierende Datei finde. (Wie gesagt, md5 ist kaputt, weshalb man in der Praxis eine sehr viel bessere Wahrscheinlichkeit hat)

Bei n=(2128)+x Dateien auf dieser Welt steigt also die Wahrscheinlichkeit von Kollisionen linear mit x an.
Setzen wir diese Zahl mal in Bezug, um sie uns zu verdeutlichen.

Beispiel 1

Es gibt n=232, also sehr, sehr viel weniger IPv4-Adressen auf der Welt (die sich jetzt langsam dem Ende zuneigen),
weshalb man nun auf IPv6 umsatteln möchte, das um den Faktor 296 mehr Adressen ermöglicht, nämlich genau (tadaaa) 2128, was dann reichen soll, um jedem der 7 Milliarden Menschen auf der Erde

n = (2128)/(7*109) = 4,8*1028

IP-Adressen geben zu können.

Beispiel 2

Eine 1GB-Datei enthält ~8,5*109 bits
Es sind also 28589934592 unterschiedliche 1GB-Dateien möglich, ich kann aber nur 2128 unterschiedliche Hashes haben, also gibt es unter der Vorraussetzung, dass ich nur 1 GB-Dateien, davon aber “alle” habe,

nkollisionen/hash = 2(8589934592-128) = 28589934464

Kollisionen – und zwar pro Hashwert. Insgesamt sind es

nkollisionen_gesamt = 28589934592 – 2128

Wohlgemerkt: Das gilt bei der Annahme, dass alle Dateien genau ein GB groß sind – weshalb man üblicherweise bei einem Hashvergleich zur Identitätsprüfung nicht nur den Hash, sondern auch die Dateigröße heranzieht. Geht anstatt von “allen Dateien von 1 GB Größe” von “allen Dateien bis 1 GB Größe” aus, dann gibt es

nkollisionen -> ∞

aber leider auch so viele Eingabewerte! (und dummerweise benötigt das hashen von 1GB durchaus seine Zeit).

Fazit

Hashfunktionen eignen sich dann, wenn ich eine konkrete Hypothese habe, was der Inhalt einer Datei ist bzw. sein sollte, und genau das Prüfen möchte. Wenn ich die Größe, den Hash und meine Erwartung zusammen nehme, kann ich mit an Sicherheit grenzender Wahrscheinlichkeit davon ausgehen, dass es sich um den gewünschten Inhalt handelt.

Wenn aber Hashfunktionen zum Suchen einer Datei genutzt werden, wie es bei itWatch’s WhiteIT-Ansatz vorgesehen ist, dann wäre die sinnvolle Gegenmaßnahme, an der Datei einfach ein paar Bits (zum Beispiel in den Meta-Tags) automatisch zufällig zu generieren, um zu einem unterschiedlichen Hash zu führen und der Hashdatenbank zu entgehen.

Bei einer Integration ins Betriebssystem aller Rechner weltweit, wie sie geplant ist, würde ich mir aber sehr genau überlegen, wie ich mit Kollisionen umgehen will. Eine Idee wäre zum Beispiel das Bilden von Hashes über mehrere Einzelteile der Datei, um die Wahrscheinlichkeit einer Fehleinschätzung wg. Kolllision auszuliegen zu verringern. So etwas ähnliches habe ich bei Monoxyd als Verteidigung gegen das Dropship vorgeschlagen.

Zurück zur Frage:

Ja.

9 comments

„…weshalb man üblicherweise bei einem Hashvergleich zur Identitätsprüfung nicht nur den Hash, sondern auch die Dateigröße heranzieht.“

Der Weg, der mir zuerst in den Sinn kommt, wenn ich davon ausgehe, dass die Wahrscheinlichkeit für Kollisionen zu groß ist, ist es, den Bildbereich der Hashfunktion zu erweitern. Statt einen 128bit Hash mit einer etwa 33bit großen Dateigrößenangabe zu verwenden, setze ich also gleich eine Hashfunktion mit 160bit ein.

Vielleicht wäre es nicht schlecht, wenn man weiß, wogegen man sich absichern will. Aber eine kryptographisch sichere Funktion erscheint mir auf den ersten Blick sinnvoller als die Dateigröße anzuhängen. Vermutlich eben, weil ich mir gerade ausmale, wie gehäuft bestimmte Dateigrößen im gesamten Dateienpool auftauchen mögen. Etwa, weil sich vielleicht „viele“ Leute 1MB-große Keyfiles für TrueCrypt-Container erstellen. Oder in 100MB gesplittete Multi-Volume-Archive verwenden. Oder…

Gibt es zu dem Dateigröße-Übertragen eigentlich einen tieferen Hintergedanken? Oder macht man das nur, weil man die Dateigröße sowieso wissen und beim Hash nicht gleich das nächste Fass aufmachen will?

by Johann on 14. März 2012 at 22:12. #

@Johann
“setze ich also gleich eine Hashfunktion mit 160bit ein.”

Randbemerkung 2: Wenn die Hashfunktion einen kleinen Ergebnisraum hat, dann geht natürlich auch das Raten schneller. Stellen wir uns zur Vereinfachung eine Hashfunktion mit nur 10 möglichen Hashes vor. Deshalb haben wir uns von SHA-1 über SHA-256 zu SHA-512 entwickelt.

-> inzwischen macht man sich über 512bit Gedanken. Nachteil ist dabei, dass die Anforderungen 4. und 5. leiden, also die Berechnung länger dauert, und unsere Hash-Datenbank mehr Platz benötigt.

Der Grund, warum man die Größe mit zu Rate zieht, ist viel trivialer: Wenn die Datei nicht die gleiche Größe hat, dann brauche ich gar keinen Hash mehr zu berechnen, sie kann ja gar nicht intakt/korrekt sein ;-) Das ist dann eine Aussage, die man mit einer Irrtumswahrscheinlichkeit perror=0 treffen kann, während, wenn man nur den Hash nimmt, die Irrtumswahrscheinlichkeit sehr viel höher (weil nicht = 0), wenn auch immer noch minimal, ist.

by Linus on 14. März 2012 at 22:19. #

Note to self: Hash-Berechnung und Speicherung ist aufwändig. Vergisst man als Endanwender ja immer. Danke für die Antwort.

Aber bei der Irrtumswahrscheinlichkeit ist IMHO ein Wurm drin. Die Wahrscheinlichkeit für einen (Falsch-Positiv-)Irrtum kann ja bei beiden Methoden null sein. Verschiedene Hashes bedeuten ja genauso wie verschiedene Dateigrößen stets verschiedenen Dateien.

by Johann on 15. März 2012 at 00:48. #

“Verschiedene Hashes bedeuten ja genauso wie verschiedene Dateigrößen stets verschiedenen Dateien.”

Stimmt. Ich meinte:

Datei hat gleiche Größe: pgleiche Datei = 1/2nbits der Datei
Datei hat nicht die gleiche Größe: pgleiche Datei = 0
Datei hat gleichen Hash: pgleiche Datei = 1/nmögliche Kollisionen,
(wobei nmögliche Kollisionen für alle Dateien beliebiger Größe gilt),
also dass gleicher Hash kein eindeutiger Beweis ist, dass die Datei jene ist, die ich suche.

Es ist also eine Frage der Perspektive, denn natürlich gilt, wie du richtig sagst:

Datei hat unterschiedlichen Hash: pgleiche Datei = 0, unabhängig von der Größe.

Ökonomisch prüfend würde ich aber immer zuerst auf die Größe schauen, bevor ich überhaupt den Hash errechne.

by Linus on 15. März 2012 at 00:57. #

Geld need anyone people of this World come here and take it…

Zu Kollisionen in Hashfunktionen und dem (Un)sinn, sie zur Suche zu verwenden. › Linus Neumann…

by Geld need anyone people of this World come here and take it on 29. März 2012 at 14:47. #

Gibts noch ein Kommentar zu den drei Abmahnungen? Wer hat weswegen abgemahnt?

by Bernd on 1. April 2012 at 10:39. #


Jeder mögliche Hash kann auch tatsächlich vorkommen (Subjektivität)

Kann es sein, dass du hier “Surjektivität” meinst?

by Verschlüssi on 8. April 2012 at 21:36. #

ja, da kam wohl kurz doch der Psychologe durch…
Danke für den Hinweis!

by Linus Neumann on 9. April 2012 at 13:47. #

Bits in den Metadaten zu ändern reicht leider nicht. Wir haben vor mehr als zehn Jahren schon Hashes über MP3-Files generiert, die Metadaten schlicht ignorierten. Das selbe Prinzip gilt für alle Container-Formate. Abhilfe schafft hier eigentlich nur die erwähnte Segmentierung, aber die funktioniert in Containerformaten auch nur, wenn die Offsets der eigentlichen Daten konsistent bleiben, sonst kann man leere Container einschieben die dann auch alle folgenden Hashes verändern. Im Falle von Filesharing ist das natürlich Blödsinn, aber für richtige Nachweise auf Inhaltsgleichheit anstatt Dateigleichheit ist das schon interessant. Leider kommt man auch dort von einem Problem zum Nächsten: wenn sich die Kodierung ändert, aber die Information gleich bleibt, dann ist das Hashing besonders wertfrei. :)

by Franco on 30. Mai 2012 at 00:23. #

Leave your comment

Required.

Required. Not published.

If you have one.