Kryptografische Hashverfahren

1. Preimage Resistance (Einwegfunktion): Zu gegebenem $h$ ist es schwer, ein $m$ mit $H(m)=h$ zu finden.
2. Second Preimage Resistance: Zu gegebenem $m$ ist es schwer, ein $m' \neq m$ mit $H(m)=H(m')$ zu finden.
3. Collision Resistance: Es ist schwer, irgendein Paar $(m, m')$ mit $m \neq m'$ und $H(m)=H(m')$ zu finden.

Aufwand: Preimage und Second Preimage $\approx 2^n$, Collision nur $\approx 2^{n/2}$.

Wegen des Geburtstagsparadoxons: Man sucht kein bestimmtes Urbild, sondern irgendein kollidierendes Paar. Die Anzahl möglicher Paare wächst quadratisch mit $k$, sodass die Kollisionswahrscheinlichkeit bereits ab $$k \approx \sqrt{2 \cdot 2^n \cdot \ln 2} \approx 1{,}177 \cdot 2^{n/2}$$ Versuchen nennenswert wird. Für $n=256$: $k \approx 2^{128}$.

• Second Preimage: die Nachricht $m$ ist fest vorgegeben. Angreifer sucht $m' \neq m$ mit gleichem Hash. Aufwand $\approx 2^n$.
• Collision: Beide Nachrichten sind frei wählbar. Aufwand nur $\approx 2^{n/2}$ (Birthday).

Aus Collision Resistance folgt Second Preimage Resistance (aber nicht umgekehrt). Deshalb ist Collision Resistance die stärkere Eigenschaft.

• MD5 (128 Bit): Birthday-Grenze bei $2^{64}$, aber strukturelle Angriffe (Wang et al., 2004) liefern Kollisionen in Sekunden. Chosen-Prefix-Kollisionen wurden bereits für gefälschte X.509-Zertifikate ausgenutzt.
• SHA-1 (160 Bit): 2017 durch Google/CWI (SHAttered) praktisch gebrochen – zwei PDFs mit gleichem SHA-1 wurden veröffentlicht. Kosten damals ca. $110$ GPU-Jahre.

Standards heute: SHA-256, SHA-3 oder BLAKE2/BLAKE3.

Ein Salt ist ein zufälliger, pro Nutzer individueller Wert, der beim Hashen des Passworts angehängt wird: $H(p \| s)$. Der Salt wird zusammen mit dem Hash gespeichert – er muss nicht geheim sein.

Zweck:

• Vernichtet Rainbow-Tables: vorab berechnete Tabellen müssten pro Salt neu berechnet werden.
• Verhindert, dass zwei Nutzer mit identischem Passwort denselben Hash haben.
• Erschwert Massenangriffe: jeder Account muss einzeln angegriffen werden.

SHA-256 ist auf Geschwindigkeit optimiert – moderne GPUs berechnen $10^{10}$ Hashes/s. Für Passwörter ist genau das schlecht: Brute-Force wird trivial.

bcrypt / scrypt / Argon2 sind bewusst langsam und (bei Argon2/scrypt) speicherhart:

• Konfigurierbare Kostenparameter (Iterationen, Speicher, Parallelität).
• Ein einzelner Hash dauert z.B. $100$ ms, Brute-Force skaliert nicht linear mit GPU-Kernen.
• Argon2 zusätzlich speicherhart $\Rightarrow$ ASIC/GPU-Angriffe teuer.

Faustregel: für Passwörter immer bcrypt/scrypt/Argon2 statt einer schnellen Hashfunktion.

HMAC ist eine schlüsselabhängige Hashkonstruktion zur Nachrichtenauthentifizierung: $$\text{HMAC}(k, m) = H\bigl((k' \oplus \text{opad}) \,\|\, H((k' \oplus \text{ipad}) \,\|\, m)\bigr).$$

$H(k \| m)$ ist bei Merkle-Damgård-Hashes wegen Length-Extension-Angriffen unsicher: Aus $H(k \| m)$ und $|m|$ lässt sich $H(k \| m \| \text{pad} \| x)$ berechnen, ohne $k$ zu kennen. Ein Angreifer kann so gültige MACs für erweiterte Nachrichten erzeugen.

HMAC umgeht das durch den äußeren Hash-Aufruf mit opad – der finale Zustand ist nicht mehr der interne Zustand am Nachrichtenende, sondern das Ergebnis eines neuen Hashings.

Bei RSA/DSA/ECDSA wird nicht die Nachricht $m$ selbst signiert, sondern $H(m)$: $$\sigma = \text{Sign}_{sk}(H(m)).$$

Gründe:

• Effizienz: die Signaturoperation ist teuer (asymmetrisch) und arbeitet auf festem Blockformat.
• Feste Größe: unabhängig von der Nachrichtenlänge.
• Sicherheit: verhindert existentielle Fälschungen (z.B. bei RSA würde ohne Hash die multiplikative Struktur $\text{Sig}(m_1 \cdot m_2) = \text{Sig}(m_1) \cdot \text{Sig}(m_2) \mod n$ Fälschungen erlauben).
• Domain Separation: Hash mit strukturiertem Padding trennt Anwendungsfälle sauber.

Voraussetzung: die verwendete Hashfunktion muss kollisionsresistent sein, sonst könnte ein Angreifer zwei Nachrichten mit gleichem Hash finden und eine Signatur austauschen.

Der Avalanche-Effekt beschreibt: Eine minimale Änderung an der Eingabe (z.B. ein einzelnes Bit) ändert im Idealfall ca. die Hälfte der Ausgabebits – die Ausgabe wirkt zufällig verändert.

Wichtig, weil sonst Ähnlichkeiten von Eingaben in den Hashwerten sichtbar wären, was Angriffe (differentielle Kryptanalyse, gezielte Kollisionssuche) erleichtern würde.

• SHA-2: Merkle-Damgård-Konstruktion mit Kompressionsfunktion. Nachrichte wird geblockt, iterativ komprimiert. Anfällig für Length-Extension-Angriffe.
• SHA-3 (Keccak): Sponge-Konstruktion. Zustand $b = r+c$ Bit, Absorbing- und Squeezing-Phase mit fester Permutation $f$. Keine Kompressionsfunktion, keine Length-Extension-Anfälligkeit.

SHA-3 wurde als "Sicherheitsreserve" gewählt, falls SHA-2 einmal geschwächt würde – die grundlegend andere Konstruktion macht gemeinsame Angriffe unwahrscheinlich.

Der Salt hat nicht den Zweck, Informationen zu verstecken, sondern jeden Passwort-Hash zu individualisieren. Dadurch:

• Rainbow Tables werden nutzlos, weil sie pro Salt neu berechnet werden müssten.
• Zwei Nutzer mit identischem Passwort haben unterschiedliche Hashes.

Beim Login muss der Server den Salt kennen, um den Hash reproduzieren zu können – also wird er zusammen mit dem Hash im Klartext gespeichert.

Wegen des Birthday-Angriffs kostet Kollisionsfinden nur $\approx 2^{n/2}$. Die effektive Kollisionssicherheit ist also halbiert gegenüber der Ausgabelänge:

• $n = 128$ (MD5): nur $64$ Bit Kollisionsresistenz $\Rightarrow$ zu wenig.
• $n = 160$ (SHA-1): $80$ Bit $\Rightarrow$ heute unzureichend.
• $n = 256$ (SHA-256, SHA-3-256): $128$ Bit $\Rightarrow$ aktueller Standard.
• $n = 512$ (SHA-512): $256$ Bit $\Rightarrow$ für Langzeit-Sicherheit.

Faustregel: Für $k$ Bit Kollisionssicherheit braucht man $n \geq 2k$ Bit Ausgabelänge.