[Chaos CD][Datenschleuder] [80]
  [Chaos CD]
  [Datenschleuder] [80] AES und Attack
[ -- ] [ ++ ] [Suchen]  

 

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:

  • 128-bit breite Blockchiffre.
  • Drei verschieden Schlüssellängen 128 bit, 192 bit und 256 bit.
  • AES soll mindestens so schnell und sicher sein wie Triple-DES,
  • Im Gegensatz zum DES-Verfahren wurden diesmal die Design-Grundsätze veröffentlicht.
  • Die Entwickler mussten plausibel machen, dass ihre Algorithmen nicht mit geheimen Hintertüren versehen sind.

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.

  • Mars
  • RC6
  • Rijndael
  • Serpent
  • Twofish
Von diesen Kandidaten wurden Mars, Serpent und Twofish von der NSA hohe Sicherheit bescheinigt und Rijndael und RC6 nur 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. 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.

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 Serpent 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 Kryptoanalyse 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 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.

Mathematische Struktur

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

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:

  • Beschreibe die Chiffre als überspezifiziertes System quadratischer Gleichungen in GF(2). 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").
  • Erzeuge durch An-Multiplizieren zusätzliche Gleichungen, um ein noch mehr überspezifiziertes System zu erhalten. Aus der obigen Gleichung kann man durch Multiplizieren mit x1, x2, x3 und x4 die folgenden zusätzlichen Gleichungen erhalten: x1 + x1 x2 x3 + x1 x2 x4 = x1 (mod 2), x1 x2 + x2 x3 + x2 x4 = x2 (mod 2) x1 x3 + x2 x3 + x2 x3 x4 = x3 (mod 2), x1 x4 + x2 x3 x4 + x2 x4 = x4 (mod 2). Man beachte, dass jede erfüllende Variablenbelegung der ursprünglichen Gleichung auch eine erfüllende Belegung für jede der vier neuen Gleichungen ist. Die Umkehrung gilt nicht: So ist x1=x2=x3=x4=0 in unserem Beispiel eine erfüllende Belegung für alle vier zusätzlichen Gleichungen, aber keine für die ursprüngliche Gleichung.
  • Linearisiere durch Ersetzung jedes nicht-linearen Term durch eine (Hilfs-)Variable. Zum Beispiel kann man im obigen Beispiel jedes Auftreten des Terms x2 x3durch eine Variable x[2,3] ersetzen. Das Gleichungssystem muss so stark überspezifiziert sein, dass es selbst nach dem Linearisierungsschritt immer noch mehr Gleichungen gibt als Variablen, einschließlich der neu-geschaffenen Hilfsvariablen.
  • Das so erzeugte große überspezifizierte System von linearen Gleichungen kann man effizient lösen.
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 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.

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]. 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!-)

Literatur

  • [C02] Coppersmith, "Re: Impact of Courtois and Pieprzyk results", 19.09.2002
  • [CP02] Courtois, Pieprzyk, "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations" Asiacrypt 2002, http://eprint.iacr.org/2002/044/
  • [DKR97] Daemen, Knudsen, Rijmen, "The block cipher Square", Fast Software Encryption 1997.
  • [F+00] Ferguson, Kelsey, Lucks, Schneier, Stay, Wagner, Whiting, "Improved Cryptanalysis of Rijndael", Fast Software Encryption 2000.
  • [FM02] Fuller, Millian, "On Linear Redundancy in the AES S-Box", http://eprint.iacr.org/2002/111/
  • [FSW01] Ferguson, Schroeppel, Whiting, "A simple algebraic representation of Rijndael". Draft, 2001/05/16, http://www.macfergus.com/pub/rdalgeq.html
  • Lucks, Weis, "How to Make DES-Based Smartcards fit for the 21th Century", Cardis 2000.
  • [LW02] Lucks, Weis, "Neue Erkenntnisse zur Sicherheit des Verschlüsselungsstandards AES", DuD 12/2002.
  • [M02] Moh, "AES is NOT broken", http://www.usdsi.com/aes.html
  • [W99] Weis, "AES", Datenschleuder 66, http://ds.ccc.de/066/aes
  • [W02] Weis, Cryptolabs AES Page, http://cryptolabs.org/aes/
  • [WL99] Weis, Lucks, "Advanced Encryption Standard", DuD 10/1999.
  • [WL00] Weis, Lucks, "Die dritte AES Konferenz in New York", DuD 7/2000.
  • [SeHo] Serpent Homepage: http://www.cl.cam.ac.uk/~rja14/serpent.html

  [Chaos CD]
  [Datenschleuder] [80] AES und Attack
[ -- ] [ ++ ] [Suchen]