Meet-in-the-middle-Angriff

Ein Meet-in-the-middle-Angriff ist ein generischer kryptographischer Angriff.

Triple-DES Beispiel

Bei der Triple-DES-Verschlüsselung wird drei mal das gleiche Verfahren, jedoch mit unterschiedlichen Schlüsseln zur Verschlüsselung verwendet. Jeder Datenblock wird mit einem DES-Schlüssel $K_{1}$ chiffriert, dann mit $K_{2}$ dechiffriert und mit $K_{3}$ chiffriert:

$\operatorname {3DES} _{(K_{1},K_{2},K_{3})}:=\operatorname {DES} _{K_{3}}\circ \operatorname {DES} _{K_{2}}^{-1}\circ \operatorname {DES} _{K_{1}}$

Da die Schlüssellänge 56 Bit ist, gibt es für die ersten beiden Stufen insgesamt $2^{56}\cdot 2^{56}=2^{112}$ mögliche Schlüsselkombinationen.

Die Idee des Meet-in-the-middle-Angriffs ist es, für ein bekanntes Klartext-Ciphertext-Paar $(P,C)$ den Klartext mit allen $2^{112}$ Schlüsselkombinationen zu verschlüsseln und die $2^{112}$ Zwischenergebnisse zu speichern. Dann erzeugt man aus dem Ciphertext das Zwischenergebnis $Z=\operatorname {DES} _{K_{3}}\circ \operatorname {DES} _{K_{2}}^{-1}(P)=\operatorname {DES} _{K_{1}}^{-1}(C)$. Nun muss man das Zwischenergebnis $Z$ mit den $2^{112}$ Zwischenergebnissen vergleichen. Sobald man eine Übereinstimmung gefunden hat, kennt man den Schlüssel.

Der Gesamtaufwand für das finden des Schlüssels ist damit auf $2^{56}\cdot 2^{56}+2^{56}\approx 2^{112}$ DES-Transformationen reduziert.