Meet-in-the-middle-Angriff

Ein Meet-in-the-middle-Angriff ist ein generischer kryptographischer Angriff. Er macht sich zu Nutze, dass anfällige kryptographische Algorithmen ihren Schlüssel zerteilen, und während der Berechnung des Chiffrats in einzelnen Schritten nur einen Teil des Schlüssels verwenden. Ein gängiges Beispiel dafür sind Verschlüsselungsverfahren, die ihren eigentlichen Verschlüsselungsalgorithmus mehrfach mit jeweils unterschiedlichen Schlüsseln anwenden.

Verfahren

In einem kryptographischen Verfahren, das nicht anfällig für diese Art von Angriffen ist, wird ein Klartext und ein Schlüssel als Eingabe für einen Algorithmus verwendet und daraus zum Beispiel ein Chiffrat errechnet. Liegt einem Angreifer ein Paar aus Klartext und Chiffrat vor, kann er (sofern das Verfahren nicht verwundbar durch einen anderen Angriff ist) den Schlüssel nur errechnen, indem er mit der Brute-Force-Methode alle möglichen Schlüssel ausprobiert, und das Ergebnis mit dem Chiffrat vergleicht. Teilt nun aber der Algorithmus den Schlüssel auf und berechnet einzelne Zwischenergebnisse mit jeweils einem Schlüsselteil, ohne von den übrigen Schlüsselteilen Gebrauch zu machen, so kann ein Angreifer die Teile des Schlüssels einzeln errechnen. Dabei profitiert der Angreifer vom enorm reduzierten Rechenaufwand. Greift er dabei die Teile des Verfahrens von beiden Seiten des Algorithmus (also vom Klartext und rückwärts vom Chiffrat aus) gleichzeitig an, so spricht man von einem Meet-in-the-middle-Angriff. Notwendige Voraussetzung ist folglich, dass sich die Zwischenschritte umkehren lassen.

Sei $K=(K_{1},K_{2},\cdots ,K_{n})$ gegeben und ohne Beschränkung der Allgemeinheit $n$ gerade und $|K_{1}|=|K_{2}|=\dots =|K_{n}|$. Dazu sei ein Verschlüsselungsverfahren gegeben durch:

$\operatorname {Enc} _{K}:=\operatorname {Enc} _{K_{n}}\circ \operatorname {Enc} _{K_{n-1}}\circ \cdots \circ \operatorname {Enc} _{K_{1}}$

Dann kann der Angreifer für alle $K_{1}$ mit der Klartextnachricht $M$ das erste Chiffrat $C_{1}=\operatorname {Enc} _{K_{1}}(M)$ berechnen. Gleichzeitig berechnet er für alle $K_{n}$ mit dem Chiffrat $C$ das Ergebnis des letzten Zwischenschrittes durch $C_{n-1}=\operatorname {Enc} _{K_{n}}^{-1}(C)$. Aus den jeweils berechneten Zwischenergebnissen berechnet der Angreifer nun solange jeweils die nächsten Zwischenschritte, bis er von beiden Seiten aus beim selben Zwischenschritt angekommen ist. Diese Chiffrate, die er nun für alle $(K_{1},K_{2},\cdots ,K_{n/2})$ und für alle $(K_{{\frac {n}{2}}+1},K_{{\frac {n}{2}}+2},\cdots ,K_{n})$ berechnet hat, muss der Angreifer nun temporär zusammen mit dem jeweiligen Schlüsselteil abspeichern. Dies erfordert $2\cdot 2^{|{\frac {K}{2}}|}$ Speicheraufwand, da für beide Mengen an Chiffraten nur jeweils $\prod _{i=1}^{\frac {N}{2}}|K_{i}|$ Möglichkeiten zur Schlüsselwahl bestehen. In diesen beiden Mengen gibt es genau ein Paar aus Chiffraten, die übereinstimmen: Dieses ist das Chiffrat, welches durch die Teilschlüssel erzeugt wurde, welche zusammengenommen die ursprüngliche Nachricht $M$ in das ursprüngliche Chiffrat $C$ überführt haben. Der gesuchte geheime Schlüssel ist demnach zusammengesetzt aus den Teilschlüsseln, die mit dem gefundenen Zwischenergebnis abgespeichert wurden.

Die Komplexität eines herkömmlichen Brute-Force-Angriffs ist durch $2^{|K|}$ gegeben. Der beschriebene Angriff muss jedoch nur $2\cdot 2^{|{\frac {K}{2}}|}$ Chiffrate berechnen und ist damit signifikant schneller. Zusätzlich fällt ein erhöhter Speicherbedarf von $2\cdot 2^{|{\frac {K}{2}}|}$ gegenüber der Brute-Force-Methode an. Man spricht deshalb von einem Time-Memory Tradeoff. Verzichtet der Angreifer auf die Parallelisierung des Verfahrens, genügt sogar ein Speicheraufwand von $2^{|{\frac {K}{2}}|}$, da die zweite Chiffratmenge schon während der Berechnung mit der ersten, gespeicherten Menge verglichen werden kann und somit nicht gespeichert werden muss. Diese Angaben beziehen sich auf den optimalen Fall, dass $n$ gerade ist und die Teilschlüssel gleich groß sind. Ist dies nicht der Fall, kann nur eine annähernd optimale Reduzierung des Rechen- und Speicheraufwandes erreicht werden.

Triple-DES Beispiel

Bei der Triple-DES-Verschlüsselung wird das ursprüngliche DES-Verfahren dreimal hintereinander, jedoch mit unterschiedlichen Schlüsseln angewendet. Jede Nachricht $M$ wird mit einem DES-Schlüssel $K_{1}$ chiffriert, dann mit $K_{2}$ dechiffriert und schließlich 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 von DES 56 Bit beträgt, hat der Triple-DES-Schlüsselraum $2^{56}\cdot 2^{56}\cdot 2^{56}=2^{168}$ Elemente.

Durch den Meet-in-the-middle-Angriff können nun aber zwei Schritte des Verfahrens einzeln angegriffen werden und dann mit dem dritten Schritt, der rückwärts ausgeführt wird, verglichen werden. Ein Angreifer führt zunächst $2^{56}$ mal $\operatorname {DES} _{K_{3}}^{-1}(C)$ aus und speichert die Ergebnisse zusammen mit dem verwendeten Teilschlüssel. Dann berechnet er $2^{112}$ mal $Z=\operatorname {DES} _{K_{2}}^{-1}\circ \operatorname {DES} _{K_{1}}(M)$ und vergleicht das $Z$ jeweils mit der gespeicherten Chiffratmenge. Sobald er eine Übereinstimmung gefunden hat, kann er den Schlüssel zusammensetzen.

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. Dies ist auch der Grund, warum kein Double-DES verwendet wird, da dies durch die fehlende zweite Transformation in der Mitte keinen Mehraufwand gegenüber DES beim Berechnen des Schlüssels bedeutet.