Hashfunktionen

Gegenstände in allen Größen fallen in einen Trichter und kommen unten als identische, gleich große Kacheln wieder heraus.

Woher weiß eine Website, dass dein Passwort stimmt, ohne dein Passwort zu kennen? Woran merkt dein Handy, dass eine heruntergeladene Datei unterwegs beschädigt wurde? Beide Male mit demselben Trick: mit einem Fingerabdruck der Daten. Klein, immer gleich groß und einmalig für das, was hineinging.

Wörter, die du gleich brauchst

Hash (oder Hashfunktion): Ein Rechner, dem du etwas gibst — ein Wort, ein Foto, ein ganzes Buch — und der daraus immer eine gleich lange Folge von Zeichen macht. Dieselbe Eingabe gibt immer dieselbe Ausgabe. Etwas anderes eingeben, und sei es nur ein Buchstabe, gibt eine völlig andere Ausgabe.
Bit: Das kleinste Stück Information: eine 0 oder eine 1. Acht Bits ergeben ein Byte. Wenn etwas „256 Bit“ ist, sind das 256 Nullen und Einsen hintereinander.
SHA-256: Der Name der Hashfunktion, die heute am meisten benutzt wird. Die 256 ist die Anzahl der Bits in der Ausgabe: immer genau 256, egal ob du einen Buchstaben oder einen ganzen Film eingibst. In Hexadezimal sind das 64 Zeichen.
Algorithmus: Ein festes Rezept aus Rechenschritten. SHA-256, SHA-1 und MD5 sind drei verschiedene Rezepte mit demselben Ziel.
Hexadezimal: Kennst du aus Kapitel 1: Bytes mit den Ziffern 0–9 und den Buchstaben a–f aufschreiben, zwei Zeichen pro Byte. Jedes Hexzeichen steht also für vier Bits. So wird ein Hash unten angezeigt — und für nichts anderes benutzt.

Drei Regeln, an die sich ein Hash hält

Regel	Was das bedeutet
Einbahnstraße	Aus dem Hash kannst du die Eingabe nicht zurückrechnen. Nicht „schwierig“, nicht „mit einem schnellen Computer schon“ — es gibt keinen Weg zurück. So wie du aus dem Hackfleisch die Kuh nicht zurückbekommst.
Keine Kollisionen	Zwei verschiedene Eingaben dürfen nicht denselben Hash bekommen. Theoretisch geht das (es gibt unendlich viele Texte und nur 2²⁵⁶ Hashes), aber finden kann sie niemand.
Lawineneffekt	Ein Buchstabe anders, und ungefähr die Hälfte aller Bits in der Ausgabe kippt um. Es bleibt nichts übrig, was dem vorherigen Hash ähnelt.

Probier es selbst

Alles passiert in deinem Browser. Es wird nichts an den Server geschickt.

Klick auf Fingerabdruck erzeugen. Du siehst vier Hashes desselben Satzes, mit vier verschiedenen Rezepten. Achte darauf, wie lang jeder ist.
Ändere einen Buchstaben im Satz und klick noch einmal. Vergleich. Erkennst du noch etwas?
Klick auf Lawineneffekt zeigen: Die Demo ändert selbst ein Zeichen und zählt, wie viele Bits umkippen.
Füg einen richtig langen Text ein — einen Songtext, einen Aufsatz. Der Hash bleibt gleich lang.

Text

Was du da genau vor dir hast

Diese Zeichenreihen sind kein Base64. Sie bestehen nur aus 0–9 und a–f, und das ist Hexadezimal: zwei Zeichen pro Byte, vier Bits pro Zeichen. 64 Zeichen × 4 = 256 Bit, genau das, was hinter SHA-256 steht. Bei SHA-1 zählst du 40 Zeichen, also 160 Bit.

Warum hier Hexadezimal und in Kapitel 1 Base64? Weil es hier ums Schauen geht. Hexadezimal ist länger, aber du kannst es noch verfolgen: Jedes Zeichen ist genau vier Bits, und du kannst zwei Hashes nebeneinanderlegen und Zeichen für Zeichen vergleichen. Base64 ist kürzer und damit praktischer zum Verschicken, aber die Grenze zwischen zwei Bytes fällt dort mitten in ein Zeichen. Dieselben Bytes, eine andere Art, sie aufzuschreiben — genau der Punkt aus dem vorigen Kapitel.

Warum diese Länge wichtig ist

256 Bit bedeutet 2²⁵⁶ mögliche Ergebnisse. Das ist eine Zahl mit 78 Stellen. Zum Vergleich: Die Anzahl der Atome im Universum ist eine Zahl mit ungefähr 80 Stellen. Jeder mögliche Text bekommt einen Platz in einem Raum so groß wie das Universum — die Chance, dass zwei verschiedene Texte zufällig auf demselben Platz landen, ist praktisch null.

Die Lektion, die man nicht sehen kann

Schau dir in der Demo die Zeile mit SHA-1 an. Sie sieht genauso zufällig aus wie SHA-256, nur kürzer: 160 Bit statt 256, also 40 Hexzeichen statt 64. Trotzdem ist SHA-1 gebrochen: 2017 zeigten Forscher von Google und vom CWI in Amsterdam zwei verschiedene PDF-Dateien mit genau demselben SHA-1-Hash. Die Regel „keine Kollisionen“ war durchbrochen. MD5 war schon viel früher weg.

An der Ausgabe merkst du davon nichts. Ob eine Hashfunktion taugt, hängt nicht davon ab, wie zufällig sie aussieht, sondern davon, ob Mathematiker eine Schwachstelle darin gefunden haben. Deshalb benutzt du heute SHA-256 und nicht irgendetwas, das „auch gut aussieht“.

Kann man einen Hash „entschlüsseln“? Nein. Es ist nichts verschlüsselt, es gibt nichts zu entschlüsseln. Trotzdem gibt es Websites, die behaupten, sie könnten es — und manchmal gelingt es ihnen wirklich. Wie das geht und warum das für deine Passwörter wichtig ist, ist das nächste Kapitel.

Das ist Mathematik: das Geburtstagsparadoxon

Wirf einen Würfel. Wie oft musst du werfen, bis du eine Sechs hast? Im Schnitt sechsmal. Aber wie oft musst du werfen, bis du irgendeine Zahl ein zweites Mal siehst? Nach vier Würfen liegt diese Chance schon bei 72 %. Das geht viel schneller — und es ist dasselbe Phänomen wie in einer Klasse: Bei 23 Schülern ist die Chance, dass zwei am selben Tag Geburtstag haben, größer als 50 %. Und das bei 365 Tagen.

Der Trick steckt darin, wonach du suchst. Du suchst nicht jemanden, der an deinem Geburtstag Geburtstag hat — dafür brauchst du gut 250 Leute. Du suchst irgendwelche zwei. Mit 23 Schülern kannst du 253 verschiedene Paare bilden, und jedes Paar ist eine Chance auf eine Dopplung. Deshalb kommt „doppelt“ so viel schneller, als dein Bauchgefühl sagt.

Möglichkeiten	Eine Dopplung ist wahrscheinlich nach
6 (ein Würfel)	4 Würfen
365 (Geburtstage)	23 Schülern
1 000 000	ungefähr 1 200 Versuchen
2²⁵⁶ (SHA-256)	ungefähr 2¹²⁸ Versuchen

Es ist jedes Mal ungefähr die Quadratwurzel aus der Anzahl der Möglichkeiten. Bei einer Million Möglichkeiten hast du schon nach gut tausend Versuchen eine Dopplung — nicht erst nach einer halben Million.

Ein Hash ist der „Geburtstag“ eines Textes: Jeder Text bekommt einen, aus 2²⁵⁶ möglichen. Eine Kollision — zwei Texte mit demselben Hash — ist also nichts anderes als zwei Schüler, die zusammen Geburtstag haben. Und die Tabelle sagt, wie viele Texte du ausprobieren musst, bis das wahrscheinlich passiert: keine 2²⁵⁶, sondern 2¹²⁸. Ein Hash ist nur halb so stark, wie seine Länge vermuten lässt.

Das ist der Grund, warum 256 der Standard ist und nicht 128. Ein Hash aus 128 Bit gibt eine Kollision nach 2⁶⁴ Versuchen — und so viele Hashes rechnen alle Computer, die heute Bitcoin laufen lassen, zusammen in weniger als einer Sekunde aus. Bei 256 Bit bleiben 128 übrig, und das schafft niemand. Das ist Wahrscheinlichkeitsrechnung: eine einzige Rechnung über Würfel bestimmt, wie lang jeder Hash der Welt sein muss.