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

Bearbeiten

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   gegeben und ohne Beschränkung der Allgemeinheit   gerade und  . Dazu sei ein Verschlüsselungsverfahren gegeben durch:

 

Dann kann der Angreifer für alle   mit der Klartextnachricht   das erste Chiffrat   berechnen. Gleichzeitig berechnet er für alle   mit dem Chiffrat   das Ergebnis des letzten Zwischenschrittes durch  . 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   und für alle   berechnet hat, muss der Angreifer nun temporär zusammen mit dem jeweiligen Schlüsselteil abspeichern. Dies erfordert   Speicheraufwand, da für beide Mengen an Chiffraten nur jeweils   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   in das ursprüngliche Chiffrat   ü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   gegeben. Der beschriebene Angriff muss jedoch nur   Chiffrate berechnen und ist damit signifikant schneller. Zusätzlich fällt ein erhöhter Speicherbedarf von   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  , 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   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

Bearbeiten

Bei der Triple-DES-Verschlüsselung wird das ursprüngliche DES-Verfahren dreimal hintereinander, jedoch mit unterschiedlichen Schlüsseln angewendet. Jede Nachricht   wird mit einem DES-Schlüssel   chiffriert, dann mit   dechiffriert und schließlich mit   chiffriert:

 

Da die Schlüssellänge von DES 56 Bit beträgt, hat der Triple-DES-Schlüsselraum   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   mal   aus und speichert die Ergebnisse zusammen mit dem verwendeten Teilschlüssel. Dann berechnet er   mal   und vergleicht das   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   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

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