Was ist Hashfunktion?

Funktion, die aus Daten beliebiger Länge einen Wert fester Länge (Hashwert) berechnet. In der Kryptografie verwendete Hashfunktionen wie SHA-256 sind so gebaut, dass es praktisch unmöglich ist, aus einem Hashwert die ursprünglichen Daten zu finden oder zwei Daten mit demselben Hashwert zu finden; sie dienen zur Erkennung von Manipulationen, für digitale Signaturen und zur Passwortspeicherung.

Japanische Bezeichnung: ハッシュ関数

„Hashfunktion“ kommt in 7 Übungsfragen aus 2 Themen vor, z. B. Grundlagen der Informationssicherheit, Datenstrukturen und Algorithmen.

Fachgebiet: Grundlagen der Informationssicherheit

Geforderte Eigenschaften kryptografischer Hashfunktionen

In der Kryptografie verwendete Hashfunktionen müssen drei Eigenschaften haben. Urbildresistenz (Einwegeigenschaft) bedeutet, dass es schwierig ist, eine Eingabe zu finden, die einen vorgegebenen Hashwert ergibt. Zweite Urbildresistenz bedeutet, dass es schwierig ist, zu einer gegebenen Eingabe eine andere mit demselben Hashwert zu finden. Kollisionsresistenz bedeutet, dass es schwierig ist, beliebige zwei verschiedene Eingaben mit demselben Hashwert zu finden. Außerdem ändert schon ein einziges geändertes Eingabebit etwa die Hälfte der Ausgabebits (Lawineneffekt).

Ausgabelänge und Sicherheit

Bei einer idealen Hashfunktion mit n-Bit-Ausgabe erfordert die Suche nach einem Urbild per Brute Force etwa 2^n Berechnungen, eine Kollision wird wegen des Geburtstagsparadoxons dagegen schon nach etwa 2^(n/2) wahrscheinlich. SHA-256 gilt daher gegenüber Kollisionen als etwa 128 Bit stark. Für MD5 und SHA-1 wurden Methoden gefunden, Kollisionen mit weit weniger Berechnungen als per Brute Force zu erzeugen; sie dürfen daher nicht verwendet werden, wo Sicherheit gefordert ist, etwa bei digitalen Signaturen.

Wichtige Anwendungen

Ein Hashwert kann als „Fingerabdruck“ von Daten dienen. Vergleicht man den Hashwert einer heruntergeladenen Datei mit dem offiziell veröffentlichten Wert, zeigt sich, ob sie beschädigt oder ausgetauscht wurde (sofern der offizielle Wert selbst über einen vertrauenswürdigen Weg bezogen wurde). Bei digitalen Signaturen wird statt eines langen Dokuments dessen Hashwert signiert. Zur Passwortspeicherung wird ein Salt hinzugefügt, und absichtlich aufwendige Verfahren wie bcrypt oder Argon2 werden verwendet. HMAC, das eine Hashfunktion mit einem Schlüssel kombiniert, dient als Message Authentication Code zur Erkennung von Manipulationen.

Jetzt üben: Fragen zu Hashfunktion

Welche Kombination gibt für eine ideale Hashfunktion mit 256-Bit-Ausgabe die ungefähre Zahl der Berechnungen bei einem Brute-Force-Angriff in zwei Fällen richtig an: eine Eingabe finden, die einen vorgegebenen Hashwert ergibt (Urbildangriff), und beliebige zwei verschiedene Eingaben finden, die denselben Hashwert ergeben (Kollisionsangriff)?

AUrbildangriff etwa 2^256, Kollisionsangriff etwa 2^128
BUrbildangriff etwa 2^128, Kollisionsangriff etwa 2^256
CUrbildangriff und Kollisionsangriff jeweils etwa 2^256

Antwort und Erläuterung anzeigen

Antwort: A. Urbildangriff etwa 2^256, Kollisionsangriff etwa 2^128

Eine ideale Hashfunktion mit n-Bit-Ausgabe hat 2^n mögliche Hashwerte, und jede ausprobierte Eingabe trifft einen vorgegebenen Hashwert mit der Wahrscheinlichkeit 1/2^n. Ein Urbildangriff braucht daher etwa 2^n Berechnungen, bei n = 256 also etwa 2^256. Beim Kollisionsangriff dagegen dürfen zwei beliebige Eingaben übereinstimmen; mit k ausprobierten Eingaben gibt es etwa k^2/2 vergleichbare Paare. Nähert sich k^2/2 dem Wert 2^n, also bei k in der Größenordnung von 2^(n/2), wird eine Kollision wahrscheinlich; bei n = 256 sind das etwa 2^128. Das ist derselbe Gedanke wie beim Geburtstagsparadoxon, nach dem in einer Gruppe von 23 Personen die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, über 50 % liegt; man spricht daher vom Geburtstagsangriff. Folglich wird die Kollisionsresistenz einer Hashfunktion mit der halben Ausgabelänge angesetzt, und für eine Sicherheit von 128 Bit ist eine 256-Bit-Ausgabe erforderlich.

Warum wird empfohlen, zum Speichern von Passwörtern nicht direkt eine schnelle Hashfunktion wie SHA-256 zu verwenden, sondern ein absichtlich rechenaufwendig entworfenes Verfahren wie bcrypt oder Argon2?

AWeil langsame Verfahren längere Ausgaben haben und dadurch keine Kollisionen mehr auftreten
BWeil die aufwendige Berechnung es nur berechtigten Nutzern erlaubt, das ursprüngliche Passwort aus dem Hashwert wiederherzustellen
CWeil bei einem Abfluss der gespeicherten Hashwerte auch jeder Rateversuch des Angreifers teuer wird, was die Dauer von Brute-Force- und Wörterbuchangriffen stark erhöht

Antwort und Erläuterung anzeigen

Antwort: C. Weil bei einem Abfluss der gespeicherten Hashwerte auch jeder Rateversuch des Angreifers teuer wird, was die Dauer von Brute-Force- und Wörterbuchangriffen stark erhöht

Fließen Passwort-Hashwerte ab, können Angreifer auf eigenen Rechnern Passwortkandidaten nacheinander hashen und nach einem Treffer suchen. Universelle Hashfunktionen wie SHA-256 sind dafür gebaut, große Datenmengen schnell zu verarbeiten; mit GPUs u. Ä. lassen sich daher pro Sekunde enorm viele Kandidaten testen. Verfahren für die Passwortspeicherung wie bcrypt und Argon2 haben eine einstellbare Zahl von Wiederholungen (Kostenfaktor) und machen jede einzelne Berechnung absichtlich aufwendig. Wird jede Berechnung zum Beispiel 1 Million Mal langsamer, dauert auch eine Brute-Force-Suche 1 Million Mal länger. Ein berechtigter Nutzer braucht bei der Anmeldung nur eine Berechnung, eine Verzögerung von etwa 0,1 Sekunden ist also kein Problem. Argon2 lässt sich zudem so einstellen, dass es viel Speicher belegt, was massiv parallele Berechnung auf GPUs oder Spezialschaltungen erschwert. Welches Verfahren auch verwendet wird, es wird mit einem Salt pro Nutzer kombiniert.

Häufige Fragen

Was ist der Unterschied zwischen einer Hashfunktion und Verschlüsselung?

Verschlüsselung ist eine Umwandlung mit Schlüssel, die sich umkehren (entschlüsseln) lässt; eine Hashfunktion verwendet dagegen keinen Schlüssel und ist eine nicht umkehrbare Einwegberechnung. Hashwerte dienen daher nicht der Geheimhaltung, sondern der Prüfung, ob Daten gleich sind.

Wie viele Bit hat ein SHA-256-Hashwert?

256 Bit (64 Hexadezimalzeichen), unabhängig von der Eingabelänge. Eine Eingabe aus einem Zeichen und eine große Datei ergeben beide einen Wert derselben Länge.

„Hashfunktion“ in den Erläuterungen

Eine ideale Hashfunktion mit n-Bit-Ausgabe hat 2^n mögliche Hashwerte, und jede ausprobierte Eingabe trifft einen vorgegebenen Hashwert mit der Wahrscheinlichkeit 1/2^n.
Welche Kombination gibt für eine ideale Hashfunktion mit 25…
Eine Hashfunktion berechnet aus Daten beliebiger Länge einen Wert fester Länge (Hashwert, Digest).
Welche Aussage beschreibt eine Eigenschaft der in der Krypt…
Grundregel ist, Passwörter nicht im Klartext zu speichern, sondern die mit einer Hashfunktion berechneten Hashwerte.
Ein Webdienst fügt beim Speichern der Nutzerpasswörter jede…
Ein Message Authentication Code (MAC) ist ein kurzer Wert, der aus einer Nachricht und einem symmetrischen Schlüssel berechnet wird; verbreitet ist HMAC, das eine Hashfunktion verwendet.
Welche Aussage vergleicht einen Message Authentication Code…
Eine Hashtabelle berechnet mit einer Hashfunktion aus dem Schlüssel eine Speicherposition und ermöglicht so Suchen, Einfügen und Löschen im Mittel in O(1).
Welche Aussage beschreibt eine Kollision in einer Hashtabel…