Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03587.jsonl.gz/3131

AES und Attack
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].
Zentrale Anforderungen waren dabei:
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.
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 wurde von den beiden Belgiern Joan Daemen und Vincent Rijmen entwickelt. Rijndael ist eine Weiterentwicklung des SQUARE Algorithmus, der 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 Diffusionseigenschaften sicherzustellen. Die Berechnungen erinnern an fehler- erkennende bzw. -korrigierende Codes (MDS-Codes). Rijndael ist im Gegensatz zu DES kein Feistel-Netzwerk.
Rijndael überzeugte nicht nur durch Effizienz, sondern auch durch seine mathematisch elegante und einfache Struktur. Manche Kryptographen warnten allerdings auch davor, daß gerade diese einfache Struktur ein Einfallstor für Angreifer sein könnte. Und es gab noch weitere kritische Stimmen.
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 Serpent 32 Runden.
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 Kryptoanalyse von Blockchiffren.
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 gewinnen lassen. Auch konnte die einfache mathematische Darstellung der Rundenschlüssel bei den unten diskutierten Angriffen verwendet werden. Lucks [Lu00] nutzte eine weitere Schwäche für einen erfolgreichen Angriff gegen Rijndael mit reduzierter Rundenzahl.
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.
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 Sicherheitsziel verfehlt hat. Im Fall der AES-Variante mit maximaler Schlüssellänge (256 bit) braucht die erschöpfende Schlüsselsuche im Durchschnitt 2255 Verschlüsselungsoperationen. Dies ist der Wert, den es mit einem kryptoanalytischen Angriff zu unterbieten gilt.
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:
Für die meisten Blockchiffren ist dieser Angriff unbrauchbar, da das Gleichungssystem, 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 [M02]. Der wohl prominenteste Zweifler ist Don Coppersmith, einer der Autoren des DES [C02]. Weil der Angriff mit einem Aufwand von 2200 Operationen nicht praktikabel ist, kann man ihn auch schwerlich experimentell verifizieren.
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.
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]. Obwohl die Einschätzung über die tatsächliche 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 Sicherheitsprobleme 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 an der Entwicklung von Twofish Dr. David Wagner, inzwischen Prof in Berkeley, massgeblich beteiligt - Ältere kennen ihn noch als Netscape-GSM-WEP-...-Hacker!-)