Kategorien
Alle Beiträge Uncategorized

Hashfunktionen – Erklärung

Definition: Eine Hashfunkion ist eine Funktion, die einen Wert beliebiger Länge als Input (Pre-Image) entgegen nimmt und daraus einen Output (Digest) fester länge berechnet.

Hash function input->function->output

Der Output wird in der Regel als Hexadezimalzahl dargestellt.

Eigenschaften von Hashfunktionen

Hashfunktionen haben bestimmte Eigenschaften.

Deterministisch: Für den Gleichen Input erhält man stets den gleichen Output.

Einweg: Die Berechnung kann nur in einer Richtung durchgeführt werden.

Hat man einen Input M1 und einen Hash-Output H(M1), ist es praktisch unmöglich, einen zweiten Input M2 zu finden, der sich von M1 unterscheidet, sodass der Output aber gleich ist (H(M1) = H(M2)).

Das heißt, es ist unmöglich, den Input aus dem Output zurückzuberechnen.

Input beliebiger Länge: Es spielt keine Rolle, was als Input für die Hashfunktion genutzt wird. Es wird in jedem Fall ein Output erzeugt. Jedoch gibt es auch spezielle Hashfunktionen, die eine Mindestlänge des Inputs erfordern.

Output: Viele Hashfunktionen erzeugen Outputs fester Länge. Allerdings gibt es auch Hashfunktionen, die Outputs mit variabler Länge erzeugen.

Effiziente Berechnung: In vielen Fällen sind Hashfunktionen schnell zu berechnen. Aber es gibt besondere Anwendungen, die sehr langsame Hashfunktionen erfordern. Dies ist zum Beispiel im Proof of Capacity der Fall oder beim Schutz von Passworten vor Brute-Force-Angriffen.

Uniformität: Es ist wünschenswert, dass die Inputs gleichmäßig und mit gleicher Wahrscheinlichkeit auf die Outputmenge abgebildet werden. Dies bedeutet auch, dass bereits eine kleine Änderung des Inputs zu einer großen Änderung im Output führen kann. Allerdings gibt es auch Hashfunktionen, die sich darauf spezialisiert haben, bei ähnlichen Inputs ähnliche Outputs zu erzeugen (Fuzzy Hashes oder Locality Sensitive Hashing)

Eigenschaften kryptografischer Hashfunktionen

Für kryptografische Hashfunktionen gibt es weitere Eigenschaften:

Kollisionsfreiheit: Es sollte praktisch unmöglich sein, zwei unterschiedliche Inputs M1 und M2 zu finden, die den gleichen Output H(M1) = H(M2) hervorbringen.

Selbstverständlich gibt es Kollisionen, da wir eine unendlich große Eingabemenge auf eine endliche Outputmenge abbilden. Aber die Outputmenge ist so groß, dass es praktisch unmöglich ist, eine solche Kollision zu finden.

Hiding: Wenn ein geheimer, zufällig gewählter Wert R und ein Hahoutput H(R|M) gegeben sind, dann ist es praktisch unmöglich M zu finden. R|M bedeutet, dass die Zeichenketten R und M miteinander verknüpft wurden.

Wenn wir also einen Inputwert M mit einem anderen unbekannten, zufälligen Wert R verknüpft haben und das Ergebnis gehasht wurde, kann der Originalwert von M nicht mehr zurückberechnet werden. R wird manchmal als Salt bezeichnet. Es schützt Eingabewerte M mit geringer Entropie vor Brute-Force-Angriffen.

Die Hiding-Eigenschaft ist der Einweg-Eigenschaft sehr ähnlich.

Beispiel:

Angenommen, wir wollen unser Alter in Jahren hashen, um uns darauf festzulegen. Aber wir wollen es nicht vor einem Bestimmten Zeitpunkt verraten. Jetzt könnte ein Angreifer jedoch alle Zahlen zwischen 0 und 120 durchprobieren, die als Alter in Frage kommen, und die Hashes mit unserem Hash vergleichen. Das würde sehr schnell gehen. Um unser Alter zu schützen, können wir es mit einem Zufallsstring R verknüpfen. Diesen Wert halten wir geheim.

Nach Ablauf der Geheimhaltungszeit veröffentlichen wir unser Alter und den Zufallsstring R. Mit beiden Angaben kann jeder überprüfen, ob diese zu demselben Hash führen, den wir zu Beginn erzeugt haben.

Puzzlefreundlich: Eine Hashfunktion H ist puzzlefreundlich, wenn für jeden möglichen n-bit langen Output Y und einen zufällig gewählten Wert R es unmöglich ist, einen Input M zu finden in einer Zeit weniger als 2^n bei dem gilt H(R|M) = Y.

Dies bedeutet, dass sich der Output gleichmäßig über den Output-Wertebereich erstreckt und unabhängig vom Input ist. Es gibt also keine bessere Strategie, als alle Werte von M durchzuprobieren, bis der richtige Wert gefunden wurde.

Beim Bitcoin-PoW bedeutet das, dass man versucht, einen Hashwert bestimmter Länge zu finden (Anzahl führender Nullen). Dabei gibt es keine Möglichkeit, einen Inputwert M zu finden, der mit einer höheren Wahrscheinlichkeit einen gewünschten Output bringt.

Die Eigenschaft der Puzzlefreundlichkeit darf nicht mit der Hiding-Eigenschaft verwechselt werden, obwohl sie sehr ähnlich sind.

Beispiele kryptografischer Hashfunktionen

Hier sind ein paar Beispiele kryptografischer Hashfunktionen:

Anwendungen von Hashfunktionen

Hash functions are used for many purposes. Here you find a list of common applications.

Hashfunktionen warden für viele Zwecke eingesetzt. Hier ist eine Liste mit üblichen Anwendungen:

  • Commit-Reveal Schemes
  • Signaturen (diese benötigen einen String fester Länge als Input)
  • Public Private key-Infrastructure
  • Hashtables
  • Sharding
  • Sicherheitsabgleiche von Dateien