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

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 ineffizient 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 Voraussetzung, 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. Kollision zu verringern. So etwas ähnliches habe ich bei Monoxyd als Verteidigung gegen das Dropship vorgeschlagen.

Zurück zur Frage:

Ja.