Dipl.-Inform. Carsten Eilers

SubBytes^-1

Jedes Byte im aktuellen Block wird durch die inverse S-Box umgewandelt.

ShiftRow^-1

Die ShiftRow-Verschiebung wird durch Verschiebung in die Gegenrichtung rückgängig gemacht: Die Bytes des aktuellen Blocks werden zeilenweise nach rechts verschoben, übergelaufene Zellen von links nachgeschoben.

MixColumn^-1

Die Spalten des aktuellen Blocks werden mit dem zum bei der Verschlüsselung verwendeten konstanten Polynom inversen Polynom multipliziert.

AddRoundKey

Aktueller Block und aktueller Rundenschlüssel werden bitweise XOR-verknüpft Die Umkehrung besteht darin, das die Rundenschlüssel in umgekehrter Reihenfolge verwendet werden.

Den Ablauf der AES-Entschlüsselung zeigt Abbildung 1.

Abb. 1: Ablauf der AES-Entschlüsselung

Die Sicherheit von AES

Die linearen Transformationen MixColumn und ShiftRow sorgen für eine optimale Vermischung der Bits innerhalb jedes Blocks. Die nichtlineare Substitution durch die S-Box in SubBytes schützt vor differentieller und linearer Kryptanalyse. Die XOR-Verknüpfung mit den Rundenschlüsseln vor der ersten und nach jeder weiteren Runde führt dazu, dass jedes Bit vom Schlüssel abhängig ist.

Da AES auf mathematischen Funktionen basiert, ist es Niels Ferguson, Richard Schroeppel und Doug Whiting bereits 2001 gelungen, den allgemeinen Algorithmus als Formel mit 2⁷⁰ Termen zu schreiben, siehe ihre Ankündigung samt Paper auf archive.org

128-Bit-AES wurde von Nicolas Courtois und Josef Pieprzyk 2002 als System von ca. 8.000 Gleichungen mit 1.600 Variablen dargestellt. Solche Systeme können theoretisch gelöst werden, praktisch scheitert ein Angriff darüber (noch) an der Komplexität der Aufgabe und damit an der benötigten Rechenzeit. Trotzdem könnte sich die algebraische Einfachheit in der Zukunft als entscheidende Schwachstelle von AES erweisen.

Der von Nicolas Courtois und Josef Pieprzyk entwickelte XSL-Angriff ("eXtended Sparse Linearization") erreicht eine Komplexität im Bereich von 2¹⁰⁰ Operationen. XSL ist eine Weiterentwicklung der "eXtended Linearization" (XL), mit der manche große, nichtlineare Gleichungssysteme effizient berechnet werden können. Eigentlich richten sich XL-Angriffe gegen Public-Key-Systeme. Ihre Verwendung für symmetrische Systeme wurde von Nicolas Courtois und Josef Pieprzyk entwickelt.

Weitere Verbesserungen wurden zum Beispiel von Alex Biryukov und Dmitry Khovratovich entwickelt. Mitte 2009 griffen die beiden die AES-Varianten mit 192 und 256 Bit Schlüssellänge an. Ihr Algorithmus hatte eine Komplexität von 2¹¹⁹ (PDF, FAQ). Ende 2009 konnten sie die Komplexität des Angriffs auf AES-256 auf 2^99,5 verbessern. Praktisch ändert das aber bisher nichts, denn berechnen lässt sich AES damit immer noch nicht.

Daran ändert auch der 2011 von Andrey Bogdanov, Dmitry Khovratovich und Christian Rechberger vorgestellte erste Angriff auf den AES-Algorithmus nichts (PDF). Für die Berechnung eines AES-128-Schlüssels werden 2^126,1 Schritte benötigt, für einen AES-192-Schlüssel werden 2^189,7 und für einen AES-256-Schlüssel 2^254,4. Damit sind die Angriffe zwar um ungefähr den Faktor 4 schneller als ein Brute-Force-Angriff, aber das ändert nichts daran, dass die Berechnung immer noch schlicht zu lange dauert.

Zur Zeit erfolgversprechender sind die sog. Seitenkanal-Angriffe ("side chanel attacks", bei denen nicht der Algorithmus, sondern seine Implementierung das Ziel des Angriffs ist. So kann beispielsweise der Inhalt eines Prozessor-Caches Informationen über eine zuvor durchgeführte AES-Berechnung an einen anderen Prozess 'verraten', wie Dag Arne Osvik, Adi Shamir und Eran Tromer bereits 2005 gezeigt haben (PDF). Dazu muss der Angreifer aber sein eigenes Programm auf dem gleichen Rechner laufen lassen, auf dem die AES-Ver- oder Entschlüsselung durchgeführt wird. Was zumindest in Cloud-Umgebungen nicht ausgeschlossen ist.

Bisher kann AES auf jedem Fall als sicherer Algorithmus angesehen werden.

Anwendungen von AES

AES im WLAN

Der Wi-Fi Protected Access 2 Standard (WPA2, IEEE 802.11i) nutzt AES zur Verschlüsselung von über WLAN übertragenen Daten. Alle bisher bekannten Angriffe auf WPA2 basieren auf dem Ausspähen oder der Brute-Force-Berechnung verwendeter schwacher Schlüssel, was ein gutes Beispiel dafür ist, das ein sicherer Algorithmus allein noch nicht zu einem sicheren System führt.

AES in GnuPG

AES ist einer der in GnuPG zur Verschlüsselung zur Verfügung stehenden Algorithmen. Dabei verwendet GnuPG ein sogenanntes hybrides Verschlüsselungsverfahren: Die Nachricht wird mit einem zufällig erzeugten Sitzungsschlüssel mit einem symmetrischen Verfahren, zum Beispiel AES, verschlüsselt. Der Sitzungsschlüssel wird danach mit dem öffentlichen Schlüssel eines asymmetrischen Verfahrens (auch Public-Key-Verfahren genannt) verschlüsselt und zur verschlüsselten Nachricht hinzugefügt. Der Empfänger verwendet seinen geheimen Schlüssel des asymmetrischen Verfahrens, um den Sitzungsschlüssel zu entschlüsseln. Danach kann er damit die eigentliche Nachricht entschlüsseln.

Alle bisher vorgestellten Verfahren waren symmetrische Verfahren: Für Ver- und Entschlüsselung wird der gleiche Schlüssel verwendet. In der nächsten Folge werden asymmetrische Verfahren vorgestellt, die für Ver- und Entschlüsselung zwei separate Schlüssel verwenden.

Carsten Eilers