Fingerabdrücke Ihrer Dateien

Drei Kryptografen der Stanford University haben kürzlich eine clevere Lösung für das anhaltende Problem des Identitätsdiebstahls im Internet gefunden. Schlaue Hacker in Russland, China und anderen Ländern versenden stapelweise E-Mail-Nachrichten, die aussehen, als kämen sie von Finanzinstituten wie Citibank oder Paypal. Millionen von Verbrauchern erhalten diese Nachrichten, in die HTML-Links eingebettet sind, die den ahnungslosen Empfänger zu ähnlichen Websites führen, die an weit entfernten Orten betrieben werden. Sie werden aufgefordert, einen Benutzernamen und ein Passwort einzugeben, und dann hat der Hacker die Schlüssel zu Ihrem Bankkonto.

Aber gute Benutzernamen und Passwörter, die auf schlechten Websites eingegeben werden, sind nicht die einzige Bedrohung, der Verbraucher ausgesetzt sind. Ein potenziell größeres Problem besteht darin, dass viele Benutzer auf mehreren Websites dieselbe Kombination aus Benutzername und Kennwort verwenden. Dies erleichtert das Auswendiglernen, bedeutet jedoch, dass ein skrupelloser Website-Betreiber eine Liste mit Benutzernamen und Passwörtern beispielsweise von einer Internet-Gewinnspiel-Site nehmen und damit versuchen kann, in Online-Bankkonten einzubrechen.

Daher haben die Stanford-Kryptographen Blake Ross, Dan Boneh und John Mitchell ein cleveres Plug-In für Internet Explorer entwickelt, das dieses Problem löst, indem es das, was Sie in das Passwortfeld eingeben, verschlüsselt, sodass jede Website ein anderes Passwort sieht – ein Passwort, das auf beiden basiert, was Sie eingeben und auf der Domain der Website selbst.

Nun verwenden viele Leute eine Variante dieser Strategie. Ihr Hotmail-Passwort könnte nosmis-hotmail sein, während ihr Yahoo! Das Passwort für die Kontaktanzeigen ist nosmis-Yahoo! Aber jede Strategie wie diese ist ziemlich einfach zu entschlüsseln. Die Methode zum Verschlüsseln von Passwörtern, die das Stanford-Trio entwickelt hat, basiert auf einer mathematischen Funktion, die als kryptografische Hash-Einwegfunktion bezeichnet wird und die Eingaben des Benutzers in ein Wirrwarr von Zahlen und Buchstaben auf eine Weise umwandelt, die nicht rückgängig gemacht werden kann. Da das Stanford-System den kryptografischen Hash sowohl der Website-Domain als auch des Benutzerpassworts berechnet, erhält der Hacker andere Passwörter als die legitimen. (Klicken Hier Details zu dieser cleveren Lösung zu finden.)

Ein Unternehmen, das kryptografische Hashes sehr öffentlich verwendet, ist Yahoo! Letztes Jahr hat Yahoo! hat den Login-Prozess auf seiner Website neu gestaltet, um ihn schnüffelsicher zu machen. Die Standardmethode hierfür ist die Verschlüsselung. Die Verschlüsselung kann jedoch langsam sein, insbesondere wenn Sie eine der beliebtesten Websites im Internet betreiben.

Also, was Yahoo! Stattdessen änderte er seine Login-Seite, um ein sogenanntes Challenge-Response-System basierend auf einem kryptografischen Hash zu verwenden. Wenn Sie versuchen, sich anzumelden, lädt der Yahoo!-Server eine in JavaScript geschriebene kryptografische Hash-Funktion in Ihren Browser herunter. Zusammen mit dieser Funktion ist eine kurze Abfolge von Buchstaben und Zahlen eine Herausforderung. Wenn Sie Ihr Passwort in den Anmeldebildschirm eingeben, nimmt Ihr Browser Ihr Passwort, fügt diese von Yahoo! bereitgestellten Zeichen an und berechnet den kryptografischen Hash der resultierenden Zeichenfolge. Der Browser sendet dann den resultierenden Wert zurück an Yahoo!, es ist keine Verschlüsselung erforderlich. Selbst wenn Sie sich in einem Cybercafe befinden und Ihren Webverkehr von belgischen Hackern ausspioniert haben, haben die Bösen keine Möglichkeit, den resultierenden Hash-Wert zu nehmen und Ihr ursprüngliches Passwort abzuleiten.

Dieses clevere Challenge-Response-System ist auch die Basis des Mobil Speedpass-Systems: Es macht das Klonen des Speedpass-Radiofrequenz-Identifikations-Tags (RFID) so schwierig. Andere RFID-Systeme verwenden kein Challenge-Response, was den Angriff vergleichsweise einfach macht.

Aber was ist diese kryptografische Hash-Funktion überhaupt?

Das unglaublich nützliche Hash

Kryptografische Hashfunktionen sind einer der grundlegenden Bausteine ​​der heutigen digitalen Wirtschaft. Dennoch bleiben sie in vielerlei Hinsicht ein Rätsel, sowohl für die Kryptografen, die sie erstellen, als auch für die allgemeine Öffentlichkeit, die sie täglich verwendet.

Hash-Funktionen werden manchmal als Fingerabdruckfunktionen bezeichnet, da sie verwendet werden können, um einen eindeutigen Fingerabdruck einer digitalen Datei zu erstellen. Die Fingerabdrücke sind normalerweise 128-Bit- oder 160-Bit-Zahlen, die als Folge von hexadezimalen Ziffern angezeigt werden. Der Fingerabdruck meines Namens, der das MD5-System verwendet, ist zum Beispiel c55bbe0f3ba258f5b1cb6d5b62b0b360. Hashfunktionen sind so konzipiert, dass zumindest theoretisch keine zwei Dateien jemals den gleichen Wert haben.

Damit Sie sich ein Bild von der Funktionsweise dieser Fingerprinting-Funktionen machen können, haben wir unten einen JavaScript-basierten MD5-Rechner eingebettet. Geben Sie einfach etwas Text ein und Sie können den MD5-Hash sehen. Beachten Sie, wie er sich jedes Mal vollständig ändert, wenn Sie einen Buchstaben hinzufügen, entfernen oder ändern. Die Art und Weise, wie sich der Fingerabdruck ändert, ist unvorhersehbar. Wenn wir vorhersagen könnten, wie er sich ändert, wären Dateifingerabdrücke nicht sehr nützlich.

Geben Sie unten Ihren Text ein:

Der MD5 ist:

Die meisten der heute verwendeten Hash-Funktionen basieren auf einer Technik, die in den 1980er Jahren von MIT-Professor Ron Rivest entwickelt wurde. (Rivest ist wahrscheinlich am besten dafür bekannt, dass es das R im RSA-Verschlüsselungsalgorithmus ist, dem Verschlüsselungsalgorithmus mit öffentlichem Schlüssel, der in praktisch jeden Webbrowser integriert ist.) Zu dieser Zeit arbeiteten Rivest und andere Mathematiker die Details der grundlegenden kryptografischen Operationen aus, die wir jetzt für selbstverständlich halten. Die Hash-Funktionen wurden als eine Art kryptografisches Komprimierungssystem konzipiert, mit dem eine große Datei auf eine kurze Reihe von Buchstaben und Zahlen zerkleinert werden kann.

Die Idee war, diese Fingerabdrücke als eine Art Ersatz für die Dateien selbst zu verwenden. Anstatt die gesamte Datei digital zu signieren, argumentierten Rivest und andere, könnten Sie den Hash digital signieren. Da die Kryptografie mit öffentlichen Schlüsseln viel anspruchsvolle Mathematik erfordert, machen Hashfunktionen das Signieren einer extrem langen Datei fast so schnell wie das Signieren einer kurzen Datei.

Eines der grundlegendsten Dinge, die Sie mit einer Hash-Funktion tun können, ist herauszufinden, ob sich eine Datei geändert hat: Berechnen Sie einfach den Hash einer Datei und schreiben Sie ihn auf. Später berechnen Sie den Hash erneut. Wenn sich der Hash nicht geändert hat, ist die Wahrscheinlichkeit überwältigend, dass sich auch die Datei nicht geändert hat.

Angenommen, Sie verwalten die Finanzen Ihres kleinen Unternehmens mit QuickBooks und möchten für ein paar Tage in den Urlaub fahren: Die Leute müssen Ihren Computer benutzen, aber Sie möchten sicherstellen, dass niemand die QuickBooks-Daten ändert. Eine einfache Sache, die Sie tun können, ist, den kryptografischen Hash der Datei vor dem Verlassen zu berechnen und die Nummer auf eine Karteikarte zu schreiben. Wenn Sie aus dem Urlaub zurückkommen, berechnen Sie einfach den Hash neu. Wenn die beiden Werte nicht übereinstimmen, wissen Sie, dass die Datei manipuliert wurde.

Natürlich müssen Sie nicht mit nur einer Datei aufhören. Sie könnten den kryptografischen Hash jeder Datei auf Ihrem Computer berechnen und alle in eine neue Datei namens hashes.txt einfügen. Sie könnten dann den Hash von hashes.txt berechnen und diesen Fingerabdruck auf Ihre Notizkarte schreiben. Wiederholen Sie den Vorgang, wenn Sie aus dem Urlaub zurückkommen, und Sie wissen schnell, ob sich eine Datei auf Ihrem gesamten Computer geändert hat. (Sie haben keine Möglichkeit zu wissen, welche Datei sich geändert hat, aber das ist ein anderes Problem.)

Diese Idee, den Hash eines Hashs zu berechnen, ist die Grundlage eines Intrusion Detection-Systems namens Tripwire, das der Informatikprofessor der Purdue University, Gene Spafford, und sein Doktorand Gene Kim Anfang der 1990er Jahre erfunden haben. (Spafford und ich haben fünf Bücher über Informatik gemeinsam verfasst.) Heutzutage verwenden viele verschiedene Programme diesen Tripwire-Ansatz, um die Integrität von Computerdateien und Datenbanken sicherzustellen.

Die Berechnung von Hashes von Hashes ist auch die Grundlage eines sicheren Zeitstempeldienstes, der von Stuart Haber und Scott Stornetta erfunden wurde, als die beiden 1990 bei Bellcore waren. Der Dienst namens Surety ermöglicht es, einen kryptographisch sicheren und fälschungssicheren Beweis dafür zu generieren, dass ein bestimmtes Dokument , Foto oder andere Datei zu einem bestimmten Zeitpunkt an einem bestimmten Datum existierte und seitdem nicht geändert wurde.

Die Surety-Technik funktioniert, indem sie einen Hash-Baum basierend auf den Hash-Codes jedes Dokuments berechnet, das mit einem Zeitstempel versehen ist. Die Wurzel des Baumes wird dann an einem bekannten Ort veröffentlicht und könnte zum Beispiel in einer Kleinanzeige im New York Times . Sie können beweisen, dass Ihr Dokument an dem betreffenden Tag existierte, indem Sie nachweisen, dass der Fingerabdruck Ihres Dokuments erforderlich war, um die Fingerabdrücke zu erstellen, die in der Zeitung erschienen sind.

Andere Unternehmen und sogar der US-Postdienst haben seitdem ihren eigenen elektronischen Zeitstempeldienst eingerichtet. Alle diese Systeme verlassen sich jedoch auf eine Organisation, die als vertrauenswürdiger Dritter agiert und Ihr Dokument mit ihrem privaten Schlüssel signiert. Das Problem bei diesem Ansatz ist, dass der Drittanbieter absolut vertrauenswürdig sein muss: Wenn dieser Drittanbieter beschließt, eine Signatur mit dem falschen Datum zu erstellen, oder es einem Hacker gelingt, den privaten Schlüssel des Drittanbieters zu stehlen, gibt es keine Möglichkeit, dies zu tun eine betrügerische Unterschrift von einer gültigen unterscheiden. Es ist natürlich auch möglich, betrügerische Surety-Signaturen zu erstellen, aber Sie müssen entweder in der Zeit zurückgehen und ändern, was in The . gedruckt wurde New York Times , oder reisen Sie um die ganze Welt, finden Sie jede Kopie, die gedruckt wurde, und ändern Sie den alten Fingerabdruck gegen den neuen.

Wie Hash-Funktionen funktionieren

Deshalb sind Hash-Funktionen hilfreich. Schauen wir uns nun an, wie sie tatsächlich aussehen.

Zu den heute am weitesten verbreiteten Hashfunktionen zählen die sogenannten MD5 (für Message Digest #5). MD5 erzeugt einen 128 Bit langen Hash, der üblicherweise als Folge von 32 hexadezimalen (Basis 16) Ziffern geschrieben wird. Wenn Sie meinen Namen nehmen und mit MD5 verarbeiten würden, erhalten Sie diese scheinbar zufällige Zeichenfolge:

c55bbe0f3ba258f5b1cb6d5b62b0b360

Oder, um es mathematischer zu formulieren:

MD5 (Simson Garfinkel) = c55bbe0f3ba258f5b1cb6d5b62b0b360

Jedes dieser hexadezimalen Zeichen repräsentiert 4 Bits; der MD5-Wert meines Namens ist eigentlich:

1100010101011011101111100000111100111011101
0001001011000111101011011000111001011011011
0101011011011000101011000001011001101100000

Die meisten Leute arbeiten mit der hexadezimalen Darstellung, weil es ziemlich einfach ist, zwei Hashes zu sehen und zu erkennen, ob sie gleich oder unterschiedlich sind.

MD5 funktioniert, indem es die Datei in viele kleine Teile aufteilt und dann jeden dieser Brocken nimmt und Hunderte von mathematischen Operationen durchführt, die die Bits mischen, invertieren, transponieren und auf andere Weise in ein unkenntliches Durcheinander verarbeiten. Das Wort nicht wiederzuerkennen in dieser Beschreibung ist der Schlüssel. Die grundlegende Anforderung an eine gute Hash-Funktion besteht darin, dass es unmöglich sein sollte, den Fingerabdruck einer Datei vorherzusagen, ohne sich tatsächlich um die Berechnung dieses Fingerabdrucks zu bemühen. Es darf keine Abkürzungen geben. Wenn ja, können Sie die Hash-Funktion möglicherweise rückwärts ausführen und eine Datei erstellen, die einen bestimmten Hash enthält, beispielsweise den Hash einer anderen Datei. Tatsächlich bricht die gesamte Sicherheit von Hash-Funktionen völlig zusammen, wenn es möglich ist, zwei Dateien mit dem gleichen Hash zu generieren.

Das Schöne an der Hash-Funktion ist, dass selbst eine winzige Änderung der Eingabe eine dramatische Änderung der Ausgabe bewirkt. Mathematisch sind die Funktionen so ausgelegt, dass jedes Bit in der Ausgabe eine 50-prozentige Chance hat, sich für jedes einzelne Bit, das in der Eingabe geändert wird, zu ändern.

Schauen wir uns einen anderen MD5-Hash an, dieser eine etwas andere Darstellung meines Namens:

MD5 (Simson L. Garfinkel) = df876e8e6f548d5be698fab7f06dd278

Die bloße Zugabe von L. erzeugt einen völlig anderen Hash. Wenn Sie die beiden Hashes Bit für Bit vergleichen, werden Sie feststellen, dass sich 63 der 128 Positionen von 0 auf 1 oder 1 auf 0 geändert haben und die anderen 65 unverändert geblieben sind.

Leider hat die ganze Theorie der kryptographischen Hashfunktionen ein riesiges Problem. Die Nutzung dieser Funktionen setzt voraus, dass es keine sogenannten Kollisionen gibt. Entweder versehentlich oder absichtlich, es sollten keine zwei Dateien mit demselben kryptografischen Fingerabdruck vorhanden sein. Und wie sich herausstellt, ist dies eine unmögliche Voraussetzung.

Der Grund ist ziemlich einfach. Datei-Fingerabdrücke haben eine feste Größe, was bedeutet, dass es eine endliche Anzahl möglicher Fingerabdrücke gibt. Dateien hingegen können jede beliebige Größe haben. Somit gibt es mehr mögliche Dateien als Fingerabdrücke, und daher muss es mindestens einen Fingerabdruck geben, der der Fingerabdruck mehrerer Dateien ist. Der mathematische Begriff dafür ist das Schubladenprinzip. Selbst wenn Sie sich auf Dateien beschränken, die nur neun Zeichen lang sind, gibt es immer noch 256-mal so viele mögliche Dateien wie mögliche Fingerabdrücke.

Dass das Schubladenprinzip Hash-Funktionen nicht völlig sinnlos macht, liegt daran, dass es erstaunlich viele mögliche Fingerabdrücke gibt, weit mehr als die Anzahl der Dateien auf dem Planeten. (Bei MD5 gibt es 2128 mögliche Fingerabdrücke. Jetzt beträgt die Gesamtzahl der jemals hergestellten Computerfestplatten nur etwa 229. Wenn jede Festplatte eine Million einzelne Dateien hätte, eine grobe Überschätzung, wären es immer noch nur 249 einzelne Dateien. Das ist viel , viel, viel kleinere Zahl als 2128.)

Die SHA-1-Kontroverse

Für Tutorialzwecke habe ich die MD5-Hash-Funktion verwendet. Aber heutzutage wird MD5 in Betracht gezogen bestehen Stattdessen wechselt der Großteil der Welt zum Secure Hash Algorithm der US-Regierung, bekannt als SHA-1, ein Standard, der Anfang der 1990er Jahre von den National Institutes of Standards and Technology (NIST) übernommen wurde.

Heute ist SHA-1 ein weithin respektierter Algorithmus, aber er hat eine bewegte Geschichte. Bereits 1993 versuchte die US-Regierung, die Industrie dazu zu bringen, das sogenannte geheime Verschlüsselungssystem Clipper Chipa einzuführen, das von der National Security Agency entwickelt wurde. Während der sogenannten Kryptokriege, die um Clipper wüteten, schlug NIST vor, dass die US-Regierung ihren eigenen sicheren Hash-Algorithmus als Teil der Federal Information Processing Standards einführt. Hashfunktionen sollten aus technischen Gründen doppelt so viele Bits haben wie die Verschlüsselungsalgorithmen, mit denen sie arbeiten. Clipper war ein 80-Bit-Verschlüsselungsalgorithmus, daher wurde der Standard entwickelt, um einen 160-Bit-Fingerabdruck zu erzeugen.

Man könnte meinen, dass der Regierungsstandard mit seinem 160-Bit-Fingerabdruck sicherer wäre als der 128-Bit-MD5. Aber wie Clipper selbst wurde SHA von der National Security Agency entworfen, und sowohl NIST als auch die NSA lehnten es ab, die Prinzipien zu erklären, die in seinem Design verwendet wurden. Einige Leute fragten sich, ob die NSA möglicherweise eine Art Hintertür im Algorithmus versteckt hat, damit die Behörde bei Bedarf Kollisionen generieren könnte. Eine solche Hintertür könnte beispielsweise verwendet werden, um gefälschte digitale Signaturen zu erstellen, die für die CIA nützlich sein könnten. Eine gefälschte digitale Signatur kann beispielsweise verwendet werden, um eine elektronische Bestellung zu unterzeichnen, die einem US-Spion Zugang zu einer Datenbank im Ausland gewährt.

Viele Kryptographen und andere Akademiker analysierten den SHA-Algorithmus und konnten nichts Falsches daran finden. Am 11. Mai 1993 proklamierte NIST SHA als den sicheren Hash-Algorithmus der Nationen. Aber die Tinte war bei diesem Dekret kaum getrocknet, als NIST ankündigte, dass es einen Fehler gemacht hatte. Aus Gründen, die zu diesem Zeitpunkt nicht bekannt waren, veröffentlichte NIST eine modifizierte Version des Secure Hash Algorithm, den Algorithmus, den wir heute SHA-1 nennen.

Die Verschwörungstheoretiker in der Kryptografie-Community (und es gibt viele) hatten einen großen Tag. War die SHA so mächtig, dass die NSA beschlossen hatte, sie zu verdummen? Oder hatte die NSA vielleicht eine Hintertür in SHA errichtet und jemand vom NIST hatte es herausgefunden? Waren beide Algorithmen gleich sicher, und die Kryptografen der NSA haben nur die Köpfe der Leute durcheinander gebracht?

Im August 1998 erfuhr die Welt mehr oder weniger die Antwort auf das Rätsel SHA vs. SHA-1. Florent Chabaud und Antoine Joux, zwei französische Kryptographen, entwickelten einen theoretischen Angriff gegen die erste Version des SHAan-Angriffs, gegen die SHA-1 zufällig sicher war. Mit ziemlicher Sicherheit wussten die Leute bei der NSA von diesem Angriff und schlugen SHA-1 als Gegenmaßnahme vor. Was hier interessant ist, ist, dass die Kryptografen der NSA wahrscheinlich nichts von dem Angriff wussten, als SHA 1993 zum ersten Mal vorgeschlagen wurde, was bedeutet, dass die weltweit führende Kryptografieagentur den Kryptografen in der Wissenschaft nur fünf Jahre voraus war.

Heutzutage werden Hash-Funktionen auch häufig verwendet, um wiederholbare, aber unvorhersehbare Zufallszahlen zu generieren, um eingegebene Passwörter in Werte umzuwandeln, die als Verschlüsselungsschlüssel verwendet werden können. Anstatt Passwörter direkt zu speichern, speichern viele Computersysteme den Hash eines Passworts. Dies verhindert, dass jemand, der in einen Computer einbricht, das Passwort aller anderen lernt.

Hash-Funktionen wurden als Mittel zur Bekämpfung von Spam und als Grundlage für digitale Kassensysteme vorgeschlagen. Der Mathematiker Peter Wayner veröffentlichte ein Buch mit dem Titel Transparente Datenbanken vor einigen Jahren, in dem er zeigte, wie Hash-Funktionen verwendet werden können, um Informationen in einer Datenbank auf eine Weise zu speichern, die von der Organisation, die die Datenbank betreibt, geschützt wird. Eine Hochschulzulassungsabteilung könnte zum Beispiel die Sozialversicherungsnummern von Studenten in der Datenbank speichern, damit diese Nummern weiterhin als Identifikationsnummer für Bewerbungen verwendet werden können, aber damit sich niemand in der Zulassungsstelle an ein Terminal setzen und eine Liste der Studenten erhalten kann und ihre Nummern. Bisher hat sich jedoch keiner dieser Ansätze wirklich durchgesetzt.

Alles in allem sind kryptografische Hashes eine der interessantesten und nützlichsten mathematischen Techniken, die sich Kryptographen in den letzten 20 Jahren ausgedacht haben und immer wieder neue Verwendungen für sie fanden.

verbergen