Mit Google fortfahren
Hashfunktion einfach erklärt: Hashwerte verstehen
Eine Hashfunktion berechnet aus Eingabedaten einen kompakten Hashwert. Gleiche Eingaben liefern bei derselben Funktion denselben Wert. Verschiedene Eingaben können jedoch denselben Hashwert besitzen – das nennt man eine Kollision.
Auf dieser Seite lernst du, Hashwerte zu berechnen, Kollisionen zu erklären und Hashing von Verschlüsselung zu unterscheiden.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Von Daten zum Hashwert
Eine Hashfunktion verarbeitet einen Schlüssel, einen Text, eine Datei oder andere Daten und ordnet ihnen einen Wert aus einem festgelegten Hashraum zu.
Hashfunktion
Eine Hashfunktion ist eine Abbildung $h:K\rightarrow S$. Dabei bezeichnet $K$ die möglichen Eingaben und $S$ die möglichen Hashwerte.
Der Hashwert ist das Ergebnis der Funktion. Bei vielen Verfahren dürfen die Eingaben unterschiedlich lang sein, während die Ausgabe eine feste Länge besitzt.
Wichtig ist der Determinismus: Solange Funktion und Eingabe gleich bleiben, entsteht derselbe Hashwert. Eine zufällige neue Ausgabe bei jedem Aufruf wäre für Vergleiche oder Tabellenzugriffe unbrauchbar.
Bei kryptographischen Hashfunktionen soll außerdem eine kleine Änderung der Eingabe den Hashwert stark verändern. Diese starke Streuung heißt Avalanche-Effekt.
Eine einfache Hashfunktion für ganze Zahlen verwendet den Rest bei der Division durch 10:
$$h(k)=k\bmod 10$$
Für $k=34$ bleibt bei der Division durch 10 der Rest 4. Daher gilt:
$$h(34)=4$$
Für $k=78$ ist der Rest 8, also $h(78)=8$. Die Funktion verteilt Zahlen damit auf die zehn Hashwerte 0 bis 9. Sie ist schnell, aber nicht kryptographisch sicher.
Warum Kollisionen entstehen
Eine Kollision liegt vor, wenn zwei verschiedene Eingaben denselben Hashwert erhalten:
$$k\neq k'\quad\text{und}\quad h(k)=h(k')$$
Wenn es mehr mögliche Eingaben als Hashwerte gibt, müssen mehrere Eingaben auf einzelne Hashwerte fallen. Kollisionen lassen sich dann nicht grundsätzlich verhindern.
Bei $h(k)=k\bmod 10$ gilt:
- $h(25)=5$
- $h(35)=5$
Obwohl 25 und 35 verschieden sind, besitzen sie denselben Hashwert. Das ist eine Kollision.
Für eine bekannte, begrenzte Menge von Schlüsseln kann eine perfekte Hashfunktion so konstruiert werden, dass innerhalb genau dieser Menge keine Kollision auftritt. Daraus folgt nicht, dass sie für alle denkbaren Eingaben kollisionsfrei ist.
Ein Hashwert ist ein kompakter Fingerabdruck, aber keine garantiert eindeutige Kopie der Eingabe.
Gute Eigenschaften hängen vom Zweck ab
Es gibt nicht die eine beste Hashfunktion für alle Aufgaben. Die Anforderungen richten sich nach der Anwendung.
Hashtabellen
Eine Hashtabelle verwendet Hashwerte als Indizes oder Speicherpositionen. Dafür soll die Funktion schnell rechnen und die erwarteten Schlüssel möglichst gleichmäßig verteilen. Viele Kollisionen würden einzelne Tabellenbereiche überfüllen und den Zugriff erschweren.
Ein einfaches Ablagesystem nach dem ersten Buchstaben zeigt das Problem: Ein Ordner für S kann sehr voll werden, während ein Ordner für Q leer bleibt. Die Berechnung ist leicht, die Verteilung aber möglicherweise schlecht.
Kryptographische Anwendungen
Eine kryptographische Hashfunktion soll zusätzliche Angriffshürden bieten:
- Aus einem gegebenen Hashwert soll praktisch keine passende Eingabe berechnet werden können.
- Es soll praktisch nicht möglich sein, gezielt zwei verschiedene Eingaben mit demselben Hashwert zu finden.
- Kleine Eingabeänderungen sollen den Hashwert stark verändern.
„Praktisch nicht möglich“ bedeutet nicht mathematisch ausgeschlossen. Gemeint ist, dass kein ausreichend effizientes Verfahren bekannt sein soll.
Ähnlichkeitssuche
Bei einer Ähnlichkeitssuche kann gerade das Gegenteil nützlich sein: Ähnliche Inhalte sollen ähnliche oder gleiche Werte erhalten. Eine solche Funktion verfolgt ein anderes Ziel als eine kryptographische Hashfunktion.
Hashing ist keine Verschlüsselung
Hashing und Verschlüsselung lösen unterschiedliche Aufgaben.
| Verfahren | Ziel | Rückweg zur Eingabe |
|---|---|---|
| Hashing | kompakten Prüf-, Vergleichs- oder Indexwert erzeugen | bei kryptographischen Funktionen praktisch nicht vorgesehen |
| Verschlüsselung | Daten vor unbefugtem Lesen schützen | mit dem passenden Schlüssel vorgesehen |
Eine Verschlüsselung muss für berechtigte Empfänger umkehrbar sein. Eine kryptographische Hashfunktion wird dagegen gerade so gewählt, dass sich die ursprüngliche Eingabe nicht effizient aus dem Hashwert bestimmen lässt.
Hashing allein macht einen lesbaren Text nicht vertraulich. Wer den Text kennt, kann seinen Hash selbst berechnen und vergleichen.
Bei einer Passwortprüfung muss der Server das Passwort nicht aus einem Hashwert zurückgewinnen:
- Beim Einrichten wird aus dem Passwort und einem individuellen zufälligen Zusatz, dem Salt, ein Passwort-Hash berechnet.
- Gespeichert werden der Salt und das Ergebnis, nicht das Klartextpasswort.
- Bei der Anmeldung wird die Eingabe mit demselben Salt erneut verarbeitet.
- Das neue Ergebnis wird mit dem gespeicherten Wert verglichen.
Dafür werden spezielle Passwort-Hashverfahren eingesetzt. Eine beliebige schnelle Hashfunktion genügt nicht, weil Angreifer sonst sehr viele Passwortversuche in kurzer Zeit prüfen könnten.
Hashwerte richtig einsetzen
Integrität prüfen
Für eine Integritätsprüfung wird zunächst ein Referenz-Hash der Originaldaten berechnet. Später wird der Hash der erhaltenen oder gespeicherten Daten neu berechnet.
- Sind beide Werte verschieden, wurden die Daten oder der Referenzwert verändert.
- Sind beide Werte gleich, spricht das bei einer geeigneten Funktion stark für unveränderte Daten. Wegen möglicher Kollisionen ist dies kein mathematischer Beweis.
- Gegen gezielte Manipulation muss der Referenzwert vertrauenswürdig geschützt sein, etwa durch eine digitale Signatur.
Blöcke verknüpfen
In einer Blockchain kann ein Block den Hash des vorherigen Blocks enthalten. Ändert sich ein früherer Block, ändert sich sein Hash. Die gespeicherte Verknüpfung im nächsten Block passt dann nicht mehr; die Veränderung wird sichtbar.
Digitale Signaturen vorbereiten
Bei einer digitalen Signatur wird üblicherweise ein Hashwert des Dokuments signiert. Die Signaturprüfung verbindet dadurch die Integrität des Inhalts mit der Prüfung des verwendeten öffentlichen Schlüssels. Die Hashfunktion allein bestätigt jedoch keine Identität.
Hashfunktionen unterstützen Integrität. Vertraulichkeit erfordert Verschlüsselung, und Authentizität benötigt zusätzlich ein geeignetes Signatur- und Vertrauensverfahren.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Hashfunktion
- Grundidee
- Eingabe wird auf Hashwert abgebildet
- gleiche Eingabe ergibt gleichen Wert
- Grenzen
- Kollisionen sind möglich
- Hashing ist keine Verschlüsselung
- Anforderungen
- Hashtabelle: schnell und gleichmäßig
- Kryptographie: schwer umkehrbar und kollisionsresistent
- Ähnlichkeitssuche: ähnliche Inhalte zusammenführen
- Anwendungen
- Tabellenzugriff
- Integritätsprüfung
- Passwortprüfung
- Signaturen und Blockverknüpfung
- Grundidee
Abschluss-Check
Du hast den Kern verstanden, wenn du bei einem Verfahren zuerst nach seinem Zweck fragst: schneller Zugriff, Ähnlichkeitssuche, Integritätsprüfung und Passwortschutz verlangen unterschiedliche Eigenschaften.