Meet-in-the-Middle und Zeit-Speicher-Kompromisse

MITM-Angriffe teilen eine Chiffre in zwei Hälften und greifen diese unabhängig voneinander an. Der Angreifer erstellt von einem Ende aus eine Tabelle und sucht dann vom anderen Ende aus nach einer Übereinstimmung. Dadurch sinkt die Angriffskomplexität von O(2^{2n}) auf O(2^n), allerdings mit einem Speicherbedarf von O(2^n).

Double-DES wendet DES zweimal an: C = DES_{K2}(DES_{K1}(P)). Der Schlüsselraum umfasst 2^{112} Möglichkeiten. MITM-Angriff: Berechnen Sie für alle 2^{56} K1-Werte DES_{K1}(P) und speichern Sie die Ergebnisse. Berechnen Sie für alle 2^{56} K2-Werte DES_{K2}^{-1}(C) und suchen Sie die Ergebnisse in der Tabelle. Eine Übereinstimmung → Kandidat (K1, K2). Insgesamt sind nur 2^{57} Berechnungen erforderlich.

Schritt 1: Verschlüsseln Sie den Klartext P mit allen möglichen K1-Werten → Tabelle T[DES_{K1}(P)] = K1. Schritt 2: Entschlüsseln Sie für jeden K2-Wert den Chiffretext C: v = DES^{-1}_{K2}(C). Prüfen Sie, ob v ∈ T gilt. Wenn T[v] = K1 vorhanden ist, verifizieren Sie (K1, K2) anhand eines zweiten Klartext-Chiffretext-Paars. Rechnen Sie mit 1–2 falschen Übereinstimmungen und verwerfen Sie diese.

Triple-DES (3DES) verwendet drei Schlüssel K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM ist weiterhin möglich, allerdings mit geringerer Wirkung: Bei 2-Key-3DES (K3=K1) sind 2^{112} Berechnungen erforderlich. Für 3-Key-3DES existiert ein MITM-Angriff mit 2^{112} Berechnungen. Das erklärt, warum 3DES trotz eines 168-Bit-Schlüssels nur etwa 112 Bit effektive Sicherheit bietet.

Hellman (1980): Berechnen Sie vorab eine Tabelle mit Ketten aus (start_point, end_point), um die Offline-Schlüsselsuche zu beschleunigen. Suchen Sie bei einem Ziel-Hash oder Chiffretext in der Hellman-Tabelle nach einer Kette, die ihn enthält. Kompromiss: P = N (Zeit × Speicher = konstanter Speicherplatz). Dies bildet die Grundlage für Rainbow-Tabellen.

Rainbow-Tabellen (Oechslin, 2003) verbessern Hellman-Tabellen, indem sie an jeder Kettenposition unterschiedliche Reduktionsfunktionen verwenden und dadurch Fehlalarme (zusammengeführte Ketten) vermeiden. Sie eignen sich besonders zum Knacken ungesalzener Passwort-Hashes. Eine Suche benötigt O(table_size/chain_length) Zeit.

Ein Salt ist ein zufälliger Wert, der vor dem Hashing dem Passwort vorangestellt wird: H(salt||password). Unterschiedliche Salts erzeugen für dasselbe Passwort unterschiedliche Hashes – eine Rainbow-Tabelle für "password" ist nutzlos, wenn ein anderer Salt verwendet wurde. Salts müssen zusammen mit dem Hash gespeichert werden.

MITM-Angriffe auf AES-128 (10 Runden) teilen bekannte Angriffe nach Runde 5 auf: Sie verschlüsseln 5 Runden vorwärts, entschlüsseln 5 Runden rückwärts und treffen sich in der Mitte. Der beste bekannte Angriff ist ein Biklique-Angriff, der 2^{128} auf 2^{126.1} reduziert. Er ist nicht praktisch durchführbar, zeigt aber, dass AES gegenüber MITM-ähnlichen Ansätzen keine Sicherheitsreserve besitzt.

Bei Merkle-Damgård-Hashfunktionen kann MITM für bestimmte Konstruktionen Präbilder schneller als durch vollständiges Ausprobieren finden. Der Angriff erstellt eine Tabelle aus Nachrichtenblöcken, die beim IV beginnen, und sucht vom Ziel-Hash aus rückwärts. Gegen SHA-256 mit allen Runden sind weiterhin etwa 2^{255} Berechnungen erforderlich – keine Verbesserung gegenüber vollständigem Ausprobieren.

Der Dissection-Angriff verallgemeinert MITM auf Aufteilungen in r Teile. Bei einer Aufteilung einer Chiffre in drei Teile werden 1/3 der Runden vorwärts verschlüsselt, die Mitte der Kette wird abgeglichen und anschließend 1/3 der Runden rückwärts entschlüsselt. Er benötigt O(2^{n*2/3}) Zeit und O(2^{n/3}) Speicher – ein ausgewogenerer Kompromiss.

In Protokollen lassen sich MITM-Angriffe verhindern, indem Sie lange, aus passwortbasierten KDFs abgeleitete Schlüssel mit hoher Entropie verwenden (dadurch wird der enumerierbare Schlüsselraum verkleinert), Hardware-Token (FIDO2) einsetzen, deren Schlüssel das Gerät nie verlässt, oder eine Public-Key-Authentifizierung verwenden (kein gemeinsames Geheimnis, das enumeriert werden kann).

Wie hoch ist die effektive Sicherheit von Double-DES (2x DES, kombinierter 112-Bit-Schlüssel) gegen einen MITM-Angriff?

MITM-Angriffe teilen Chiffren in Hälften und reduzieren den Zeitaufwand mit 2^n Speicher von 2^{2n} auf 2^n. Dadurch wird Double-DES gebrochen; 3DES ist dagegen besser geschützt, bietet aber nur 112 Bit effektive Sicherheit. Rainbow-Tabellen verwenden MITM-Logik zum Knacken von Passwörtern und werden durch Salts verhindert. Als Nächstes: Timing-Angriffe und Seitenkanalangriffe.