www.wikidata.de-de.nina.az

Meet in the middle Angriff Ein ist ein generischer kryptographischer Angriff Er macht sich zu Nutze dass anfällige krypt

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 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. 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Meet in the middle Angriff ist ein generischer kryptographischer Angriff Er macht sich zu Nutze dass anfallige kryptographische Algorithmen ihren Schlussel zerteilen und wahrend der Berechnung des Chiffrats in einzelnen Schritten nur einen Teil des Schlussels verwenden Ein gangiges Beispiel dafur sind Verschlusselungsverfahren die ihren eigentlichen Verschlusselungsalgorithmus mehrfach mit jeweils unterschiedlichen Schlusseln anwenden Verfahren BearbeitenIn einem kryptographischen Verfahren das nicht anfallig fur diese Art von Angriffen ist wird ein Klartext und ein Schlussel als Eingabe fur 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 Schlussel nur errechnen indem er mit der Brute Force Methode alle moglichen Schlussel ausprobiert und das Ergebnis mit dem Chiffrat vergleicht Teilt nun aber der Algorithmus den Schlussel auf und berechnet einzelne Zwischenergebnisse mit jeweils einem Schlusselteil ohne von den ubrigen Schlusselteilen Gebrauch zu machen so kann ein Angreifer die Teile des Schlussels 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 ruckwarts 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 K n displaystyle K K 1 K 2 cdots K n nbsp gegeben und ohne Beschrankung der Allgemeinheit n displaystyle n nbsp gerade und K 1 K 2 K n displaystyle K 1 K 2 dots K n nbsp Dazu sei ein Verschlusselungsverfahren gegeben durch Enc K Enc K n Enc K n 1 Enc K 1 displaystyle operatorname Enc K operatorname Enc K n circ operatorname Enc K n 1 circ cdots circ operatorname Enc K 1 nbsp Dann kann der Angreifer fur alle K 1 displaystyle K 1 nbsp mit der Klartextnachricht M displaystyle M nbsp das erste Chiffrat C 1 Enc K 1 M displaystyle C 1 operatorname Enc K 1 M nbsp berechnen Gleichzeitig berechnet er fur alle K n displaystyle K n nbsp mit dem Chiffrat C displaystyle C nbsp das Ergebnis des letzten Zwischenschrittes durch C n 1 Enc K n 1 C displaystyle C n 1 operatorname Enc K n 1 C nbsp Aus den jeweils berechneten Zwischenergebnissen berechnet der Angreifer nun solange jeweils die nachsten Zwischenschritte bis er von beiden Seiten aus beim selben Zwischenschritt angekommen ist Diese Chiffrate die er nun fur alle K 1 K 2 K n 2 displaystyle K 1 K 2 cdots K n 2 nbsp und fur alle K n 2 1 K n 2 2 K n displaystyle K frac n 2 1 K frac n 2 2 cdots K n nbsp berechnet hat muss der Angreifer nun temporar zusammen mit dem jeweiligen Schlusselteil abspeichern Dies erfordert 2 2 K 2 displaystyle 2 cdot 2 frac K 2 nbsp Speicheraufwand da fur beide Mengen an Chiffraten nur jeweils i 1 N 2 K i displaystyle prod i 1 frac N 2 K i nbsp Moglichkeiten zur Schlusselwahl bestehen In diesen beiden Mengen gibt es genau ein Paar aus Chiffraten die ubereinstimmen Dieses ist das Chiffrat welches durch die Teilschlussel erzeugt wurde welche zusammengenommen die ursprungliche Nachricht M displaystyle M nbsp in das ursprungliche Chiffrat C displaystyle C nbsp uberfuhrt haben Der gesuchte geheime Schlussel ist demnach zusammengesetzt aus den Teilschlusseln die mit dem gefundenen Zwischenergebnis abgespeichert wurden Die Komplexitat eines herkommlichen Brute Force Angriffs ist durch 2 K displaystyle 2 K nbsp gegeben Der beschriebene Angriff muss jedoch nur 2 2 K 2 displaystyle 2 cdot 2 frac K 2 nbsp Chiffrate berechnen und ist damit signifikant schneller Zusatzlich fallt ein erhohter Speicherbedarf von 2 2 K 2 displaystyle 2 cdot 2 frac K 2 nbsp gegenuber der Brute Force Methode an Man spricht deshalb von einem Time Memory Tradeoff Verzichtet der Angreifer auf die Parallelisierung des Verfahrens genugt sogar ein Speicheraufwand von 2 K 2 displaystyle 2 frac K 2 nbsp da die zweite Chiffratmenge schon wahrend 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 displaystyle n nbsp gerade ist und die Teilschlussel gleich gross sind Ist dies nicht der Fall kann nur eine annahernd optimale Reduzierung des Rechen und Speicheraufwandes erreicht werden Triple DES Beispiel BearbeitenBei der Triple DES Verschlusselung wird das ursprungliche DES Verfahren dreimal hintereinander jedoch mit unterschiedlichen Schlusseln angewendet Jede Nachricht M displaystyle M nbsp wird mit einem DES Schlussel K 1 displaystyle K 1 nbsp chiffriert dann mit K 2 displaystyle K 2 nbsp dechiffriert und schliesslich mit K 3 displaystyle K 3 nbsp chiffriert 3DES K 1 K 2 K 3 DES K 3 DES K 2 1 DES K 1 displaystyle operatorname 3DES K 1 K 2 K 3 operatorname DES K 3 circ operatorname DES K 2 1 circ operatorname DES K 1 nbsp Da die Schlussellange von DES 56 Bit betragt hat der Triple DES Schlusselraum 2 56 2 56 2 56 2 168 displaystyle 2 56 cdot 2 56 cdot 2 56 2 168 nbsp Elemente Durch den Meet in the middle Angriff konnen nun aber zwei Schritte des Verfahrens einzeln angegriffen werden und dann mit dem dritten Schritt der ruckwarts ausgefuhrt wird verglichen werden Ein Angreifer fuhrt zunachst 2 56 displaystyle 2 56 nbsp mal DES K 3 1 C displaystyle operatorname DES K 3 1 C nbsp aus und speichert die Ergebnisse zusammen mit dem verwendeten Teilschlussel Dann berechnet er 2 112 displaystyle 2 112 nbsp mal Z DES K 2 1 DES K 1 M displaystyle Z operatorname DES K 2 1 circ operatorname DES K 1 M nbsp und vergleicht das Z displaystyle Z nbsp jeweils mit der gespeicherten Chiffratmenge Sobald er eine Ubereinstimmung gefunden hat kann er den Schlussel zusammensetzen Der Gesamtaufwand fur das Finden des Schlussels ist damit auf 2 56 2 56 2 56 2 112 displaystyle 2 56 cdot 2 56 2 56 approx 2 112 nbsp 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 gegenuber DES beim Berechnen des Schlussels bedeutet Einzelnachweise Bearbeiten Manfred Lipp VPN virtuelle private Netzwerke Pearson Deutschland GmbH 2006 ISBN 978 3 8273 2252 4 S 125 Abgerufen von https de wikipedia org w index php title Meet in the middle Angriff amp oldid 229257805