Die erstaunliche Macht der Hash-Funktionen

Inhaltsverzeichnis

Drei Kryptografie-Experten an der Stanford University kamen kürzlich auf eine clevere Idee, wie man das bekannte Problem des Identitätsdiebstahls im Internet lösen könnte. Gerissene Hacker aus Russland, China und anderen Ländern schicken massenweise E-Mails, die so aussehen, als würden sie von Zahlungsdienstleistern wie der Citibank oder PayPal stammen. Millionen von Kunden erhalten diese Nachrichten, in denen sich HTML-Links befinden, die unbedarfte Benutzer auf gefälschte Websites führen. Die sehen aus wie die echten, sammeln aber nur Usernamen und Passwörter, um den Dieben Zugriff auf fremde Konten zu geben.

Aber die Eingabe von Usernamen und Passwörtern auf bösen Websites ist nicht die einzige Gefahr, die dem Konsumenten im Internet droht. Ein potenziell noch größeres Problem ist die Tatsache, dass viele auf verschiedenen Websites immer die gleichen Account- und Passwortkombinationen nutzen. So sind sie zwar leichter zu behalten, doch skrupellose Homepagebetreiber könnten bei einem Gewinnspiel eingesammelte Daten für Angriffe auf das Konto des Benutzers bei einer Online-Bank nutzen.

Die Lösung, die die Stanford-Forscher Blake Ross, Dan Boneh und John Mitchell nun vorgestellt haben, versucht all das zu verhindern. Ihr cleveres Plugin für den Internet Explorer verschlüsselt, was man in ein Passwort-Feld eintippt - und zwar für jede Website anders. Das Passwort ergibt sich aus dem, was man eintippt und der Adresse der Seite selbst.

Natürlich benutzen viele Leute eine ähnliche Strategie. Ihr Hotmail-Passwort heißt beispielsweise "nosmis-hotmail", während ihr Kennwort für den Yahoo!-Datingdienst "nosmis-Yahoo!" lautet. Aber eine solche Strategie ist leicht zu durchschauen. Die Verschlüsselungsmethode der Stanford-Forscher nutzt statt dessen eine mathematische Funktion - einen so genannten kryptografischen "Hash". Dabei handelt es sich um eine Berechnung, die nur in eine Richtung durchführbar ist - sie verwandelt das, was der Nutzer eingibt, in einen Buchstaben- und Zahlensalat, der nicht mehr in das Passwort zurückverwandelt werden kann. Ein Angreifer müsste also pro Website jeweils unterschiedliche Passwörter entschlüsseln, weil sich jeweils andere kryptografische Hash-Werte ergeben. Der Grund: Der Hash besteht aus der Domain der Website und dem Kennwort - und die Domain wechselt ja.

Yahoo! gehört zu den Unternehmen, die kryptografische Hash-Werte in ihren öffentlichen Angeboten breit nutzen. Im letzten Jahr wurde der Login-Prozess des Portals verändert, um die Seite abhörsicher zu machen. Der Standardweg, dies zu erreichen, wäre ihre Verschlüsselung. Aber eine solche Verschlüsselung kann langsam sein - besonders, wenn man eine der populärsten Seite im Internet betreibt.

Was Yahoo statt dessen tat, war seine Login-Seite mit einem so genannten "Challenge-Response"-System auszurüsten, das mit Hash-Werten arbeitet. Wenn man sich auf der Seite einloggt, lädt der Browser eine kryptografischen Hash-Funktion, die in JavaScript geschrieben wurde, von Yahoo-Server herunter. Zusammen mit dieser Funktion wird ein so genannter "Challenge"-Wert übertragen - eine kurze Sequenz aus Buchstaben und Zahlen. Wenn man nun sein Passwort eingibt, nimmt der Browser das Passwort, ergänzt es um die von Yahoo geschickte Sequenz und wendet auf das Ergebnis die Hash-Funktion an. Deren Wert wird dann an Yahoo geschickt - eine echte Verschlüsselung ist nicht notwendig. Selbst wenn man sich in einem Internet-Café befindet, in dem Hacker den Web-Datenverkehr mitlesen, gibt es keine Möglichkeit, aus dem Hash-Wert wieder das Original-Passwort abzuleiten.

Dieses smarte Challenge-Response-System ist auch Teil des amerikanischen Tankstellen-Bezahlsystems Mobil Speedpass - deshalb ist dessen Chip mit seiner RFID-Funktechnik so schwer zu klonen. Andere RFID-Systeme nutzen Challenge-Response nicht, was Angriffe vergleichsweise einfach macht.

Wie also funktioniert die praktische Hash-Technik, die ein fundamentaler Baustein der digitalen Wirtschaft ist? Obwohl sie so weit verbreitet ist, bleibt sie sowohl für die Krypto-Experten, die sie anwenden, als auch für die Öffentlichkeit ein kleines Mysterium.

Hash-Funktionen nennt man manchmal auch Fingerabdruck-Funktionen (Englisch: Fingerprint) weil man mit ihnen einzigartige Fingerabdrücke einer digitalen Datei erstellen kann. Die Fingerabdrücke sind normalerweise 128 oder 160 Bit lange Zahlen, die als eine Sequenz von hexadezimalen Ziffern dargestellt werden. Der Fingerabdruck meines Namens im so genannten MD5-System sähe so aus: "c55bbe0f3ba258f5b1cb6d5b62b0b360". Hash-Funktionen sollen es zumindest theoretisch erlauben, dass zwei Dateien niemals den gleichen Wert ergeben.

Hash-Werte ändern sich sofort vollständig, wenn auch nur ein einziger Buchstabe ausgetauscht wird. Die Art, wie sich der Fingerabdruck verändert, ist dabei nicht vorhersehbar - wäre das anders, würde die Hash-Funktion auch nicht sehr nützlich sein.

Die erstaunliche Macht der Hash-Funktionen

Die meisten Hash-Funktionen, die heute benutzt werden, gehen auf eine Technik zurück, die der MIT-Professor Ron Rivest in den Achtzigern entwickelt hat. (Rivest ist als das "R" im RSA-Verschlüsselungsalgorithmus bekannt geworden, einem Public-Key-Verfahren, das in fast jedem Webbrowser steckt.) Damals arbeitete Rivest zusammen mit anderen Mathematikern an den Details grundlegender kryptografischer Verfahren, die wir heute für selbstverständlich halten. Die Hash-Funktionen wurden als eine Art kryptografisches Kompressionssystem erdacht - ein Weg, eine große Datei zu nehmen und diese dann auf einen kurzen String aus Buchstaben und Zahlen herunterzurechnen.

Die Fingerabdrücke sollen ein Ersatz für die Dateien selbst sein. Anstatt die gesamte Datei digital zu signieren, ließe sich ja auch der Hash-Wert signieren, meinten Rivest und andere Forscher. Public-Key-Kryptografie benötigt sehr viel Rechenleistung. Dank der Hash-Funktionen kann eine extrem große Datei nun fast so schnell signiert werden wie eine kurze.

Eines der grundlegendsten Dinge, die man mit einer Hash-Funktion machen kann, ist es, herauszufinden, ob sich eine Datei geändert hat - man muss nur den Hash berechnen und ihn aufschreiben. Später kann man ihn dann erneut berechnen - hat er sich nicht verändert, dann ist die Wahrscheinlichkeit sehr groß, dass sich auch die Datei nicht verändert hat.

Ein Beispiel: Sie benutzen eine Buchhaltungssoftware, um die Finanzen ihrer kleinen Firma zu managen und wollen für ein paar Tage in den Urlaub. Andere Leute müssen ihren Computer benutzen, sie wollen aber nicht, dass die Finanzdaten verändert werden. Eine einfache Methode wäre es, den kryptografischen Hash der Datei vor dem Verlassen des Büros auf einen Zettel niederzuschreiben. Zurück aus dem Urlaub berechnen sie den Hash einfach neu. Wenn die beiden Werte sich unterscheiden, wissen sie, dass jemand an den Daten herumgepfuscht hat.

Natürlich muss es nicht bei einer einzelnen Datei bleiben. Sie könnten die Hash-Werte jeder einzelnen Datei auf ihrem Rechner generieren und diese dann in eine neue Datei schreiben, beispielsweise "hashes.txt". Anschließend könnten sie den Hash von "hashes.txt" berechnen und diesen wieder aufschreiben. Nach der Rückkehr wiederholen sie den Prozess und können feststellen, ob irgendeine Datei auf ihrem Rechner verändert wurde. (Welche, finden Sie so nicht heraus. Aber das ist ein anderes Problem.)

Die Idee, den Hash-Wert eines Hash-Wertes zu berechnen, ist die Basis eines Anti-Hacker-Systems namens Tripwire, einem Intrusion Dectection System (IDS), das der Informatik-Professor Gene Spafford und sein Master-Student Gene Kim in den frühen Neunzigern entwickelt haben. (Spafford und ich haben zusammen fünf Bücher über Informatik verfasst.) Heute nutzen viele verschiedene Programme den Ansatz von Tripwire, um die Integrität von Computerdateien und Datenbanken zu überprüfen.

Hash-Werte von Hash-Werten zu nehmen, ist auch die Grundlage eines sicheren Zeitstempel-Dienstes, den Stuart Haber und Scott Stornetta 1990 bei Bellcore entwickelt haben. Der Dienst namens "Surety" macht es möglich, einen kryptografisch sicheren und nicht fälschbaren Beweis zu erstellen, dass ein Dokument, eine Fotografie oder eine andere Art von Datei zu einer bestimmten Zeit an einem bestimmten Datum existierte und seitdem nicht verändert wurde.

Die Surety-Technik berechnet einen so genannten "Hash-Baum", der auf den Hash-Werten aller Dokumente beruht, die einen Zeitstempel bekommen sollen. Die Wurzel dieses Baumes wird dann an einem öffentlichen Ort publiziert, beispielsweise auf den Kleinanzeigenseiten der New York Times. Man kann dann beweisen, dass das entsprechende Dokument an jenem Tag existierte, weil der Fingerabdruck des Dokumentes notwendig war, um den Fingerabdruck des Fingerabdrucks zu generieren, der dann in der Zeitung erschien.

Die erstaunliche Macht der Hash-Funktionen

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.

Die erstaunliche Macht der Hash-Funktionen

Man möchte meinen, dass der Regierungsstandard mit seinen 160 Bit sicherer ist als der 128 Bit lange MD5. Aber wie Clipper selbst wurde der SHA von der NSA entwickelt - und sowohl NIST als auch NSA weigerten sich, zu erklären, welchen Design-Prinzipien sie folgten. Einige Leute meinten, die NSA könne sich eine Hintertür in den Algorithmus eingebaut haben, damit sie sich Kollisionen auf Zuruf erstellen konnte. Eine solche Hintertür könnte zum Beispiel dazu benutzt werden, um gefälschte digitale Signaturen zu erstellen, was dann wiederum die CIA nützlich finden könnte. Eine gefälschte digitale Signatur könnte beispielsweise dazu genutzt werden, einen elektronischen Befehl zu unterzeichnen, der einem US-Spion Zugriff auf eine ausländische Datenbank ermöglicht.

Viele Kryptografie-Experten und andere Wissenschaftler analysierten den SHA-Algorithmus, konnten aber keine Fehler finden. Am 11. Mai 1993 wurde SHA zum nationalen sicheren Hash-Algorithmus erklärt. Die Tinte auf der Veröffentlichung war noch nicht trocken, da musste das NIST schon erklären, es habe einen Fehler gemacht. Aus Gründen, die das NIST damals nicht nennen wollte, publizierte es eine modifizierte Version des SHA - den Algorithmus, den wir heute als SHA-1 kennen.

Für die Verschwörungstheoretiker in der Kryptografie-Community (und davon gibt es viele) war das ein gefundenes Fressen. War SHA so mächtig, dass die NSA sich dazu entschieden hatte, die Technik zu entschärfen? Oder hatte die NSA vielleicht eine Hintertür im SHA eingebaut - und jemand beim NIST hatte sie entdeckt? Waren beide Technologien gleich sicher und die Krypto-Experten bei der NSA spielten den Leuten nur einen Streich?

Im August 1998 erfuhr die Welt mehr oder weniger, was hinter dem SHA gegen SHA-1-Mysterium steckte. Florent Chabaud und Antoine Joux, zwei französische Kryptografen, entdeckten einen theoretischen Angriff gegen die erste Version von SHA - einen, gegen den SHA-1 gefeit war. Mit ziemlicher Sicherheit kannten die Leute bei der NSA diesen Angriff und schlugen SHA-1 als Gegenmaßnahme vor. Das Interessante daran ist, dass die NSA-Kryptografen wohl noch nicht wussten, dass es eine Angriffsmöglichkeit gegen SHA gab, als dieser 1993 vorgeschlagen wurde - was bedeutet, dass die Top-Adresse in Sachen Kryptografie den Top-Kryptografen an den Universitäten höchstens fünf Jahre voraus war.

Heute werden Hash-Funktionen auch häufig dazu genutzt, wiederholbare aber nicht vorhersehbare (Pseudo-)Zufallszahlen zu generieren, die dann dazu benutzt werden, aus eingegebenen Passwörtern Werte zu generieren, die für die Verschlüsselungs verwendet werden können. Statt Passwörter direkt abzulegen, speichern die meisten Computersysteme nur deren Hash-Wert. So ist es für einen Einbrecher in diese Rechner nicht möglich, die Passwörter aller Nutzer auszulesen.

Hash-Funktionen sind in Anti-Spam-Systemen ebenso im Gespräch wie als Basis digitalen Geldes. Vor einigen Jahren schrieb der Mathematiker Peter Wayner ein Buch namens "Translucent Database", in dem er zeigte, wie Hash-Funktionen dazu benutzt werden könnten, Informationen in einer geschützten Datenbank zu speichern. Das Studentensekretariat an einer Universität könnte so beispielsweise zwar die Sozialversicherungsnummern der Studenten in seiner Datenbank speichern und sie zur Identifikation nutzen. Aber niemand in dem Büro hätte die Möglichkeit, eine Liste der Studenten mit diesen Nummern zu generieren. Bislang sind diese Ansätze allerdings nicht sehr weit fortgeschritten.

Alles in allem sind die kryptografischen Hash-Werte eine der interessantesten und nützlichsten mathematischen Techniken, die Kryptografen in den letzten 20 Jahren erfunden haben - und es finden sich immer noch ständig neue Anwendungsbereiche dafür.

Von Simson Garfinkel; Übersetzung: Ben Schwan. (sma)