Hashes

Grundlagen

Hashfunktion

• Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet.
• Eine „gute" Hashfunktion liefert dabei für die (erwarteten) Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen.
• Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt.

Kollisionen

• Eine sog. Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird.
• Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich.
• Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.

Funktion

Auf Rechner1 wird aus den Daten ein Hash-Rechner1 gebildet

[Bearbeiten]

Rechner1 schickt Daten und Hash an Rechner2

[Bearbeiten]

Rechner2 bildet aus den empfangenen Daten den Hash-Rechner2

[Bearbeiten]

Ergebnis

Anwendungen

Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:

• Datenbanken
  • In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle).
• Prüfsummen
  • Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen.
• Kryptologie
  • In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.

Kryptologische Hashfunktionen

• Eine kryptologische Hashfunktion oder kryptographische Hashfunktion ist eine spezielle Form der Hashfunktion, welche kollisionsresistent sein sollte und nach Definition immer eine Einwegfunktion ist.
• Kryptologische Hashfunktionen werden in schlüssellose und schlüsselabhängige eingeteilt.
  • Schlüssellose Hashfunktionen benötigen keinen geheimen Schlüssel (z. B. SHA-256, MD5).
  • Schlüsselabhängige Hashfunktionen (auch MAC) verwenden zusätzlich einen geheimen Schlüssel zur Berechnung des Hashwerts (z. B. HMAC).

Einfaches Beispiel Quersumme

• Fritz bekommt als Rechenaufgabe auf $x$ auszurechnen. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = 9^2\times 2+7}
• Die Quersumme beträgt 16.
• Fritz rechnet 169 aus.
• Fritz zählt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1+6+9=16}
• Ergebnis stimmt.

Hinweis: Die Quersumme dient hier nur zur Illustration des Prinzips. Sie ist keine kryptologische Hashfunktion, da sie nicht kollisionsresistent ist – so ergibt z. B. auch die Zahl 97 die Quersumme 16.

Merkle-Damgård-Verfahren

• Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht M zuerst in Blöcke fester Länge geteilt
• Der letzte Block wird mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt.
• Die Funktion hat als Input einen Nachrichtenblock und den Wert des letzten Hashberechnung (außer beim ersten Block).
• Der Output entspricht dem Wert der neuen Hashberechnung.
• Der Hashwert der gesamten Nachricht ist der Hashwert des letzten Blocks:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} H\left(0\right) & = IV \\ H\left(i \right) & = f\left(M\left(i \right),H\left(i-1\right)\right), \qquad i=1,2,\dotsc,t \\ h\left(M \right) & = H(t) \end{align}}

IV bezeichnet einen festen Startwert (initial value).

Links

• https://de.wikipedia.org/wiki/Hashfunktion
• https://de.wikipedia.org/wiki/Kryptologische_Hashfunktion