Hashfunktionen erklärt

Wenn du Software herunterlädst und eine Prüfsumme vergleichst, dich mit einem Passwort anmeldest, ein Dokument signierst oder einen Block zu Bitcoin hinzufügst, ist eine Hashfunktion am Werk. Sie macht aus einer beliebigen Datenmenge einen kurzen Fingerabdruck fester Größe, den Hashwert, und zwar so, dass sich das weder rückgängig machen noch fälschen lässt. Die Idee ist einfach, doch die Anforderungen an einen guten Hash sind streng, und zwei der meistgenutzten, MD5 und SHA-1, haben ihnen nicht standgehalten.

Zwei Nachrichten, die sich in einem Buchstaben unterscheiden, gehen in eine Hashfunktion und kommen als zwei völlig verschiedene SHA-256-Hashwerte heraus, die gekippten Bits sind in einem Raster markiert
Zwei Nachrichten, die sich in einem Buchstaben unterscheiden, gehen in eine Hashfunktion und kommen als zwei völlig verschiedene SHA-256-Hashwerte heraus, die gekippten Bits sind in einem Raster markiert

Ein Fingerabdruck für Daten

Eine Hashfunktion nimmt eine Eingabe beliebiger Länge und gibt einen Hashwert fester Länge zurück: 256 Bits bei SHA-256, geschrieben als 64 Hexadezimalziffern. Dieselbe Eingabe ergibt immer denselben Hashwert, daher kann der Hashwert für die Daten stehen. Haben zwei Dateien denselben SHA-256-Hashwert, kannst du sicher sein, dass sie identisch sind, und wurde ein Bit eines Downloads beschädigt, stimmt sein Hashwert nicht mehr mit dem vom Herausgeber angegebenen überein. Weil es weit mehr mögliche Eingaben als Hashwerte gibt, müssen sich viele Eingaben jeden Hashwert teilen; ein guter Hash macht es einfach unmöglich, eine davon zu finden.

Drei Versprechen

Ein kryptografischer Hash gibt drei Versprechen. Urbildresistenz: Zu einem Hashwert findet man keine Eingabe, die ihn erzeugt. Zweite Urbildresistenz: Zu einer Eingabe findet man keine andere Eingabe mit demselben Hashwert. Kollisionsresistenz: Man findet überhaupt keine zwei Eingaben mit demselben Hashwert. Bei einem idealen Hash mit n Bits ist Raten der beste Angriff: etwa 2ⁿ Versuche für ein Urbild und etwa 2ⁿᐟ² für eine Kollision. Ein Hash gilt als gebrochen, wenn jemand einen Weg findet, der deutlich schneller ist.

Der Lawineneffekt

Ändert man ein Bit der Eingabe, sollte jedes Bit des Hashwerts mit einer Wahrscheinlichkeit von einhalb kippen, unabhängig von den anderen. Dann ergibt eine kleine Änderung der Nachricht einen Hashwert, der mit dem ursprünglichen scheinbar nichts zu tun hat, und der Hashwert verrät nichts darüber, welcher Teil der Eingabe sich geändert hat. SHA-256 erreicht das mit 64 Runden, die seine acht 32-Bit-Wörter rotieren, addieren und kombinieren, sodass nach wenigen Runden jedes Eingabebit jedes Wort beeinflusst hat. Eine einfache Summe der Bytes dagegen ändert sich um genau den Betrag, um den sich die Eingabe geändert hat, und verrät damit alles.

Ein Blick in SHA-256

SHA-256 füllt die Nachricht zuerst auf: Es hängt ein 1-Bit, Nullen und die Länge der Nachricht an, bis die Gesamtlänge ein Vielfaches von 512 Bits ist. Dann verarbeitet es die Nachricht in Stücken von 512 Bits. Jeder Block wird auf 64 Wörter gestreckt, die in einen Zustand aus acht 32-Bit-Wörtern eingemischt werden; dieser beginnt mit festen Werten, die aus den Quadratwurzeln der ersten acht Primzahlen stammen. Der Zustand nach dem letzten Block ist der Hashwert. Diese verkettete Bauweise, benannt nach Ralph Merkle und Ivan Damgård, teilen MD5, SHA-1 und SHA-512; das neuere SHA-3, 2015 standardisiert, nutzt eine andere Konstruktion, den sogenannten Schwamm (Sponge).

Ralph Merkle beim Singularity Summit 2007. Die verkettete Bauweise, die SHA-256 verwendet, ist nach ihm und Ivan Damgård benannt.
Ralph Merkle beim Singularity Summit 2007. Die verkettete Bauweise, die SHA-256 verwendet, ist nach ihm und Ivan Damgård benannt.

Der Geburtstagsangriff

In einer Gruppe von 23 Personen liegt die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, knapp über einhalb, obwohl das Jahr 365 Tage hat, denn entscheidend ist die Zahl der Paare, und die wächst mit dem Quadrat der Gruppengröße. Kollisionen in einem Hash folgen derselben Regel. Bei 2ᵏ möglichen Hashwerten ist nach etwa √(π/2 · 2ᵏ) zufälligen Eingaben eine Kollision zu erwarten. Bei 32 Bits sind das etwa 82.000 Eingaben, in Augenblicken erledigt; bei 128 Bits etwa 2⁶⁴, was für große Rechenprojekte erreichbar ist. Deshalb waren die 128 Bits von MD5 nie großzügig, und deshalb verdoppelt SHA-256 die Länge, um eine Sicherheit von 128 Bit zu bieten.

MD5 und SHA-1: gebrochen

Ron Rivest entwarf MD5 im Jahr 1991, und die NSA entwarf SHA-1, das 1995 veröffentlicht wurde. 2004 zeigten Xiaoyun Wang und ihre Kollegen, wie man schnell MD5-Kollisionen erzeugt, und 2008 nutzten Forscher sie, um ein Zertifikat zu fälschen, dem Webbrowser vertrauten. Die Spionagesoftware Flame von 2012 nutzte eine MD5-Kollision, um sich als Update von Microsoft auszugeben. SHA-1 fiel 2017, als Google und CWI Amsterdam zwei verschiedene PDF-Dateien mit demselben SHA-1-Hashwert veröffentlichten, nach etwa 2⁶³ Berechnungen. Beide taugen weiterhin, um zufällige Fehler zu erkennen, aber nicht für irgendetwas, das ein Angreifer ins Visier nehmen könnte.

Wo Hashes eingesetzt werden

Digitale Signaturen signieren den Hash eines Dokuments statt des Dokuments selbst. Git benennt jede Datei und jeden Commit nach ihrem Hash, und Bitcoin-Miner suchen nach Blockheadern, deren doppelter SHA-256-Hash mit einer langen Folge von Nullen beginnt. Websites sollten Passwörter nie speichern, sondern nur einen Hash davon; weil Menschen aber kurze Passwörter wählen, muss dieser Hash langsam und gesalzen sein, mit Verfahren wie bcrypt, scrypt oder Argon2, damit Raten teuer wird. Prüfsummen wie CRC-32, die in ZIP-Dateien, PNG-Bildern und Ethernet verwendet werden, sind ebenfalls Hashes, gebaut, um Rauschen statt Angreifer abzufangen.

Selbst ausprobieren

Öffne „Hashfunktionen ausprobieren“, um eigenen Text mit SHA-256, SHA-512, SHA-1, MD5, CRC-32 und einer einfachen Bytesumme zu hashen. Ändere ein Zeichen und zähle die gekippten Bits, führe den Lawinentest über tausend Ein-Bit-Änderungen aus, um die Glockenkurve um die Hälfte des Hashwerts zu sehen, und finde echte Kollisionen in den ersten 8 bis 32 Bits eines Hashwerts, um den Geburtstagsangriff bei der Arbeit zu beobachten.

Häufig gestellte Fragen

Ist Hashen dasselbe wie Verschlüsseln?

Nein. Verschlüsselung soll von dem rückgängig gemacht werden, der den Schlüssel besitzt; Hashen hat keinen Schlüssel und kann von niemandem rückgängig gemacht werden. Verschlüsselung hält eine Nachricht geheim, während ein Hash nur einen Fingerabdruck liefert, mit dem man eine Nachricht prüfen kann, die man bereits hat.

Wie lange würde es dauern, eine SHA-256-Kollision zu finden?

Mit dem Geburtstagsangriff etwa 2¹²⁸ Hashberechnungen, eine Zahl mit 39 Stellen. Selbst wenn jeder Computer der Erde nichts anderes täte, würde es unvorstellbar viel länger dauern als das Alter des Universums. Eine Abkürzung ist nicht bekannt.

Warum unterscheiden sich zwei Hashes desselben Textes nie?

Eine Hashfunktion ist deterministisch: Sie hat keinen Zufall und keinen Schlüssel, daher ergeben dieselben Bytes immer denselben Hashwert. Kleine Unterschiede, die man nicht sieht, etwa ein Leerzeichen am Ende, ein anderes Zeilenende oder eine andere Unicode-Form eines Buchstabens mit Akzent, ergeben sehr wohl einen anderen Hashwert.

Was ist ein Salt?

Ein Zufallswert, der neben einem Passwort-Hash gespeichert und in ihn eingemischt wird. Zwei Nutzer mit demselben Passwort erhalten dann verschiedene Hashes, und ein Angreifer kann nicht eine einzige vorberechnete Tabelle häufiger Passwörter für alle Konten verwenden.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Hashfunktionen ausprobieren