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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K = (K_1, K_2, \cdots, K_n)} gegeben und ohne Beschränkung der Allgemeinheit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gerade und $|K_{1}|=|K_{2}|=\dots =|K_{n}|$. Dazu sei ein Verschlüsselungsverfahren gegeben durch:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_1} mit der Klartextnachricht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} das erste Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_1 = \operatorname{Enc}_{K_1}(M)} berechnen. Gleichzeitig berechnet er für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_n} mit dem Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} das Ergebnis des letzten Zwischenschrittes durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (K_1, K_2, \cdots, K_{n/2})} und für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \cdot 2^{|\frac{K}{2}|}} Speicheraufwand, da für beide Mengen an Chiffraten nur jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} in das ursprüngliche Chiffrat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{|K|}} gegeben. Der beschriebene Angriff muss jedoch nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \cdot 2^{|\frac{K}{2}|}} Chiffrate berechnen und ist damit signifikant schneller. Zusätzlich fällt ein erhöhter Speicherbedarf von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} wird mit einem DES-Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_1} chiffriert, dann mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_2} dechiffriert und schließlich mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_3} chiffriert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{3DES}_{(K_1, K_2, K_3)} := \operatorname{DES}_{K_3} \circ \operatorname{DES}^{-1}_{K_2} \circ \operatorname{DES}_{K_1}}

Da die Schlüssellänge von DES 56 Bit beträgt, hat der Triple-DES-Schlüsselraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{56}} mal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{DES}^{-1}_{K_3}(C)} aus und speichert die Ergebnisse zusammen mit dem verwendeten Teilschlüssel. Dann berechnet er Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{112}} mal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z = \operatorname{DES}^{-1}_{K_2} \circ \operatorname{DES}_{K_1}(M)} und vergleicht das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.