Kryptologie Die AES-Auswahl

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Der AES-Wettbewerb

... wird ausführlich dokumentiert auf den Web-Seiten des NIST: http://csrc.nist.gov/CryptoToolkit/aes/

Gesucht war eine neue »Standard«-Bitblock-Chiffre als Nachfolge des DES.

Anforderungen:

• Bitblock-Chiffre mit Blockgröße 128 Bit.
• Drei unterstützte Schlüssellängen: 128, 192, 256 Bit. -- 256 Bit sind auch dann noch sicher, wenn Quantenrechner jemals Einsatzreife erlangen sollten.
  [Ein Problem, das auf einem herkömmlichen Rechner (von-Neumann-Architektur) die Komplexität n hat, hat auf einem Quantenrechner i. a. die Komplexität n^1/2.]
• Leicht implementierbar mit geringem Ressourcenverbrauch und hoher Effizienz in allen denkbaren Hardware- und Software-Umgebungen, auch z. B. auf Chipkarten, FPGAs (Field Programmable Gate Arrays) und ASICs (Application Specific Integrated Circuits).
• Resistenz gegen alle bekannten kryptoanalytischen Methoden, auch gegen »Side-Channel-Attacken« wie Stromverbrauchs- (Power) und Zeitbedarfs- (Timing) Attacken.
• Freiheit von jedweden patentrechtlichen Ansprüchen, freie und kostenlose Nutzung für jeden.

Bemerkenswert:

• Unbestrittenes Sicherheitsniveau nach dem Stand der (offenen) kryptologischen Forschung.
• Freie Verfügbarkeit weltweit vorgesehen.
• Freeware als Bedingung.
• Weltweite öffentliche Diskussion.

Zeitlicher Ablauf:

• 1996 Ankündigung durch NIST (National Institute of Standards and Technology).
• 1997 Ausschreibung.
• 1998 Zulassung von 15 Kandidaten - darunter 10 Nicht-US-Bewerbungen.
• 1999 Auswahl von 5 Kandidaten (»Endrunde«).
• Bis Mai 2000: Öffentlich zur Diskussion gestellt.
• Entscheidung am 2. Oktober 2000: Der Sieger heißt Rijndael.
• Ende 2001: Bestätigung als FIPS (Federal Information Processing Standard).

Die fünfzehn AES-Kandidaten der ersten Runde

1. LOKI97 (Pieprzyk/Seberry/Brown, Australien) - [Nachfolge von LOKI]
   - schwach bei Angriff mit gewähltem Klartext.
2. Rijndael (Daemen/Rijmen, Belgien)
   - Finalist.
3. CAST-256 (Adams/Heys/Tavares/Wiener, Entrust Technologies Inc., Kanada) [Nachfolge von CAST]
   - hatte zu hohen ROM-Bedarf für Chipkarten.
4. DEAL (Outerbridge/Knudsen, Kanada/Norwegen) [Weiterentwicklung von DES]
   - war zu langsam.
5. FROG (Georgoudis u. a., TecApro Int. S. A., Costa Rica)
   - war zu verwundbar bei linearer und Differential-Kryptoanalyse.
6. DFC (Vaudenay u. a., CNRS-ENS, Frankreich)
   - leichte Schwächen und etwas langsam.
7. Magenta (Telekom AG, Deutschland)
   - hatte schwaches Rundenschlüssel-Auswahlschema.
8. E2 (Kanda u. a., NTT, Japan)
   - hatte zu hohen RAM-Bedarf für Chipkarten.
9. CRYPTON (Lim, Future Systems Inc., Korea)
   - war etwas langsam und hatte Schwächen beim Rundenschlüssel-Auswahlschema.
10. HPC = Hasty Pudding Cipher (Schroeppel, USA)
    - hatte zu viele schwache Schlüssel.
11. MARS (IBM, USA)
    - Finalist.
12. RC6 = Ron's Cipher 6 (Rivest/Kaliski u. a., RSA Security Inc., USA); Nachfolger von RC5
    - Finalist.
13. SAFER+ (Massey u. a., Cylink Corp., USA) [Nachfolge von SAFER]
    - war etwas zu langsam.
14. Twofish (Schneier u. a., Counterpane Systems, USA); Nachfolger von Blowfish
    - Finalist.
15. Serpent (Anderson/Biham/Knudsen, UK, Israel, Norwegen)
    - Finalist.

Die fünf AES-Kandidaten der letzten Runde

1. MARS; unbalancierte FEISTEL-Chiffre mit 32 Runden.
   • Sehr langsam in Hardware, für billige Chipkarten nicht geeignet. Bedingt schnell in Software (abhängig von CPU-Unterstützung).
2. RC6; FEISTEL-Chiffre mit 20 Runden, datenabhängige Rotationen in den Runden.
   • Langsam in Hardware, für billige Chipkarten nicht geeignet. Bedingt schnell in Software (abhängig von CPU-Unterstützung).
3. Rijndael; iterierte Chiffre mit 10 Runden, algebraische Konstruktion über F₂₅₆.
   • Schnell in Hardware. Schnell in Software. Besondere Einfachheit und Eleganz im Design.
4. Serpent; iterierte Chiffre mit 32 Runden.
   • Schnell in Hardware. Langsam in Software. Besonders konservativ im Sicherheits-Design.
5. Twofish; FEISTEL-Chiffre mit 16 Runden, schlüsselabhängige S-Boxen.
   • Angemessen schnell in Hardware. Schnell in Software.

Die Sieger

Rijndael wurde von zwei jungen belgischen Kryptologen entwickelt: Joan Daemen (geb. 1965) und Vincent Rijmen (geb. 1970) [Bild, J. D. links, V.R. rechts].

Zur Aussprache: Die beiden Namen sind flämisch - das ist der in Belgien gesprochene niederländiche Dialekt. Das »e« in Daemen ist ein Dehnungs-e, wie es auch in manchen deutschen Ortsnamen verwendet wird (Soest); im zeitgenössischen Deutsch entspricht ihm das Dehnungs-h. Aussprache also: »Dahmen«. Das »ij« in Rijmen ist der Diphthong, der dem deutschen »ei« entspricht und auch so ähnlich gesprochen wird. Aussprache also: »Reimen«. Die beiden Erfinder wählten den Namen Rijndael für ihren Algorithmus - der also wie »Reindahl« ausgesprochen wird - nach eigener Aussage in dem Bewusstsein, dass er für Amerikaner optimal schwierig ist. Das Problem hat sich allerdings durch die Bezeichnung »AES« weitgehend erledigt.

Schwächen des AES?

Seit Verabschiedung des Standards wird natürlich weiter nach Schwächen des Algorithmus geforscht. Bisher sind keine entscheidenden gefunden worden. Am weitesten kamen die folgenden Ansätze, die immerhin zu denken geben:

• Eine strukturell einfache geschlossene Formel für den gesamten Rijndael-Algorithmus in Form einer Art von Kettenbruch-Darstellung:
  • Niels FERGUSON, Richard SCHROEPPEL, Doug WHITING: A simple algebraic representation of Rijndael. SAC 2001, 103 - 111.
  Es gibt aber nicht einmal vereinfachte Demonstrationsbeispiele, in denen eine solche Formel zu einer erfolgversprechenden algebraischen Kryptoanalyse führt. Aus den Erfahrungen in der Algebraischen Geometrie weiss man, dass strukturell einfache Gleichungen meistens trotzdem eine sehr hohe Komplexität haben und nicht effizient zu lösen sind.
• Eine Reduktion des algebraischen Angriffs auf ein System von multivariaten quadratischen Gleichungen, das überbestimmt und außerdem sehr dünn besetzt ist:
  • Sean MURPHY, Matthew J. B. ROBSHAW: Essential algebraic structure within the AES. CRYPTO 2002, 1 - 16.
  Auch hier liefert die Algebraische Geometrie eigentlich wenig Hoffnung, dass ein solches System effizient lösbar ist.
• Ein Ansatz zur Lösung überdefinierter multivariater Polynomgleichungssysteme durch »Relinearisierung«, der in manchen Beispielen in einer »XL« genannten Version effizient zu einer Lösung führt.
  • Nicolas COURTOIS, Alexander KLIMOV, Jacques PATARIN, Adi SHAMIR: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. EUROCRYPT 2000, 392 - 407.
  Daraus leiteten COURTOIS und PIEPRZYK einen algebraischer Angriff auf Rijndael und Serpent her, der etwas schneller als die Exhaustion sein sollte.
  • Nicolas COURTOIS, Josef PIEPRZYK: Cryptanalysis of block ciphers with overdefined systems of equations. ASIACRYPT 2002. Preprint auf dem IACR-E-Print-Server.
  Allerdings verzählten sich die Autoren wohl bei der Anzahl der linear unabhängigen Gleichungen, so dass diese nicht ausreichen, um eine Lösung zu erhalten. Immerhin deutet die Methode darauf hin, dass die Komplexität der Chiffren nicht exponentiell von der Rundenzahl abhängt, wie bisher angenommen. Eine interessante Analyse der Situation mit algebraisch-geometrischen Methoden gibt T. MOH in
  • T. MOH: On the Courtois-Pieprzyk's attack on Rijndael. Online.
• Eine affine Äquivalenz in den Koordinatenfunktionen der S-Box von Rijndael, die zuvor unbemerkt geblieben war, allerdings bisher noch zu keinem brauchbaren Angriffsplan geführt hat. Sie wurde von Joanne FULLER und William MILLAN entdeckt:
  • Joanne FULLER, William MILLAN: On Linear Redundancy in the AES S-Box. Preprint 2002, online auf dem IACR-E-Print-Server.
• 2005 beobachtete D. Bernstein, dass das AES-Verfahren für "Timing-Attacken" anfällig ist, bei denen eine Blackbox, die das Verfahren implementiert hat, bei verschiedenen Probeverschlüsselungen beobachtet wird. Aus dem Zeitbedarf werden statistische Aussagen über die Schlüsselbits hergeleitet. AES ist zwar, wie jeder andere Algorithmus auch, gegen diesen Angriff immunisierbar, indem man darauf achtet, dass die Zeitdauer von kritischen Operationen von den konkreten Schlüsselbits unabhängig ist; diese Härtung ist aber gerade für AES sehr aufwendig und beraubt die Chiffre ihrer, für den Sieg bei der AES-Auswahl mitentscheidenden Performanz. Quelle: Cache-timing attacks on AES.