SHA-1 Längenangriff: UF-CMA brechen – Tutorial Kryptographie CS6260

Einführung in die Längenangriff-Sicherheitslücke

In der angewandten Kryptographie ist die UF-CMA-Sicherheit (unforgeability under chosen message attack) ein zentrales Konzept. Ein klassisches Beispiel für eine unsichere Konstruktion ist ein MAC (Message Authentication Code), der auf einem Hash wie SHA-1 basiert und den geheimen Schlüssel einfach vor die Nachricht setzt: tag = SHA1(key || message). Dieser Ansatz ist anfällig für einen Längenangriff (length extension attack). In diesem Tutorial zeigen wir, wie ein Angreifer ohne Kenntnis des Schlüssels gültige (message, tag)-Paare fälschen kann. Dies ist genau die Problemstellung aus dem Assignment CS6260 Homework 1: Breaking SHA-1.

Warum ist das heute relevant? SHA-1 gilt seit 2017 als kryptographisch unsicher, und Längenangriffe sind eine der Hauptschwachstellen von Merkle-Damgård-Hashes. Wer in der IT-Sicherheit arbeitet oder studiert, muss diese Angriffsform verstehen – nicht nur für Prüfungen, sondern auch für reale Anwendungen wie Blockchain-Protokolle oder API-Authentifizierung.

Wie funktioniert ein Längenangriff?

Ein Längenangriff nutzt die Struktur von Merkle-Damgård-Hashes aus. SHA-1 verarbeitet Nachrichten blockweise (512 Bit) und verwendet einen internen Zustand (160 Bit). Kennt man den Hash H(M) und die Länge von M, kann man den Hash von M || padding || extra berechnen, ohne M selbst zu kennen. Der Trick: Man initialisiert den SHA-1-Algorithmus mit dem bekannten Hashwert und verarbeitet dann den Padding-Block sowie die zusätzlichen Daten. Der Padding-Block wird dabei aus der ursprünglichen Nachrichtenlänge berechnet.

Für den MAC-Angriff bedeutet das: Der Angreifer kennt tag = SHA1(key || message) und die Länge von key (z.B. 16 Bytes). Dann kann er SHA1(key || message || padding || extra) berechnen, ohne den Schlüssel zu kennen. Der Padding-Block hängt von der Gesamtlänge len(key) + len(message) ab. Da die Schlüssellänge bekannt ist, kann der Angreifer das Padding korrekt konstruieren.

Praktische Umsetzung in Python

Das Assignment stellt eine Datei student.py bereit, die eine Funktion main() enthalten muss, die ein (message, tag)-Paar zurückgibt. Der Tag ist ein Hex-String, die message ein Byte-Array. Wir implementieren den Angriff mit Hilfe der hashlib-Bibliothek und einer speziellen SHA-1-Implementierung, die den internen Zustand setzen kann. Da hashlib dies nicht direkt erlaubt, nutzen wir die bereitgestellte sha1_lib (im Assignment enthalten).

Zunächst importieren wir die benötigten Module:

import struct
import hashlib
from sha1_lib import SHA1

Die Funktion main() soll folgende Schritte ausführen:

Bekannte Daten sammeln: Wir haben ein (message, tag)-Paar, das vom Server stammt. Nehmen wir an, wir kennen die Nachricht original_msg und den zugehörigen Tag original_tag (Hex). Die Schlüssellänge sei key_len (z.B. 16 Bytes).
Padding berechnen: Für die ursprüngliche Nachricht key || original_msg wird der Padding-Block gemäß SHA-1-Spezifikation berechnet. Die Länge der ursprünglichen Nachricht ist key_len + len(original_msg) Bytes. Das Padding besteht aus einem '1'-Bit, gefolgt von Nullen, dann einer 64-Bit-Längenangabe in Bits.
Internen Zustand initialisieren: Wir parsen den original_tag (20 Bytes) in fünf 32-Bit-Wörter (h0-h4). Das ist der interne Zustand nach Verarbeitung der ursprünglichen Nachricht inklusive Padding.
Zusatzdaten anhängen: Wir wählen eine beliebige Zusatznachricht extra (z.B. b"&admin=true"). Dann berechnen wir den SHA-1-Hash, indem wir mit dem internen Zustand starten und die Zusatzdaten (ohne erneutes Padding der Gesamtnachricht) verarbeiten. Dabei müssen wir beachten, dass SHA-1 am Ende noch einen Padding-Block für die gesamte neue Nachricht anhängt. Da wir den internen Zustand aber nach dem ursprünglichen Padding setzen, müssen wir den Padding-Block für die Zusatzdaten selbst berechnen und mitverarbeiten.

Ein vereinfachter Code-Ausschnitt:

def main():
    # Gegeben
    original_msg = b"test"
    original_tag = "..."  # Hex von Server
    key_len = 16  # in Bytes

    # Padding für original (key || msg)
    total_len = key_len + len(original_msg)
    padding = sha1_pad(total_len)  # erzeugt Padding-Bytes

    # Internen Zustand aus original_tag setzen
    h = struct.unpack('>5I', bytes.fromhex(original_tag))

    # Zusatznachricht
    extra = b"&admin=true"

    # SHA-1 mit initialem Zustand h und extra als Eingabe
    sha = SHA1(state=h, count=(total_len + len(padding)) * 8)  # count in Bits
    sha.update(extra)
    forged_tag = sha.hexdigest()

    # Forged message = original_msg + padding + extra
    forged_msg = original_msg + padding + extra
    return (forged_msg, forged_tag)

Wichtig: Die sha1_lib-Klasse erlaubt es, den internen Zustand und die bisher verarbeitete Bitanzahl zu setzen. Das Padding für die Zusatzdaten wird automatisch von sha.update angehängt, aber da wir den Zustand nach dem ursprünglichen Padding gesetzt haben, müssen wir sicherstellen, dass die Längenangabe korrekt ist. In der Praxis wird die count-Variable auf die Gesamtlänge der ursprünglichen Nachricht inklusive Padding gesetzt.

Verbindung zu aktuellen Trends

Längenangriffe sind nicht nur akademisch. Im Jahr 2026 sind viele APIs immer noch mit einfachen Hash-basierten MACs geschützt. Ein aktuelles Beispiel: Die Authentifizierung für eine beliebte KI-gestützte Lernplattform könnte auf ähnliche Weise angreifbar sein. Wenn ein Entwickler fälschlicherweise SHA1(secret + message) verwendet, kann ein Angreifer durch einen Längenangriff beliebige Admin-Befehle anhängen – ähnlich wie wir oben &admin=true appended haben. Auch in Blockchain-Smart-Contracts tauchen solche Schwachstellen auf, wenn z.B. Merkle-Bäume falsch implementiert werden.

In der Gaming-Welt: Stell dir vor, ein Spiel speichert den Highscore als SHA1(secret + score). Ein Spieler könnte durch Längenangriff einen manipulierten Score anhängen und so die Rangliste fälschen. Das zeigt, wie wichtig es ist, sichere MAC-Konstruktionen wie HMAC zu verwenden.

Warum HMAC die Lösung ist

HMAC (Hash-based Message Authentication Code) ist resistent gegen Längenangriffe, da es den Schlüssel zweimal verwendet und die innere Struktur des Hashs ausnutzt. Die Formel lautet: HMAC(K, m) = H((K' ⊕ opad) || H((K' ⊕ ipad) || m)). Durch die XOR-Operationen und die doppelte Hashung wird der Angriff unmöglich. Für das Assignment reicht es zu verstehen, warum die naive Konstruktion unsicher ist – und dass HMAC der empfohlene Standard ist.

Fazit und Ausblick

Der Längenangriff auf SHA-1-basierte MACs ist ein Paradebeispiel für die Lücke zwischen Theorie und Praxis. Wer Kryptographie versteht, kann solche Angriffe nicht nur nachvollziehen, sondern auch vermeiden. In der Hausaufgabe CS6260 geht es genau darum: die Lücke zu schließen, indem man den Angriff implementiert und dokumentiert. Die Abgabe besteht aus dem modifizierten Code in student.py und einem kurzen Bericht.

Denk daran: Verwende in der Praxis immer HMAC oder modernere Verfahren wie SHA-256 mit HMAC. SHA-1 ist tot – aber seine Lehren leben weiter.