AES/Angriffe

Biclique-Angriff

Auf der Rump-Session der Konferenz CRYPTO im August 2011 stellten die Kryptologen Andrey Bogdanov, Dmitry Khovratovich und Christian Rechberger den ersten Angriff auf den vollen AES-Algorithmus vor. Dieser Angriff ist bei den verschiedenen Schlüssellängen im Schnitt etwa um den Faktor 4 schneller als ein vollständiges Durchsuchen des Schlüsselraumes.

• Damit zeigt er die prinzipielle Angreifbarkeit von AES, ist aber für die praktische Sicherheit nicht relevant.
• Der Angriff berechnet den geheimen Schlüssel von AES-128 in 2^126,1 Schritten.
• Bei AES-192 werden 2^189,7 Schritte, bei AES-256 2^254,4 Schritte benötigt.

XSL-Angriff

2002 wurde von Courtois und Pieprzyk ein theoretischer Angriff namens XSL (für eXtended Sparse Linearization) gegen Serpent und Rijndael vorgestellt (siehe Serpent).

• Mit dem XSL-Angriff ist nach Angabe der Autoren eine Komplexität im Bereich von $2^{100}$ Operationen erreichbar.
• XSL ist die Weiterentwicklung einer heuristischen Technik namens XL (für eXtended Linearization), mit der es manchmal gelingt, große nichtlineare Gleichungssysteme effizient zu lösen.
• XL wurde ursprünglich zur Analyse von Public-Key-Verfahren entwickelt.
• Der Einsatz im Kontext von symmetrischen Kryptosystemen ist eine Innovation von Courtois und Pieprzyk.
• Grob kann die Technik und ihre Anwendung auf symmetrische Kryptosysteme wie folgt beschrieben werden:

Die Blockchiffre wird als überspezifiziertes System quadratischer Gleichungen in GF(2) beschrieben. Überspezifiziert bedeutet, dass es mehr Gleichungen als Variablen gibt.

• Variablen und Konstanten können nur die Werte 0 und 1 annehmen.
• Die Addition entspricht dem logischen eXklusiv-OdeR (XOR), die Multiplikation dem logischen UND.
• Eine solche Gleichung könnte wie folgt aussehen:

$x_{1}+x_{2}\cdot x_{3}+x_{2}\cdot x_{4}\equiv 1\mod 2$

Diese Gleichung besteht aus einem linearen Term (der Variablen $x_{1}$), zwei quadratischen Termen ($x_{2}\cdot x_{3}$ und $x_{2}\cdot x_{4}$) und einem konstanten Term ($1$).

Einige Wissenschaftler zweifeln die Korrektheit der Abschätzungen von Courtois und Pieprzyk an:

Diese Art von System kann typischerweise sehr groß werden, im Falle der 128-Bit-AES-Variante wächst es auf 8000 quadratische Gleichungen mit 1600 Variablen an, womit der XSL-Angriff in der Praxis nicht anwendbar ist. Das Lösen von Systemen quadratischer Gleichungen ist ein NP-schweres Problem mit verschiedenen Anwendungsfeldern in der Kryptographie.

Weitere Angriffe

Kurz vor der Bekanntgabe des AES-Wettbewerbs stellten verschiedene Autoren eine einfache algebraische Darstellung von AES als Kettenbruch vor.

• Dies könnte für erfolgreiche Angriffe genutzt werden.
• Hierzu gibt es einen Videovortrag von Niels Ferguson auf der HAL 2001.

Im Jahr 2003 entdeckten Sean Murphy und Matt Robshaw eine alternative Beschreibung des AES, indem sie diesen in eine Blockchiffre namens BES einbetteten, welche anstatt auf Datenbits auf Datenblöcken von 128 Bytes arbeitet.

• Die Anwendung des XSL-Algorithmus auf BES reduziert dessen Komplexität auf 2¹⁰⁰, wenn die Kryptoanalyse von Courtois und Pieprzyk korrekt ist.

Im Mai 2005 veröffentlichte [[Daniel J.

• Bernstein|Daniel Bernstein]] einen Artikel über eine unerwartet einfache Timing-Attacke (eine Art der Seitenkanalattacke) auf den Advanced Encryption Standard.

Die Forscher Alex Biryukov und Dmitry Khovratovich veröffentlichten Mitte des Jahres 2009 einen Angriff mit verwandtem Schlüssel auf die AES-Varianten mit 192 und 256 Bit Schlüssellänge.

• Dabei nutzten sie Schwächen in der Schlüsselexpansion aus und konnten eine Komplexität von 2¹¹⁹ erreichen.
• Damit ist die AES-Variante mit 256 Bit Schlüssellänge formal schwächer als die Variante mit 128 Bit Schlüssellänge. Ende 2009 wurde mit einer Verbesserung des Angriffs eine Komplexität von nur noch 2^99,5 erreicht. Für die Praxis hat dieser Angriff jedoch wenig Relevanz, denn AES bleibt weiterhin praktisch berechnungssicher.

Im März 2012 wurde bekannt, dass die NSA in ihrem neuen Utah Data Center neben dem Speichern großer Teile der gesamten Internetkommunikation auch mit enormen Rechenressourcen am Brechen von AES arbeitet. Die Eröffnung des Rechenzentrums läuft schrittweise seit September 2013.

Craig Ramsay & Jasper Lohuis, als Forscherteam der beiden Unternehmen Fox-IT und Riscure, beschreiben 2017 einen Angriff, bei dem sie die von der CPU abgestrahlten Funksignale zur Entschlüsselung verwenden.

• Damit ließe sich der AES-Schlüssel in maximal fünf Minuten ermitteln, wenn Sniffer und angegriffene CPU etwa 1 Meter entfernt voneinander stehen.
• Bei 30 Zentimeter Distanz schrumpfe die Zeit auf etwa 50 Sekunden. Man muss aber beachten, dass dies ein Angriff auf eine einzelne Implementierung des Algorithmus auf einer bestimmten CPU ist, nicht auf den Algorithmus an sich.
• Ein solcher Angriff ist nur unter sehr speziellen Bedingungen durchführbar und kann nicht unbedingt verallgemeinert werden.