Advanced Encryption Standard

AES im Überblick

Der Advanced Encryption Standard (AES) ist eine symmetrische Blockchiffre: Zum Ver- und Entschlüsseln wird derselbe geheime Schlüssel verwendet. Er wurde im Oktober 2000 vom National Institute of Standards and Technology (NIST) als US-Standard und Nachfolger des Data Encryption Standard (DES) bekanntgegeben. Entwickelt wurde der zugrunde liegende Algorithmus Rijndael von Joan Daemen und Vincent Rijmen; veröffentlicht wurde er 1998.

AES verarbeitet stets Blöcke von 128 Bit und erlaubt Schlüssel mit 128, 192 oder 256 Bit. Entsprechend heißen die Varianten AES-128, AES-192 und AES-256. Sie verwenden 10, 12 beziehungsweise 14 Runden. Rijndael selbst kann unabhängig voneinander Block- und Schlüssellängen von 128, 160, 192, 224 oder 256 Bit besitzen. AES ist frei verfügbar, lizenzfrei sowie in Software und Hardware umsetzbar.

AES gilt als pragmatisch sicher: Es ist kein praktisch durchführbarer Angriff bekannt. Theoretische Angriffe können zwar weniger Aufwand als das vollständige Ausprobieren aller Schlüssel benötigen, verlangen aber weiterhin unrealistisch hohe Rechenleistung. AES-192 und AES-256 sind in den USA für staatliche Dokumente mit höchstem Geheimhaltungsgrad zugelassen.

Warum Rijndael ausgewählt wurde

DES war wegen seiner Schlüssellänge von 56 Bit spätestens seit den 1990er Jahren nicht mehr ausreichend gegen Brute-Force-Angriffe, also das systematische Durchprobieren möglicher Schlüssel. Das amerikanische Handelsministerium schrieb deshalb am 2. Januar 1997 international einen Nachfolger aus; das NIST leitete die Auswahl. Die endgültige Ausschreibung erschien am 12. September 1997.

Gefordert waren eine symmetrische Blockchiffre mit 128-Bit-Blöcken und Schlüsseln von 128, 192 und 256 Bit. Der Algorithmus sollte schnell und leicht in Hard- und Software umsetzbar, gegen bekannte Kryptoanalyse sowie Power- und Timing-Attacken widerstandsfähig, für Smartcards sparsam und frei von Patentansprüchen sein. Bewertet wurden vor allem Sicherheit, Kosten einschließlich Lizenzfreiheit, Effizienz, Speicherbedarf, Flexibilität und Einfachheit.

Von 15 Vorschlägen erreichten MARS, RC6, Rijndael, Serpent und Twofish die Endrunde. Im Mai 2000 waren Analysen und öffentliche Diskussionen abgeschlossen; am 2. Oktober 2000 wurde der belgische Algorithmus Rijndael zum Sieger erklärt. Ausschlaggebend waren seine Einfachheit – die Referenzimplementierung umfasst weniger als 500 Zeilen C-Code –, Sicherheit und überdurchschnittliche Geschwindigkeit in Hard- und Software. Der offene Auswahlprozess wurde international als vorbildlich angesehen.

Runden und Schlüssel

AES ist ein Substitutions-Permutations-Netzwerk. Ein Datenblock wird als Tabelle aus vier Zeilen und bei AES vier Spalten gespeichert; jede Zelle enthält ein Byte. Die Verschlüsselung ist iteriert: Der Block durchläuft mehrere nahezu gleich aufgebaute Runden. Für jede Runde wird durch Schlüsselexpansion ein eigener Rundenschlüssel aus dem Benutzerschlüssel erzeugt.

Zuerst wird der Block mit Rundenschlüssel[0] per bitweisem XOR verknüpft. In den Runden 1 bis R−1 folgen SubBytes, ShiftRows, MixColumns und AddRoundKey. In der Schlussrunde fehlen MixColumns; sie besteht aus SubBytes, ShiftRows und AddRoundKey mit Rundenschlüssel[R]. AddRoundKey ist die einzige AES-Funktion, in die der Benutzerschlüssel unmittelbar eingeht.

Die Schlüsselexpansion erzeugt R+1 Teilschlüssel in Blockgröße. Mit N = k/32 wird der Schlüssel zunächst als Wörter W₀ bis Wₙ₋₁ eingetragen. Weitere Wörter entstehen grundsätzlich durch XOR von Wᵢ₋₁ und Wᵢ₋ₙ. Jedes N-te Wort wird zuvor um 8 Bit nach links rotiert, byteweise mit der S-Box substituiert und mit einer Konstanten verknüpft; bei N>6 erfolgt zusätzlich bei i ≡ 4 mod N eine Substitution. Die Konstanten Cⱼ enthalten 2ʲ im Körper F₂⁸ im höchsten Byte, die übrigen Bytes sind 0.

Die Umformungen eines Blocks

SubBytes ersetzt jedes Byte B durch S(B), also einen Eintrag der S-Box. Diese Substitutionsbox bewirkt Konfusion: Die Beziehung zwischen Klartext und Geheimtext wird verwischt. Die Rijndael-S-Box besitzt 256 Werte. Für jedes Byte außer 0 wird im endlichen Körper F₂⁸ das multiplikative Inverse gebildet, danach eine affine Transformation ausgeführt: S(x)=x̄ ⊕ (x̄ ≪≪ 1) ⊕ (x̄ ≪≪ 2) ⊕ (x̄ ≪≪ 3) ⊕ (x̄ ≪≪ 4) ⊕ (63)hex. Für x=0 ist x̄=0; ≪≪ bezeichnet eine Linksrotation, ⊕ XOR. Die S-Box soll lineare, differentielle und algebraische Angriffe erschweren.

ShiftRows verschiebt die Zeilen der Tabelle zyklisch nach links. Für AES bleiben die Verschiebungen der vier Zeilen 0, 1, 2 und 3 Spalten. MixColumns mischt anschließend – außer in der Schlussrunde – die vier Bytes jeder Spalte. Die Berechnung erfolgt im Galois-Körper GF(2⁸) modulo x⁸+x⁴+x³+x+1. Dabei gilt a·1=a, a·2=2a für a<2⁷, sonst 2a ⊕ (11b)hex, und a·3=(a·2)⊕a. Die neuen Bytes entstehen aus XOR-Verknüpfungen der alten Bytes mit den Faktoren 1, 2 und 3.

Zur Entschlüsselung werden die Rundenschlüssel erzeugt und die Schritte in umgekehrter Reihenfolge ab der Schlussrunde ausgeführt. Wegen der XOR-Verknüpfungen sind viele Funktionen dieselben; erforderlich sind jedoch die inverse S-Box und Zeilenverschiebungen in Gegenrichtung.

Einsatzgebiete und Implementierung

AES wird unter anderem in WLAN nach IEEE 802.11i und WPA2, WiMAX, HomePlug AV, SSH, IPsec und IP-Telefonie mit SRTP oder Skype eingesetzt. Weitere genannte Anwendungen sind verschlüsselte Disk-Images und FileVault unter Mac OS X, EFS in Windows XP ab SP 1, Archive wie 7-Zip und RAR, PGP, GnuPG sowie LTO-Bandlaufwerke ab LTO-4. AES gehört zu den von NESSIE empfohlenen Algorithmen und zur Suite B der NSA.

Intel- und AMD-CPUs unterstützen AES teilweise durch AES-NI. Damit soll Verschlüsselung fünfmal und Entschlüsselung 25-mal schneller als mit nicht spezialisierten Maschinenbefehlen erfolgen; Bibliotheken wie OpenSSL nutzen diese Hardware-Unterstützung. AES schützt außerdem die Kommunikation zwischen elektronischen Identitätsdokumenten, etwa neueren Reisepässen oder dem deutschen Personalausweis, und Inspektionsgeräten. Da AES eine Blockverschlüsselung ist, sollte ein Betriebsmodus eingesetzt werden, der die Blöcke verkettet und die Sicherheit weiter erhöht.

Schwächen und bekannte Angriffe

Kritisiert wurden die algebraisch einfach beschreibbare S-Box als einzige nichtlineare Komponente und die einfache Schlüsseleinteilung: Ein beliebiger Rundenschlüssel würde 128 Bit des Verfahrensschlüssels kompromittieren. Außerdem wurde die Sicherheitsmarge mit nur drei Runden bei 128-Bit- und fünf Runden bei 256-Bit-Schlüsseln als gering angesehen.

Der Biclique-Angriff von Andrey Bogdanov, Dmitry Khovratovich und Christian Rechberger wurde im August 2011 vorgestellt. Er ist im Mittel etwa Faktor 4 schneller als die vollständige Schlüsselsuche, benötigt für AES-128 aber noch 2^126,1, für AES-192 2^189,7 und für AES-256 2^254,4 Schritte. Er ist daher praktisch nicht relevant.

Der 2002 vorgestellte theoretische XSL-Angriff von Courtois und Pieprzyk beschreibt AES als große Systeme quadratischer Gleichungen in GF(2). Die Autoren gaben eine Komplexität um 2^100 Operationen an, doch andere Wissenschaftler, darunter Don Coppersmith, bezweifelten diese Abschätzung. Für AES-128 entstehen 8000 quadratische Gleichungen mit 1600 Variablen; der Angriff ist praktisch nicht anwendbar.

Weitere Angriffe betreffen vor allem besondere Voraussetzungen oder konkrete Implementierungen: 2005 wurde eine Timing-Attacke beschrieben. Angriffe mit verwandtem Schlüssel erreichten 2009 bei AES-256 zunächst 2^119 und später 2^99,5 Komplexität, bleiben aber praktisch wenig relevant. 2017 wurde ein Angriff über von einer bestimmten CPU abgestrahlte Funksignale beschrieben; unter speziellen Bedingungen könne er den Schlüssel in maximal fünf Minuten aus etwa 1 Meter Entfernung ermitteln. Dies ist ein Angriff auf eine einzelne Implementierung, nicht auf AES selbst.