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
n_Dateien -> ∞ 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

n_hashes = 2¹²⁸ = 3,4 × 10³⁸

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

p_kollision = 1/(2¹²⁸) = 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=(2¹²⁸)+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=2³², 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 2⁹⁶ mehr Adressen ermöglicht, nämlich genau (tadaaa) 2¹²⁸, was dann reichen soll, um jedem der 7 Milliarden Menschen auf der Erde

n = (2¹²⁸)/(7*10⁹) = 4,8*10²⁸

IP-Adressen geben zu können.

Beispiel 2

Eine 1GB-Datei enthält ~8,5*10⁹ bits
Es sind also 2^8589934592 unterschiedliche 1GB-Dateien möglich, ich kann aber nur 2¹²⁸ unterschiedliche Hashes haben, also gibt es unter der Vorraussetzung, dass ich nur 1 GB-Dateien, davon aber “alle” habe,

n_{kollisionen/hash} = 2^{(8589934592-128)} = 2^8589934464

Kollisionen – und zwar pro Hashwert. Insgesamt sind es

n_{kollisionen_gesamt} = 2^8589934592 – 2¹²⁸

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

n_{kollisionen ->} ∞

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.

• Sylvia Johnigk vom FIFF Forum Informatikerinnen für Frieden und Freiheit
• Andreas Ruch, Wissenschaftlicher Mitarbeiter am Lehrstuhl für Kriminologie, Kriminalpolitik und Polizeiwissenschaft an der Ruhr-Universtität Bochum
• Nils Johanning, Geschäftsführer der Sicherheitsfirma Innotec, die an der Entwicklung von INDECT beteiligt ist.

habe ich über automatisierte Überwachungssysteme gesprochen. Moderiert hat Markus Heidmeier.
Hier geht es zur Sendungsbeschreibung und hier zum mp3-Dowload.

Bei diesem vom Träger der deutschen Wikipedia, dem Wikimedia e.V., ausgelobten Wettbewerb können teilnehmende Projekte zwischen 500 und 5.000€ Förderung für Ideen zur Förderung Freien Wissens gewinnen.

Projekteinreichungen hier entlang.

Ich habe mich bemüht, dafür zu argumentieren, den Fokus der Debatte auf die Forderungen der Piratenpartei nach Transparenz und Beteiligung zu legen, statt sich auf die Bevölkerungsgruppe der “Nerds” zu beziehen und die Inhalte aus den Augen zu verlieren.

Link zum dradio.
Link zum Mitschnitt (mp3).

Einen guten Demobericht gibt es noch bei Anne, die auch schon öfter über meinen Star des Tages, Lothar König berichtet hat. Über ihn habe ich jetzt auch noch mal was bei Netzpolitik geschrieben.

Linus Neumann wird 1983 im Ruhrgebiet geboren. Nach Auslandaufenthalten, Abitur und Zivildienst studiert er in Berlin Psychologie mit den Nebenfächern Politologie und forensische Psychiatrie. Er vertreibt nebenher im Eigenverlag mit dem Gestalter Roland Brückner die Kinderbuchserie “Mumpelmonster”, arbeitet als freiberuflicher Webdesigner und unterstützt zwei Lehrstühle der Humboldt-Universität, wo er sich komplexer Datenanalyse widmet. Mitte 2010 beginnt er für das Blog Netzpolitik.org zu schreiben und tritt im April 2011 dem Verein Digitale Gesellschaft bei, der sich für digitale Bürgerrechte engagiert. Im Frühjahr des gleichen Jahres entdeckt Linus auf seinem Fensterbrett ein Amselnest.

www.berlinfolgen.de
www.taz.de/berlinfolgen
www.2470media.com

Zum Video

Hier eine mp3 davon