Seite 3: Die erstaunliche Macht der Hash-Funktionen

Inhaltsverzeichnis

Andere Firmen und sogar die amerikanische Post haben seither elektronische Zeitstempel-Dienste entwickelt. All diese Systeme nutzen aber immer irgendeine Organisation, die als vertrauenswürdiger Dritter dient - sie unterschreibt dann das Dokument mit ihrem so genannten Private Key. Das Problem bei diesem Ansatz ist, dass die Drittpartei tatsächlich vollständig vertrauenswürdig sein muss. Wenn sich diese Partei dazu entschließt, eine Signatur mit dem falschen Datum herauszugeben oder ein Hacker den Private Key der Organisation stiehlt, ist es nicht mehr möglich, eine echte von einer falschen Signatur zu unterscheiden. Es ist natürlich auch möglich, eine falsche Surety-Signatur zu erstellen, aber man müsste schon in die Vergangenheit reisen können, um das zu verändern, was in der New York Times stand. Oder man müsste auf der ganzen Welt die Ausgabe des fraglichen Tages zusammensuchen, und die darin gemachten Angaben verändern.

Hash-Funktionen sind also ausgersprochen nützlich. Hier kommt, wie sie funktionieren: Eine der am weitesten verwendeten Hash-Funktionen ist der so genannte MD5 (für "Message Digest #5"). MD5 produziert einen Hash, der 128 Bit lang ist und normalerweise aus einer Sequenz von 32 hexadezimalen Zahlen besteht. Wenn man meinen Namen mit MD5 bearbeitet, kommt wie bereits erwähnt "c55bbe0f3ba258f5b1cb6d5b62b0b360" heraus. Etwas mathematischer ausgedrückt bedeutet das:

MD5("Simson Garfinkel")=c55bbe0f3ba258f5b1cb6d5b62b0b360.

Jedes dieser hexadezimalen Zeichen steht für vier Bit, der MD5-Wert lautet also eigentlich:

1100010101011011101111100000111100111011101 0001001011000111101011011000111001011011011 010101101101100010101100001011001101100000

Die meisten Leute arbeiten mit der hexadezimalen Darstellung, weil es so einfacher ist, zwei Hash-Werte zu vergleichen und daraus zu schließen, ob sie identisch sind.

MD5 bedient sich einer Methode, bei der eine Datei in viele kleine Teile aufgesplittet wird. Jeder dieser Teile wird dann durch hunderte mathematischer Vorgänge vermischt, umgekehrt, vertauscht und anderweitig bearbeitet, um aus den Bits ein nicht wiederzuerkennendes Chaos zu machen. Das Wort "nicht wiedererkennbar" ist dabei das wichtigste. Das fundamentale Kriterium einer guten Hash-Funktion ist, dass es unmöglich sein muss, den Fingerabdruck vorherzusagen, ohne ihn tatsächlich aus der Originaldatei zu berechnen. Es darf keine Abkürzungen geben. Wenn es welche gäbe, wäre es möglich, die Hash-Funktion rückwärts zu berechnen. So könnte man dann eine Datei erstellen, die einen bestimmten Hash-Wert hat - beispielsweise den einer anderen Datei. Die ganze Sicherheit der Hash-Funktionen fällt vollständig in sich zusammen, sobald es möglich ist, zwei Dateien zu generieren, die denselben Hash-Wert haben.

Das Schöne an Hash-Funktionen ist es, dass sogar eine klitzekleine Veränderung an einer Datei den Output dramatisch verändert. Mathematisch sind die Funktionen so angelegt, dass jedes Bit des Endergebnisses eine 50prozentige Wahrscheinlichkeit einer Veränderung hat, wenn nur ein einziges Bit im Input verändert wird.

Eine leicht veränderte Darstellung meines Namens ändert bereits den kompletten MD5:

MD5("Simson L. Garfinkel”)= df876e8e6f548d5be698fab7f06dd278

Wenn man sich die beiden Hash-Werte Bit für Bit ansieht, findet man heraus, dass sich 63 der 128 Positionen verändert haben - aus 0 wurde 1 und aus 1 wurde 0. 65 Werte blieben unverändert.

Unglücklicherweise gibt es in der Gesamttheorie der kryptografischen Hash-Funktionen ein riesiges Problem. Wenn man sie benutzt, darf es keine so genannten "Kollisionen" geben. Egal ob absichtlich oder zufällig, es darf niemals zwei Dateien geben, die den gleichen kryptografischen Fingerabdruck haben. Diese Voraussetzung ist allerdings praktisch unmöglich zu erreichen.

Der Grund dafür ist sehr einfach: Fingerabdrücke von Dateien haben eine festgelegte Größe, was bedeutet, dass es nur eine endliche Anzahl verschiedener Fingerabdruck-Werte geben kann. Dateien können hingegen jede Größe annehmen. Dementsprechend gibt es mehr Dateien als Fingerabdrücke und so muss es also mindestens einen Fingerabdruck geben, der mehrere Dateien repräsentiert. Der mathematische Ausdruck hierfür ist das Verteilerfach-Prinzip. Selbst wenn wir uns auf Dateien beschränken, die maximal neun Zeichen lang sind, gibt es immer noch 256 mal so viele Dateien wie die mögliche Anzahl von Fingerabdrücken.

Der einzige Grund dafür, dass das Verteilerfach-Prinzip Hash-Funktionen nicht vollständig aushebelt, ist die erstaunliche Zahl von möglichen Fingerabdrücken. Tatsächlich sind es mehr, als es Dateien auf dem Planeten gibt. (Bei MD5 gibt es 2 hoch 128 mögliche Fingerabdrücke. Die Gesamtzahl aller Computerfestplatten, die jemals produziert wurden, liegt aber nur bei 2 hoch 29. Wenn jede Festplatte eine Million einzigartiger Dateien besäße, was viel zu viel wäre, gäbe es immer noch nur 2 hoch 49 individuelle Files. Das ist eine viel, viel kleinere Zahl als 2 hoch 128.)

Im obigen Beispiel habe ich mit MD5-Hash-Funktionen gearbeitet. Diese gelten heute allerdings als altmodisch - statt dessen ist die Welt derzeit dabei, voll auf den so genannten Secure Hash Algorithm, kurz SHA-1, umzusteigen. Er wurde von der US-Regierung entwickelt und vom National Institute of Standards and Technology (NIST) in den frühen Neunzigerjahren als Standard festgelegt.

Heutzutage ist SHA-1 weithin akzeptiert, obwohl er eine problembelastete Geschichte hat. 1993 versuchte die US-Regierung, die Industrie zur Annahme des so genannten Clipper-Chips zu bewegen - ein geheimes Verschlüsselungssystem, das die National Security Agency, kurz NSA, entwickelt hatte. In den so genannten "Crypto-Kriegen", die um Clipper tobten, schlug NIST der US-Regierung vor, dass sie ihre eigene sichere Hash-Funktion als Teil der IT-Standards des Landes festsetzen sollte. Aus technischen Gründen sollten Hash-Funktionen zweimal so viele Bits haben, wie die Verschlüsselungsalgorithmen, mit denen sie arbeiten. Clipper war ein 80-Bit-Verschlüsselungsstandard, also musste SHA-1 160-Bit-Fingerabdrücke generieren.