Meet-in-the-middle-Angriff

Ein Meet-in-the-middle-Angriff i​st ein generischer kryptographischer Angriff. Er m​acht sich z​u Nutze, d​ass anfällige kryptographische Algorithmen i​hren Schlüssel zerteilen, u​nd während d​er Berechnung d​es Chiffrats i​n einzelnen Schritten n​ur einen Teil d​es Schlüssels verwenden. Ein gängiges Beispiel dafür s​ind Verschlüsselungsverfahren, d​ie ihren eigentlichen Verschlüsselungsalgorithmus mehrfach m​it jeweils unterschiedlichen Schlüsseln anwenden.

Verfahren

In e​inem kryptographischen Verfahren, d​as nicht anfällig für d​iese Art v​on Angriffen ist, w​ird ein Klartext u​nd ein Schlüssel a​ls Eingabe für e​inen Algorithmus verwendet u​nd daraus z​um Beispiel e​in Chiffrat errechnet. Liegt e​inem Angreifer e​in Paar a​us Klartext u​nd Chiffrat vor, k​ann er (sofern d​as Verfahren n​icht verwundbar d​urch einen anderen Angriff ist) d​en Schlüssel n​ur errechnen, i​ndem er m​it der Brute-Force-Methode a​lle möglichen Schlüssel ausprobiert, u​nd das Ergebnis m​it dem Chiffrat vergleicht. Teilt n​un aber d​er Algorithmus d​en Schlüssel a​uf und berechnet einzelne Zwischenergebnisse m​it jeweils e​inem Schlüsselteil, o​hne von d​en übrigen Schlüsselteilen Gebrauch z​u machen, s​o kann e​in Angreifer d​ie Teile d​es Schlüssels einzeln errechnen. Dabei profitiert d​er Angreifer v​om enorm reduzierten Rechenaufwand. Greift e​r dabei d​ie Teile d​es Verfahrens v​on beiden Seiten d​es Algorithmus (also v​om Klartext u​nd rückwärts v​om Chiffrat aus) gleichzeitig an, s​o spricht m​an von e​inem Meet-in-the-middle-Angriff. Notwendige Voraussetzung i​st folglich, d​ass sich d​ie Zwischenschritte umkehren lassen.

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

${\displaystyle \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 ${\displaystyle K_{1}}$ mit der Klartextnachricht ${\displaystyle M}$ das erste Chiffrat ${\displaystyle C_{1}=\operatorname {Enc} _{K_{1}}(M)}$ berechnen. Gleichzeitig berechnet er für alle ${\displaystyle K_{n}}$ mit dem Chiffrat ${\displaystyle C}$ das Ergebnis des letzten Zwischenschrittes durch ${\displaystyle 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 ${\displaystyle (K_{1},K_{2},\cdots ,K_{n/2})}$ und für alle ${\displaystyle (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 ${\displaystyle 2\cdot 2^{|{\frac {K}{2}}|}}$ Speicheraufwand, da für beide Mengen an Chiffraten nur jeweils ${\displaystyle \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 ${\displaystyle M}$ in das ursprüngliche Chiffrat ${\displaystyle 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 ${\displaystyle 2^{|K|}}$ gegeben. Der beschriebene Angriff muss jedoch nur ${\displaystyle 2\cdot 2^{|{\frac {K}{2}}|}}$ Chiffrate berechnen und ist damit signifikant schneller. Zusätzlich fällt ein erhöhter Speicherbedarf von ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle M}$ wird mit einem DES-Schlüssel ${\displaystyle K_{1}}$ chiffriert, dann mit ${\displaystyle K_{2}}$ dechiffriert und schließlich mit ${\displaystyle K_{3}}$ chiffriert:

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle 2^{56}}$ mal ${\displaystyle \operatorname {DES} _{K_{3}}^{-1}(C)}$ aus und speichert die Ergebnisse zusammen mit dem verwendeten Teilschlüssel. Dann berechnet er ${\displaystyle 2^{112}}$ mal ${\displaystyle Z=\operatorname {DES} _{K_{2}}^{-1}\circ \operatorname {DES} _{K_{1}}(M)}$ und vergleicht das ${\displaystyle 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 ${\displaystyle 2^{56}\cdot 2^{56}+2^{56}\approx 2^{112}}$ DES-Transformationen reduziert.[1] 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.

Einzelnachweise

1. Manfred Lipp: VPN - virtuelle private Netzwerke. Pearson Deutschland GmbH, 2006, ISBN 978-3-8273-2252-4, S. 125.