Die Hashfunktion mal so richtig einfach erklärt
Wer sich mit der Blockchain Technologie auseinandersetzt, kommt um den Begriff “Hash” oder “Hashfunktion” nicht herum. Im Bitcoin Paper “Bitcoin: A Peer-to-Peer Electronic Cash System” von Satoshi Nakamoto findet sich das Wort schon im Abstract zwei Mal, im ganzen Paper kommt es über 50 mal vor.
Aber was ist denn eigentlich eine Hashfunktion genau? In einem Forum hab ich kürzlich nachgelesen, dass es sich bei der Hashfunktion um eine “nicht injektive Abbildung handelt, welche eine grosse Eingabemenge auf eine kleinere, meist skalare Zielmenge aus einer begrenzten Teilmenge der natürlichen Zahlen abbildet”.
Alles klar? Nein? Ich glaube, dass das ganz vielen so geht. Versteht mich nicht falsch, die oben genannte Definition ist korrekt, nur glaube ich, dass sie ein gewisses Mass an Vorwissen voraussetzt. Was nun?
Ein Mittel, das sich bei mir schon lange bewährt, ist der Grosseltern-Ansatz. Ich stelle mir dabei die folgende Frage: “Wie würde ich das den Grosseltern erklären?” Gerne möchte ich das im nächsten Abschnitt einmal versuchen. Also, ihr lieben Grosseltern, dann hört mir mal gut zu.
Der Grosseltern-Ansatz und: Was Hashfunktionen mit Bibliotheken gemeinsam haben
Liebe Grosseltern. Wenn ihr eure Bücher gelesen habt und diese nun zurück in die Bibliothek bringt, so hat der Bibliothekar eine ganz wichtige Aufgabe: Er muss das Buch an den richtigen Ort (richtige Position im richtigen Regal) zurückbringen, so dass es später von anderen Kunden wieder gefunden werden kann.
In der Regel nimmt der Bibliothekar hierzu den ersten Buchstaben des Nachnamens des Autors und weiss bereits, in welchem Regal er das Buch zurückstellen kann.
Und bereits haben wir eine erste einfache Hashfunktion in Aktion gesehen!
Im Grunde genommen macht der Bibliothekar nichts anderes, als die folgende einfache Hashfunktion auf das Buch anzuwenden:
Start der Hashfunktion
Nimm als Eingabewert den Namen des Autors. Als Ausgabewert (=Hashwert) gib den ersten Buchstaben des Nachnamens zurück.
Ende der Hashfunktion
Klingt das fast zu einfach? Glaubt mir, ist es nicht. Was wir hier haben, ist ein kleiner Algorithmus der eine richtige Hashfunktion beschreibt. Als Eingabe wird ein Name entgegengenommen und als Ausgabe kommt ein Hashwert mit fixer Länge (1) in der Form eines einzelnen Buchstabens zurück. Eine einfache, aber dennoch eine gültige Hashfunktion.
Ich glaube an dieser Stelle ist die Zeit bereits reif für eine erste einfache, ein wenig unscharfe aber dennoch nicht falsche Definition der Hashfunktion:
Einfache Definition einer Hashfunktion
- In eine Hashfunktion kann man beliebige Wörter, Buchstaben, Zahlen, Sonderzeichen, ja sogar ganze Sätze eingeben. Egal ob nur ein Wort wie “hallo” oder ein ganzes Buch, alles kann in eine Hashfunktion gefüttert werden (Beim Bibliothekar: Der Name des Autors, egal mit wie vielen Nachnamen oder zweiten Vornamen)
- Aus der Hashfunktion kommt ein einzigartiger Hashwert raus, der optimaler Weise immer die gleiche Länge hat (Beim Bibliothekar: Immer Länge 1)
- Die Hashfunktion soll effizient berechenbar sein. Es muss also ganz einfach sein, aus dem Eingabewert den Hashwert zu berechnen (Den ersten Buchstaben eines Nachnamens zu finden geht doch ziemlich fix)
- Die Hashfunktion ist zuverlässig und funktioniert immer gleich (sie ist deterministisch): Wenn man zwei mal den gleichen Eingabewert in eine Hashfunktion füttert, kommt zwei mal genau der gleiche Hashwert raus (Beim Bibliothekar immer “G” für “Goethe”)
- Die Umkehrung der Hashfunktion (also aus dem Hashwert den Eingabewert zu berechnen) soll aber so richtig schwierig sein (in unserem Fall ist es fast schon unmöglich herauszufinden, welcher Autor gemeint war, wenn man den Hashwert “G” sieht).
Wie erkläre ich es einem 10 Jährigen? Eine Hashfunktion ist etwas, was ganz einfach gemacht werden kann. Wenn man es aber wieder rückgängig machen möchte, ist das total schwierig. Beispiel: Eine Vase kaputt machen. Es ist ganz einfach, eine Vase vom Tisch runterzustossen und kaputt zu machen, aber es ist unglaublich schwierig, die Vase wieder “ganz” zu machen. Oder ein anderes Beispiel: Eier kochen. Geht ganz einfach, aber aus einem gekochten Ei wieder das rohe Ei zu kriegen ist sehr schwierig.
Die hier skizzierte Definition einer Hashfunktion liefert noch nicht das Werkzeug für eine gute Hashfunktion. Die gute Nachricht ist jedoch, dass sie eine stabile Basis bildet, auf welcher wir nun aufbauen können. Wenn man nämlich jetzt diese Definition um zusätzliche Eigenschaften erweitert, lässt sie sich verbessern, und im kryptographischen Sinne sogar “härten”. Und genau das wollen wir im nächsten Abschnitt machen.
Was macht eine gute Hashfunktion aus?
Ich glaube das war schon schwierig genug für die lieben Grosseltern und ich denke es ist an der Zeit, sie wieder gehen zu lassen. Danke fürs Zuhören. Für alle diejenigen, die noch mehr erfahren möchten: Lasst uns die oben beschriebene Hashfunktion weiter ausbauen und zu einer richtig guten Hashfunktion machen. Stellt euch dazu folgendes vor: Im Untergeschoss der Bibliothek, auf mehrere unterirdische Stockwerke verteilt, befindet sich die grösste wissenschaftliche Bibliothek des Landes. Zehntausende von Publikationen haben den Weg hierhin gefunden und warten sehnlichst darauf, von jemandem gelesen zu werden. Wenn ihr schon mal in so einer Bibliothek wart, dann ging es euch vielleicht wie mir, und ihr habt euch vielleicht gefragt:
“Wie viele dieser Publikationen sind echte Originale und wie viele davon sind Plagiate von anderen Publikationen?”
Plagiate sind nicht nur in der Forschung ein Problem, es handelt sich dabei um ein Phänomen, welches in immer mehr Bereichen unserer Gesellschaft Einzug hält (z.B. auch in der Musik). Und ich würde dieses Beispiel natürlich hier nicht erwähnen, wenn eine gute Hashfunktion nicht Abhilfe schaffen könnte :-) Ich möchte mit euch nun ein Gedankenexperiment machen.
Stellt euch einfach mal vor, wir hätten eine Hashfunktion, die für zwei unterschiedliche Eingabewerte, egal wie lang oder kompliziert die auch sein mögen, nie den gleichen Ausgabewert (Hashwert) liefert. Wir hätten also quasi einen “digitalen Fingerabdruck”. Das könnte dann etwa so aussehen:
Die ursprünglichen Hashfunktion in der Bibliothek war hierfür nicht gut genug, denn nicht nur Johann Wolfgang von Goethe und Günther Grass, sondern ganz viele andere Schriftsteller haben einen Nachnamen, der mit “G” beginnt. Wenn wir aber genau diese ursprüngliche Hashfunktion unseres Bibliothekars um folgende Anforderung erweitern, kommen wir der Sache schon näher:
Anforderung #1: Die Hashfunktion soll möglichst wenig Kollisionen haben (gemeint ist, dass verschiedene Eingabewerte nicht den gleichen Ausgabewert/Hashwert haben dürfen)
Diese Anforderung kann mit einem Zusatz sogar noch härter formuliert werden:
Zusatz zu Anforderung #1: Wenn sich der Eingabewert auch nur ein klein wenig verändert, verändert sich der Hashwert trotzdem sehr stark.
Gute Neuigkeiten: Solche Hashfunktionen (oder digitale Fingerabdrücke) gibt es, und sie erweisen der Plagiatserkennung einen unverzichtbaren Dienst. Es ist nämlich unglaublich aufwendig, ganze Publikationen oder verschiedene Abschnitte Wort für Wort, Zahl für Zahl zu vergleichen und auf Plagiate zu prüfen. Viel einfacher ist es da, die Publikationen oder Abschnitte daraus durch eine Hashfunktion zu lassen und die Hashwerte zu vergleichen.
Okay okay, so weit so gut. Wir haben jetzt eine einfache Beschreibung einer Hashfunktion und eine erste Anforderung, damit die Hashfunktion ein wenig besser wird. Der Bibliothekar, die Kundin und auch der Detektiv auf seiner Jagd nach Plagiaten sind wohl zufrieden. So what? War’s das jetzt? Und vor allem:
Was um alles in der Welt hat das mit Blockchains zu tun?
Sehr gute Frage! Und um diese Frage beantworten zu können, müssen wir einen Abstecher in die Welt der Kryptographie machen. Im folgenden Abschnitt werden wir näher auf die Bedeutung von Hashfunktionen in der Kryptographie eingehen (“Kryptographie”: Hurra, wir nähern uns also dem Wort “Crypto”). Den genauen Zusammenhang und die zentrale Bedeutung kryptographischer Hashfunktionen in der Welt der Blockchains werde ich in einem späteren Blogbeitrag weiter beleuchten.
Kryptographisch gute Hashfunktionen. Oder: So wird das bei euren Lieblingsseiten gemacht.
Warum brauchen wir Hashfunktionen der Kryptographie? Reicht es nicht, den Bibliothekar und die Bibliothekskunden mit Hashfunktionen zu plagen? Einer der vielleicht bekanntesten Anwendungsfällen von Hashfunktionen in der Kryptographie oder Informationssicherheit ist das Abspeichern von Passwörtern. Wenn ihr irgendwo im Internet ein Konto mit Benutzername/Passwort eröffnet (z.B. auf Twitter, Facebook, eurer Tageszeitung, etc.), dann wird euer geheimes und streng gehütetes Passwort nicht beim Dienstleister (z.B. Twitter) gespeichert. Oder andersrum: Twitter kennt dein Passwort nicht! Und will es auch nicht kennen! Und das ist auch gut so! Aber wie wird das denn gemacht? So geht’s:
- Ihr geht auf die Registrierungsseite (z.B. von Twitter) und gebt dort eure Informationen, wie z.B. Telefonnummer, Email Adresse und natürlich auch euer gewünschtes Passwort ein.
- Wenn ihr jetzt auf “Registrierung abschliessen” oder “Weiter” (oder was auch immer) klickt, dann wandert das ganze durch eine sichere Leitung zu Twitter.
- Twitter legt nun in einer eigenen Datenbank ein neues Profil für euch an. Alle Infos, die ihr beim Registrierungsprozess angegeben habt, werden hierbei abgespeichert, ausser: Das Passwort. Dieses wird zuerst durch eine Hashfunktion gejagt und erst danach in der Datenbank abgelegt.
- Wichtig: Twitter speichert nie dein Passwort in der eigenen Datenbank, sondern nur den errechnete Hashwert.
- Beim nächsten Login errechnet Twitter wieder zuerst den Hashwert aus dem Passwort, welches ihr bei der Login-Maske eingegeben habt, und vergleicht diesen Hashwert mit dem Hashwert, der für euch in der Twitter-Datenbank gespeicherten wurde.
- Wenn die beiden Werte identisch sind, wird die Anmeldung erfolgreich, ansonsten nicht.
Jetzt fragt ihr euch vielleicht: “Aber Moment mal! Und das soll alles mit einer Hashfunktion möglich sein? Aber unsere Bibliothekar-Hashfunktion war doch viel zu simpel, wie soll das denn gehen?”. Diese Frage ist absolut berechtigt!
Damit eine Hashfunktion auch in einem so wichtigen Umfeld wie Sicherheit im Internet Stand halten kann, müssen wir sie weiter verbessern und abhärten. Wir müssen weitere Anforderungen an die Hashfunktion stellen:
Anforderung #2: Vom Hashwert sollen keine Rückschlüsse auf den Eingabewert gemacht werden können. Weder auf die Struktur, noch die Länge, noch sonst auf sonst irgendeine Beschaffenheit des Eingabewertes.
Dieser Anforderung kann die Bibliothekar-Hashfunktion nicht genügen, denn der Hashwert (Buchstabe) lässt einen kleinen, aber nicht unwichtigen Rückschluss auf den Eingabewert (Name des Autors) zu. Oder einfacher: Wenn wir das “G” als Hashwert haben, wissen wir, dass der Name des gesuchten Autors mit “G” startet. Aus einem gegebenen Hashwert wissen wir nämlich den Anfangsbuchstaben des Nachnamens des Autors. Das ist natürlich im Umfeld der Bibliothek nicht weiter schlimm, aber es wäre inakzeptabel, wenn aus dem Hashwert eures Twitter-Passworts ein Rückschluss auf das erste Zeichen des Passworts gemacht werden könnte.
Anforderung #3: Es soll kein praktisches Verfahren möglich sein, das aus einem Hashwert den Eingabewert bestimmt.
Das ist die vielleicht wichtigste Eigenschaft einer kryptographisch guten Hashfunktion: Wie man es auch dreht und wendet, es darf keine effiziente Möglichkeit geben, aus einem Hashwert den Eingabewert zu berechnen. Hier schlägt sich die Bibliothekar-Hashfunktion tapfer, denn z.B. aus dem Hashwert “G” wissen wir beim besten Willen nicht, welcher Autor GENAU gemeint ist.
Die Frage hier aber lautet: was ist denn gemeint mit “keine effiziente Möglichkeit”? Eine einfache Antwort liefert die folgende Umformulierung der Anforderung #3:
Anforderung #4 (Umformulierung von Anforderung #3): Um aus einem Hashwert den Eingabewert zu bestimmen, darf es nichts effizienteres oder intelligenteres geben, also das brachiale Durchprobieren sämtlicher möglicher Eingabewerte, bis der richtige Hashwert gefunden ist. Dies wird auch als die Brute-Force Methode bezeichnet.
Kurz gesagt: Du musst einfach alle möglichen Eingabewerte prüfen und diese durch die Hashfunktion jagen. Und das machst du solange, bis du den gesuchten Eingabewert gefunden hast. Diese Anforderung beisst sich “leider” ein wenig mit der Anforderung #1 (“Hashfunktion soll effizient berechenbar sein”), und dagegen gibt es nur ein einziges Mittel: Die schiere Grösse, die Ewigkeit und unglaublich viele Möglichkeiten machen es aus!
Wenn die Hashfunktion effizient berechenbar sein muss, dann muss zum einen Anforderung #2 (Kollisionsfreiheit) gegeben sein, und zusätzlich muss es unglaublich viele mögliche Hashwerte geben. Nur so können wir sicherstellen, dass das brachiale Ausprobieren eine Ewigkeit dauern wird. Ich glaube jetzt ist es an der Zeit, mit ein paar Beispielen anzufangen.
Ein echter Star unter den Hashfunktionen: Der SHA-256
Die berühmte Hashfunktion, die z.B. im Bitcoin Blockchain, aber auch beim Hashen eures Passwortes bei Twitter benutzt wird, nennt sich SHA-256. Der SHA-256 produziert, wie es der Name schon sagt, Hashwerte der Länge 256 Bits, was einer 64-stelligen beliebigen Zeichenkombination entspricht.
Beispiel 1: Der SHA-256 Wert der rauskommt, wenn man
"hallo"eingibt, sieht folgendermassen aus:
"d3751d33f9cd5049c4af2b462735457e4d3baf130bcbb87f389e349fbaeb20b9"Beispiel 2: Der SHA-256 Wert der rauskommt, wenn man
"Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet."eingibt, sieht folgendermassen aus:
"ff4ef4245da5b09786e3d3de8b430292fa081984db272d2b13ed404b45353d28"Faszinierend, nicht wahr? Egal was reinkommt, raus kommt irgend ein komischer Text der Länge 64.
Nochmals zurück zur Attacke durch brachiales Ausprobieren
Lasst uns also nochmals auf die “Brute Force” Attacke zurückkommen. Lasst uns mal annehmen, Twitter wurde gehackt und die Hacker haben nun eure Email Adresse und sie haben auch den Hashwert eures Passwortes:
f61e1a4649806e696bb39372897a7c06a1b048294416be224d7365d56380bf7bNatürlich wollen sie nun um jeden Preis versuchen, euer richtiges Passwort herauszufinden. Vielleicht wart ihr nachlässig und habt das gleiche Passwort auf einer anderen Seite verwendet? Auf jeden Fall einen Versuch wert! Die Hacker wissen ebenfalls, dass beim Berechnen des Hashes der SHA-256 Algorithmus verwendet wurde. Da der SHA-256 alle oben aufgelisteten Anforderungen erfüllt, bleibt den Hackern nichts anderes übrig, als zu raten. Ich möchte kein Spielverderber sein, aber glaub mir, ihr kommt nie drauf. Deswegen die Lösung vorweg: der Eingabewert (in diesem Falle das Twitter Passwort) für obigen Hashwert lautet:
Keine Chance!Und um es nochmals zu betonen, hier ist Name auch Programm: Keine Chance. Um darauf zu stossen hätten die Hacker bis zu “2 hoch 256” Versuche benötigt. Sagen wir mal, sie wären schnell und würden es schaffen, pro Sekunde 10 Eingabewerte (mögliche Passwörter) zu berechnen und zu prüfen. Somit wären sie im dümmsten Fall 3.6717431e+68 Jahre am testen. Nur zur Vorstellung, das sind ungefähr:
367'171'743'100'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000Jahre. Das wäre zu viel Zeit und das wäre auch zu viel Arbeit. Hab ich Arbeit gesagt? Also Arbeit wie in “Work”? Hat das was mit “Proof of Work” zu tun? Ganz genau, das hat mit Work und mit “Proof of Work” zu tun, und genau darum dreht sich ein Kernelement in Satoshi’s Bitcoin Paper. Auf diesen Zusammenhang werden wir in einem nächsten Artikel näher eingehen.
