Ein Fingerabdruck ist klein und gehört trotzdem zu genau einem Menschen. Eine Hashfunktion berechnet einen solchen Fingerabdruck für Daten.

Definition

Eine Hashfunktion [math]\displaystyle{ h }[/math] ist eine Rechenvorschrift, die aus einer Nachricht [math]\displaystyle{ m }[/math] beliebiger Länge einen Hashwert [math]\displaystyle{ h(m) }[/math] fester Länge berechnet. Die Vorschrift ist öffentlich und braucht keinen Schlüssel: Jeder kann den Hashwert einer Nachricht berechnen.

Es gibt mehr mögliche Nachrichten als Hashwerte. Deshalb haben zwangsläufig verschiedene Nachrichten denselben Hashwert. Ein solches Paar heißt Kollision.

Anforderungen

Eine Hashfunktion für die Kryptologie muss diese Anforderungen erfüllen:

  • Feste Länge: Jeder Hashwert braucht gleich viel Platz, zum Beispiel 256 Bit, gleich wie lang die Nachricht ist.
  • Effizienz: Der Hashwert lässt sich schnell berechnen, auch für große Dateien.
  • Einwegeigenschaft: Zu einem gegebenen Hashwert lässt sich praktisch keine Nachricht finden, die diesen Hashwert hat.
  • Kollisionsresistenz: Es ist praktisch unmöglich, zu einer gegebenen Nachricht eine zweite mit demselben Hashwert zu finden oder überhaupt zwei verschiedene Nachrichten mit demselben Hashwert.
  • Empfindlichkeit: Schon die kleinste Änderung der Nachricht führt zu einem völlig anderen Hashwert.

„Praktisch unmöglich“ heißt: Kollisionen gibt es zwar, aber niemand kann sie mit vertretbarem Aufwand finden.

Das Bundesamt für Sicherheit in der Informationstechnik (BSI) nennt unter anderem SHA-256 als geeignete Hashfunktion, ihr Hashwert hat 256 Bit (Technische Richtlinie TR-02102-1, Version 2026-01). Die älteren Hashfunktionen MD5 und SHA-1 gelten als gebrochen: Für MD5 wurden 2004 Kollisionen veröffentlicht, für SHA-1 im Jahr 2017.

Einsatz

  • Digitale Signatur: Signiert wird nicht die Nachricht, sondern ihr kurzer Hashwert.
  • Prüfung der Integrität: Wer den Hashwert einer Datei auf einem sicheren Weg erhalten hat, erkennt jede Veränderung der Datei, indem er den Hashwert neu berechnet und vergleicht.
  • Speichern von Passwörtern: siehe nächster Abschnitt.

Passwörter

Ein Server speichert zu jedem Benutzernamen nicht das Passwort, sondern nur dessen Hashwert. Bei der Anmeldung berechnet er den Hashwert der Eingabe und vergleicht ihn mit dem gespeicherten Wert.

Vorteile:

  • Wird die Tabelle gestohlen, stehen darin keine Passwörter im Klartext. Wegen der Einwegeigenschaft lassen sie sich aus den Hashwerten nicht zurückrechnen.
  • Auch Administratoren können die Passwörter nicht lesen.
  • Alle Hashwerte sind gleich lang und verraten deshalb nicht, wie lang ein Passwort ist.

Der Angriff darauf ist der Wörterbuchangriff: Der Angreifer kennt die Hashfunktion. Er berechnet die Hashwerte vieler wahrscheinlicher Passwörter und vergleicht sie mit den gestohlenen Werten. Jeder Treffer verrät ein Passwort.

Gegenmaßnahmen:

  • Lange, zufällige Passwörter, die in keiner Wörterliste stehen.
  • Salt: Der Server erzeugt für jeden Benutzer einen zufälligen Wert, das Salt, setzt es vor das Passwort und berechnet erst dann den Hashwert. Das Salt wird neben dem Hashwert gespeichert. Gleiche Passwörter ergeben so verschiedene Hashwerte, und eine vorab berechnete Liste von Hashwerten ist wertlos. Der IT-Grundschutz des BSI verlangt für Webanwendungen solche gesalzenen Hashwerte (Baustein CON.10, Edition 2023).
  • Langsame Verfahren: Für Passwörter gibt es eigene Hashverfahren, die absichtlich viel Rechenzeit brauchen. Eine einzelne Anmeldung stört das nicht, das Durchprobieren von Millionen Wörtern schon.

Beispiele

Hashwert einer einfachen Hashfunktion berechnen

Eine einfache Hashfunktion für Wörter aus Großbuchstaben: Ein Zwischenwert beginnt mit [math]\displaystyle{ z = 0 }[/math]. Für jeden Buchstaben des Wortes, von links nach rechts, wird der bisherige Zwischenwert mit 3 multipliziert, der Buchstabenwert (A = 0 bis Z = 25) addiert und der Rest bei der Division durch 101 gebildet: [math]\displaystyle{ z_{\text{neu}} = (3 \cdot z + \text{Buchstabenwert}) \bmod 101 }[/math]. Der letzte Zwischenwert ist der Hashwert. Er liegt immer zwischen 0 und 100 und passt damit immer in drei Ziffern: Das ist seine feste Länge. Gesucht ist der Hashwert von WIKI.

Buchstabe Wert neuer Zwischenwert
W 22 [math]\displaystyle{ (3 \cdot 0 + 22) \bmod 101 = 22 \bmod 101 = 22 }[/math]
I 8 [math]\displaystyle{ (3 \cdot 22 + 8) \bmod 101 = 74 \bmod 101 = 74 }[/math]
K 10 [math]\displaystyle{ (3 \cdot 74 + 10) \bmod 101 = 232 \bmod 101 = 30 }[/math]
I 8 [math]\displaystyle{ (3 \cdot 30 + 8) \bmod 101 = 98 \bmod 101 = 98 }[/math]

Der Hashwert von WIKI ist 98.

KIWI besteht aus denselben Buchstaben wie WIKI, hat aber den Hashwert 12 statt 98. Bei dieser Hashfunktion zählt also auch die Reihenfolge der Buchstaben.

Kollision finden

Es gibt nur 101 mögliche Hashwerte (0 bis 100), aber beliebig viele Texte. Deshalb müssen verschiedene Texte denselben Hashwert haben. Eine solche Kollision ist schnell gefunden: MAUS und BAUM haben beide den Hashwert 99. Für eine digitale Signatur wäre diese Hashfunktion unbrauchbar.

Passwörter mit einem Wörterbuch angreifen

Ein Server speichert zu jedem Benutzernamen nur den Hashwert des Passworts, berechnet mit der Hashfunktion aus dem ersten Beispiel:

Benutzername gespeicherter Hashwert
kasse 7
lager 37
buero 99

Bei der Anmeldung berechnet der Server den Hashwert des eingegebenen Passworts und vergleicht ihn mit dem gespeicherten Wert.

Ein Angreifer stiehlt die Tabelle. Er berechnet die Hashwerte häufiger Wörter:

Wort HAUS HUND KATZE MAUS ROSE SONNE
Hashwert 65 7 50 99 37 77

Der Vergleich verrät die Passwörter: kasse hat HUND, lager hat ROSE, buero hat MAUS. Ein langes, zufälliges Passwort stünde in keinem Wörterbuch.

Wegen der Kollision aus dem zweiten Beispiel könnte sich der Angreifer als buero sogar mit BAUM anmelden, denn MAUS und BAUM haben denselben Hashwert.