AES under Attack

Neue mathematische Methoden  lassen Zweifel wachsen

Rüdiger Weis, Stefan Lucks

Gross war seit Oktober 2000 die Freude endlich über ein standardisiertes und sichereres Verschlüsselungsverfahren zu verfügen.
Der neue Chipher Rijndael ist schnell und elegant - vielleicht etwa zu schnell und sehr wahrscheinlicher Weise viel zu elegant.
Neue Angriffsmethoden lassen jedenfalls, obgleich noch  entfernt von einer praktischen Durchführbarkeit, bei vielen Kryptographen recht ungute Gefühle entstehen.

Der AES („Advanced Encryption Standard“) ist der Nachfolger des inzwischen wegen der zu geringen Schlüsslelänge völlig unsicheren DES („Data Encryption Standard“). Die Wahl des AES ist das Ergebnis eines mehrjährigen, mit großer Sorgfalt vom US-amerikanischen NIST („National Institute of Standards and Technology“) betriebenen Prozesses [WL99].

Auf der ersten AES-Konferenz 1998 wurden 15 Kandidaten präsentiert. Die Submission der Deutschen Telekom mit dem schönen Namen Magenta wurde übrigens schon während des Vorstellungsvortages gebrochen.

Nach der zweiten Konferenz wurden vom NIST fünf Finalisten ausgewählt.

Von diesen Kandidaten wurden Mars, Serpend und Twofish von der NSA hohe Sicherheit und Rijndael und RC6 angemessene. Gegen Mars und RC6 gab es von verschiedener Seite Bedenken wegen möglicher Patentbegehrlichkeiten.

Nach der dritten AES-Konferenz im Jahr 2000 mit einer eingehende Diskussion der fünf Finalisten entschied sich das NIST für „Rijndael“ als vorläufiger Standard, der Ende November 2001 als endgültiger Standard bestätigt wurde.

Rijndael

Rijndael wurde von den beiden Belgiern Joan Daemen und Vincent Rijmen entwickelt. Ein Vorläufer ist SQUARE, ebenfalls von den beiden Autoren zusammen mit Lars Knuden entworfen [DKR97]. Rijndael verwendet eine umkehrbare 8x8 bit S-Box und nutzt Berechnungen mit Polynomen über den Körper GF[28], um gute Diffusions­eigenschaften sicherzustellen. Die Berechnungen erinnern an fehlererkennende bzw.  korrigierende Codes (MDS-Codes). Rijndael überzeugte nicht nur durch Effizienz, sondern auch durch seine mathematisch elegante und einfache Struktur.
Manche Kryptographen warnten allerdings auch davor, dass gerade diese einfache Struktur ein Einfallstor für Angreifer sein könnte. Und es gab noch weitere kritische Stimmen.

Geringe Sicherheitsmargen

Vielen Kryptographen erschien insbesondere die Rijndael-Variante für 128-bit Schlüssel mit nur 10 Runden und recht einfacher Rundenfunktion als „recht nahe am Limit“. So verwendet der Konkurrent Serpend 32 Runden..

Einfache S-Boxen

Als weiterer Kritikpunkt galt die einfache algebraische Beschreibung der S-Boxen, die ihrerseits die einzige nichtlineare Komponente der Chiffre sind. Dieser Punkt ist im Zusammenhang mit den aktuellen Ergebnissen besonders wichtig. Die S-Boxen sind sogenannte „Knudsen-Nyberg“ S-Boxen, die optimalen Schutz gegen differentielle und lineare Kryptanalyse bieten. Diese beiden Techniken waren in der Vergangenheit die wichtigsten und erfolgreichsten Methoden für die Kryptanalyse von Blockchiffren.

Einfacher Key Schedule

Rijndael verwendet einen sehr einfachen Key Schedule. Kryptographisch unschön ist insbesondere die Eigenschaft, dass sich aus Kenntnis irgend eines Rundenschlüssels trivial 128 bit des Verfahrensschlüssel ge­winnen lassen. Auch die einfache mathematische Darstellung konnte bei den unten diskutierten Angriffen verwendet werden. Lucks [Lu00] nutzte eine weitere Schwäche für einen erfolgreichen Angriff gegen Rijndael mit reduzierter Rundenzahl.

Mathematische Struktur

Seitdem suchten und suchen Kryptanalytiker weiter intensiv nach neuen Techniken, die Einfachheit von AES für eine verbesserte Analyse bzw. für einen Angriff auszunutzen.

2001 gelang es Ferguson, Schroeppel Whiting [FSW01], die gesamte Chiffre als überraschend einfache geschlossene mathematische Formel darzustellen – in Form einer Art Kettenbruch. Entscheidend dabei war die oben erwähnte einfache algebraische Darstellbarkeit der S-Boxen. Fuller und Millian [FM02] sowie Murphy und Robshaw [MR02] veröffentlichten 2002 weitere interessante Ergebnisse.

Das wohl spektakulärste der neuen Resultate ist jedoch der „eXtended Sparse Linearization“ (XSL-Angriff von Courtois und Pieprzyk [CP02], der im folgenden Abschnitt ausführlicher dargestellt wird.

Der XSL-Angriff

Der XSL-Angriff Für den Kryptographen zählt jedes Verfahren, das eine Chiffre schneller als mit erschöpfender Schlüsselsuche bricht, als „Angriff“, unabhängig von der Praktikabilität. Denn auch ein unpraktikabler „Angriff“ gilt als Nachweis, dass die Chiffre ihr angestrebtes Sicher­heitsziel verfehlt hat. Im Fall der AES-Variante mit maxi­maler Schlüssellänge (256 bit) braucht die erschöpfende Schlüsselsuche im Durch­schnitt 2255 Verschlüsselungs­opera­tionen. Dies ist der Wert, den es mit einem kryptoanalytischen Angriff zu unterbieten gilt. Als aktuell gerade noch praktikabel (für einen finanziell hervorragend ausgestatteten Angreifer, z. B. einen Geheimdienst) gelten 275bis 290Verschlüsselungsoperationen. Der XSL-Angriff liegt nach Angabe der Autoren im Bereich von 2200 Operationen und ist damit definitiv nicht praktikabel. XSL ist eine Weiterentwicklung von XL („eXtended Linearization“), einer heuristischen Technik, mit der es manchmal gelingt ist, große nichtlineare Gleichungssysteme effizient zu lösen. XL wurde ursprünglich zur Analyse von Public-Key Kryptosystemen entwickelt. Der Einsatz im Kontext der Secret-Key Kryptographie ist eine Innovation von Courtois und Pieprzyk.

Grob kann die Technik und ihre Anwendung auf Secret-Key Kryptosysteme wie folgt beschrieben werden:

Beschreibe die Chiffre als überspezifiziertes System quadratischer Gleichungen in GF(2); d. h. 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. Mit „überspezifiziert“ ist gemeint, dass es mehr Gleichungen als Variablen gibt. Eine derartige Gleichung kann z. B. so aussehen:

x1 + x2x3 + x2 x4 = 1 (mod 2).

Diese Gleichung besteht aus einem konstanten Term („1“), einem linearen Term (der Variablen „x1“) und zwei quadratischen Termen („x2 x3“ und „x2 x4“).

Theoretisch können dabei Lösungen gefunden werden, denen keine Lösung des ursprünglichen Gleichungssystems entspricht, z. B. x2 = x3 = 0 und x[2,3]= 1. Eine solche (Schein-) Lösung wäre für den Angreifer irrelevant. Aber die Wahrscheinlichkeit, dass dieser Fall eintritt, ist dank der Überspezifiziertheit des linearen Gleichungssystem gering.

Für die meisten Blockchiffren ist dieser Angriff unbrauchbar, da das Glei­chungssystem, das man im ersten Schritt erhält, riesig wird. Besäße z. B. der AES statt definierter S-Boxen gänzlich zufällige, wäre dieses Gleichungssystem so groß und komplex, dass die XSL-Methode nicht zu einem brauchbaren Angriff führen würde. Die spezielle Wahl der AES S-Boxen erlaubt es jedoch, ein System mit „nur“ 8.000 quadratischen Gleichungen und sogar „nur“ 1.600 Variablen anzugeben. Das Gleichungssystem ist dazu noch dünn besetzt („sparse“), das heisst von den insgesamt etwa 1.280.000 möglichen quadratischen Termen tauchen nur relativ wenige überhaupt im Gleichungssystem auf.

Für Kryptographen ist es bemerkenswert, dass eine Erhöhung der Rundenzahl keine exponentielle Steigerung der für den XSL-Angriff erforderlichen Rechenzeit mit sich bringt.

Außer Rijndael scheint auch ein zweiter AES-Finalist verwundbar gegen dieses Angriffstechnik zu sein, nämlich „Serpent“ – was die Autoren von Serpent allerdings bezweifeln [SeHo].

Das generelle Problem mit diesem Angriff besteht darin, dass man bisher nicht angeben kann, unter welchen Umständen er zum Erfolg führt. Courtois und Pieprzyk geben in ihrer Arbeit einige notwendige Bedingungen dafür an [CP02]: Unter anderem darf das im zweiten Schritt erzeugte nichtlineare Gleichungssystem nicht zu viele lineare Abhängigkeiten enthalten. Leider ist nicht klar, ob die bekannten notwendigen Bedingungen auch hinreichend sind; darauf weisen auch Courtois und Pieprzyk hin.

Es gibt auch begründete Zweifel, ob der geschilderte Angriff auf den AES tatsächlich funktioniert. Der wohl prominenteste Zweifler ist Don Coppersmith, einer der Autoren des DES [C02]. Weil der Angriff mit einem Aufwand von 2200Operationennicht praktikabel ist, kann man ihn auch schwerlich experimentell verifizieren.

Was nun?

Die Arbeit von Courtois und Pieprzyk ist ohne Zweifel hoch interessant aus theoretischer Sicht. Die spezifische Bedeutung der Frage, ob der XSL-Angriff nun funktioniert oder nicht, und wie aufwändig der Angriff tatsächlich ist, wenn er denn funktioniert, sollte jedoch aus praktischer Sicht nicht überschätzt werden:
Der Angriff (Komplexität >=2200) ist im Moment weit davon entfernt, praktikabel zu sein.

Insgesamt sollte man trotzdem beim Einsatz des AES bis auf weiteres eher zurückhaltend sein, unabhängig davon, ob der XSL-Angriff funktioniert oder nicht. Es ist klar, dass Courtois, Pieprzyk und andere Autoren bestimmte Schwächen des AES aufgedeckt haben. Dieses Warnsignal sollte nicht ignoriert werden. 

Für Hochsicherheitsanwendungen raten viele Kryptographen, für den Fall, dass bereits Triple-DES verwendet wird und es sich keine Probleme aus der Blockgrösse von 64 Bit ergeben,  noch einige Jahre mit der Migration zu warten und sich über den aktuellen Forschungsstand (z. B.  [W02]) auf dem Laufenden zu halten.

Alternativen

Die Uralt-Chiffre Three-Key Triple-DES bietet für die kommenden Jahre eine Alternative, bei der das Risiko unliebsamer Überraschungen geringer ist.
 Der beste bekannte Angriff aus Three-Key Triple DES erfordert eine Rechenzeit von etwa 2108Verschlüsselungsoperationen [Lu98]. Wenn die Entwicklung der Computer­hardware so voranschreitet, wie sie das in den letzten 30 Jahren getan hat („Moore's Law“), wird ein Angriff auf Three-Key Triple-DES erst in einigen Jahrzehnten praktikabel sein.

Obwohl die Einschätzung über die wirkliche Sicherheit von Triple-DES selbst unter den Autoren leicht unterschiedlich ist, sprechen noch zwei ganz  pragmatische Gründe für Triple-DES: "Nobody will be fired for using Triple-DES" und "Wenn Triple-DES gebrochen wird, dann haben wir ganz andere Probleme". 

Leider ist eine Blockgröße von 64 bit, wie DES und Triple-DES sie bieten, oftmals problematisch. Der Einsatz einer 64-bit Blockchiffre erfordert besondere Sorgfalt seitens des Anwendungsdesigners. Bei 64-bit Blöcken können sich signifikante Sicherheits­probleme ergeben, wenn etwa 232 Blöcke, was gerade mal 32 GB entspricht, unter dem selben Schlüssel verarbeitet werden (matching ciphertext Angriffe im CBC-Modus, Probleme bei der Verwendung DES-basierter MACs etc.).

Als DES-basierte und Triple-DES ähnliche 128-Blockchiffre mit 128-bit Blöcken gibt es DEAL [Kn98]. DEAL verwendet den DES als Rundenfunktion und setzt auf die Feistel-Struktur, d. h. auf seit langem bekannte, gut untersuchte und bewährte Komponenten. DEAL bietet nicht die Sicherheit, die vom AES erwartet wurde und erhofft wird, und gelangte deshalb mit Recht als AES-Kandidat nicht in den Kreis der Finalisten [Lu99].

Auch die von den Autoren dieses Beitrags entwickelte DEAL-Variante mit einem verbesserten Key Schedule [LW00] hätte beim AES-Wettbewerb, insbesondere wegen der im Vergleich zu den anderen Kandidaten geringeren Geschwindigkeit, sicherlich keine Chance gehabt. Doch das Riskio eines großen kryptanalytischen Durchbruchs ist bei DEAL vergleichsweise geringer als bei einer noch jungen Chiffre.

Abschliessend sei noch mal auf Twofish hingewiesen.  Viele Kryptographen halten diesen mit für den sichersten Cipher im Wettbewerb. Zudem war bei der Entwicklung von Twofish Dr. David Wagner, inzwischen Prof in Berkeley, massgeblich beteiligt - Ältere kennen ihn noch als Netscape-Hacker!-)

Literatur