Rijndael

AES
Der Substitutionschritt, einer von 4 Teilschritten pro Runde
Entwickler	Joan Daemen, Vincent Rijmen
Veröffentlicht	1998, Zertifizierung Oktober 2000
Abgeleitet von	Square
Zertifizierung	NESSIE
Schlüssellänge	128, 192 oder 256 Bit
Blockgröße	128 Bit
Struktur	Substitution
Runden	10, 12 oder 14 (Schlüssellängenabhängig)
Beste bekannte Kryptoanalyse
Ein Angriff mit verwandtem Schlüssel kann bis zu 9 Runden bei einer Schlüssellänge von 256 Bit entschlüsseln. Ein Angriff mit frei wählbarem Klartext kann 8 Runden bei einer Schlüssellänge von 192 Bit und 7 Runden bei einer Schlüssellänge von 128 Bit entschlüsseln. (Ferguson et al, 2000)

Der Advanced Encryption Standard (AES) ist ein symmetrisches Kryptosystem, das als Nachfolger für DES bzw. 3DES im Oktober 2000 vom National Institute of Standards and Technology (NIST) als Standard bekannt gegeben wurde. Nach seinen Entwicklern Joan Daemen und Vincent Rijmen wird er auch Rijndael-Algorithmus genannt (gesprochen wie dt. „Reyndahl“).

Der Rijndael-Algorithmus besitzt eine variable Blockgröße von 128, 192 oder 256 Bit und eine variable Schlüssellänge von 128, 192 oder 256 Bit. Rijndael bietet ein sehr hohes Maß an Sicherheit. Das Verfahren wurde eingehenden kryptoanalytischen Prüfungen unterzogen. AES schränkt die Blocklänge auf 128 Bit ein, während die Wahl der Schlüssellänge von 128, 192 oder 256 Bits unverändert übernommen worden ist. Anhand der Schlüssellänge wird zwischen den drei AES-Varianten AES-128, AES-192 und AES-256 unterschieden.

Der Algorithmus ist frei verfügbar und darf ohne Lizenzgebühren eingesetzt sowie in Software bzw. Hardware implementiert werden. AES ist in den USA für staatliche Dokumente mit höchster Geheimhaltungsstufe zugelassen.

Entstehung

Bis zum Einsatz von AES war der 1976 festgelegte Data Encryption Standard (DES) der am häufigsten genutzte symmetrische Algorithmus zur Verschlüsselung von Daten. In den 1990er Jahren galt er mit seiner Schlüssellänge von 56 Bit als nicht mehr ausreichend sicher gegen Brute-Force-Angriffe. Zwar kann man mittels einer dreifachen Anwendung von DES, genannt 3DES, die effektive Schlüssellänge auf 112 Bit steigern, jedoch geht dies sehr zu Lasten der Geschwindigkeit.

Auswahl eines DES-Nachfolgers

Das US-amerikanische National Institute of Standards and Technology (NIST) hatte Anfang 1997 zu einem offenen Wettbewerb aufgerufen, dessen Sieger als Advanced Encryption Standard (AES) festgelegt werden sollte. Dabei wurden folgende Kriterien aufgestellt, die von den Algorithmen zu erfüllen sind:

• AES muss ein symmetrischer Algorithmus sein, und zwar eine Blockchiffre.
• AES muss 128 Bit lange Blöcke verwenden (dies wurde erst während der Ausschreibung festgelegt, zu Beginn der Ausschreibung waren auch Blockgrößen von 192 und 256 Bit verlangt, diese wurden nur als mögliche Erweiterungen beibehalten)
• AES muss Schlüssel von 128, 192 und 256 Bit Länge einsetzen können.
• AES soll gleichermaßen leicht in Hard- und Software zu implementieren sein.
• AES soll in Hardware wie Software eine überdurchschnittliche Performance haben.
• AES soll allen bekannten Methoden der Kryptoanalyse widerstehen können, insbesondere Power- und Timing-Attacken.
• Speziell für den Einsatz in Smartcards sollen geringe Ressourcen erforderlich sein (kurze Codelänge, niedriger Speicherbedarf).
• Der Algorithmus muss frei von patentrechtlichen Ansprüchen sein und muss von jedermann unentgeltlich genutzt werden können.

Im August 1998 gingen schließlich 15 Algorithmen beim NIST ein, die öffentlich diskutiert und auf die Erfüllung der genannten Kriterien geprüft wurden. Die engere Wahl war im April 1999 beendet und die fünf besten Kandidaten (MARS, RC6, Rijndael, Serpent, Twofish) kamen in die nächste Runde.

Alle fünf Kandidaten erfüllen die oben genannten Forderungen. Daher wurden weitere Kriterien hinzugezogen. Es folgte eine Überprüfung der Algorithmen auf theoretische Schwachstellen, durch die der Algorithmus möglicherweise zu einem späteren Zeitpunkt durch Technologie-Fortschritt unsicher werden kann. So können zum jetzigen Stand technisch nicht realisierbare Vorgehensweisen in einigen Jahren anwendbar sein. Ein solches Risiko soll minimiert werden.

Eindeutiger war jedoch die Staffelung der Kandidaten nach Ressourcenverbrauch und Performance. Denn nur der Rijndael-Algorithmus ist als Hardware- und Software-Implementierung überdurchschnittlich schnell. Andere Kandidaten haben jeweils in unterschiedlichen Bereichen kleinere Schwächen.

Im Mai des Jahres 2000 wurden die Analysen und öffentlichen Diskussionen abgeschlossen und am 2. Oktober 2000 der Sieger schließlich bekannt gegeben: Der belgische Algorithmus Rijndael. Rijndael überzeugte durch seine Einfachheit (die Referenz-Implementierung umfasst weniger als 500 Zeilen C-Code) und Performance, sodass sich die USA trotz Sicherheitsbedenken für einen europäischen Algorithmus entschieden.

Der Auswahlprozess faszinierte weltweit viele Kryptographen insbesondere durch seine offene Gestaltung. Bis heute ist dieser Wettbewerb als sehr vorbildlich angesehen.

Arbeitsweise

Rijndael ist, wie bereits erwähnt, eine Blockchiffre. Bei Rijndael können Blocklänge und Schlüssellänge unabhängig voneinander die Werte 128, 160, 192, 224 oder 256 Bits erhalten, während bei AES die Einschränkung der festgelegten Blockgröße von 128 Bit und der Schlüsselgröße von 128, 192 oder 256 Bit gilt. Jeder Block wird zunächst in eine zweidimensionale Tabelle mit vier Zeilen geschrieben, deren Zellen ein Byte groß sind. Die Anzahl der Spalten variiert somit je nach Blockgröße von 4 (128 Bits) bis 8 (256 Bits). Jeder Block wird nun nacheinander bestimmten Transformationen unterzogen. Aber anstatt jeden Block einmal mit dem Schlüssel zu verschlüsseln, wendet Rijndael verschiedene Teile des erweiterten Originalschlüssels nacheinander auf den Klartext-Block an. Die Anzahl r dieser Runden variiert und ist von der Schlüssellänge k und Blockgröße b abhängig (beim AES also nur von der Schlüssellänge):

Anzahl der Runden bei Rijndael. (Die für AES relevanten Werte sind farbig unterlegt.)

	b = 128	b = 160	b = 192	b = 224	b = 256
k = 128	10	11	12	13	14
k = 160	11	11	12	13	14
k = 192	12	12	12	13	14
k = 224	13	13	13	13	14
k = 256	14	14	14	14	14

S-Box

Eine Substitutionsbox (S-Box) dient als Basis für eine monoalphabetische Verschlüsselung. Sie ist meist als Array implementiert und gibt an, welches Byte wie getauscht wird. Die S-Box in AES basiert auf einem mathematischen Zusammenhang und ist somit fest im Algorithmus implementiert. Doch dies ist kein Schwachpunkt, da die S-Box lediglich zur Vermischung der Bytes in Kombination mit weiteren Operationen und dem Schlüssel genutzt wird.

Ablauf

• Schlüsselexpansion
• Vorrunde
  • KeyAddition (Rundenschlüssel[0])
• Verschlüsselungsrunden (wiederhole solange Runde < R)
  • Substitution()
  • ShiftRow()
  • MixColumn()
  • KeyAddition(Rundenschlüssel[runde])
• Schlussrunde
  • Substitution()
  • ShiftRow()
  • KeyAddition(Rundenschlüssel[R])

(Die Schlussrunde zählt auch als Runde, also R = Anzahl Verschlüsselungsrunden + 1 Schlussrunde)

Schlüsselexpansion

Prinzip der Schlüsselexpansion bei AES

Zunächst muss der Schlüssel in R + 1 Teilschlüssel (auch Rundenschlüssel genannt) aufgeteilt werden. Die Rundenschlüssel müssen die gleiche Länge wie die Blöcke erhalten. Somit muss der Benutzerschlüssel auf die Länge b * (R + 1) expandiert werden, wobei b die Blockgröße angibt. Die Schlüssel werden wieder in zweidimensionalen Tabellen mit vier Zeilen und Zellen der Größe 1 Byte gebildet. Die ersten Spalten der Tabelle werden mit dem Benutzerschlüssel gefüllt. Die weiteren Spalten werden wie folgt rekursiv berechnet: Um die Werte für die Zellen in der nächsten Spalte zu erhalten, wird zunächst das Byte, welches sich in der letzten (je nach Blockgröße: vierten, sechsten oder achten) Spalte befindet und drei Zeilen zurückliegt, durch die S-Box verschlüsselt und anschließend mit dem um eine Schlüssellänge zurückliegenden Byte XOR verknüpft. Befindet sich das zu berechnende Byte an einer Position, die ein ganzzahliger Teiler der Schlüssellänge ist, so wird das berechnete Byte zusätzlich mit einem Eintrag aus der rcon-Tabelle XOR verknüpft. Hierfür wird als Index eine fortlaufende Nummer verwendet. Die rcon-Tabelle ist ähnlich wie die S-Box eine Tabelle in Form eines Arrays, das konstante Werte enthält die auf einem mathematischen Zusammenhang beruhen. Jedes weitere Byte (das sich nicht in der ersten Spalte befindet) wird aus einer XOR-Verknüpfung des vorherigen Bytes (w_{i − 1}) mit dem Byte einer Schlüssellänge vorher (w_{i − k / 32}) gebildet.

KeyAddition

Bitweise XOR-Verknüpfung zwischen dem Block und dem aktuellen Rundenschlüssel

In der Vorrunde und am Ende jeder weiteren Verschlüsselungsrunde wird die KeyAddition ausgeführt. Hierbei wird eine bitweise XOR-Verknüpfung zwischen dem Block und dem aktuellen Rundenschlüssel vorgenommen. Dies ist die einzige Funktion in AES, die den Algorithmus vom Benutzerschlüssel abhängig macht.

Substitution

Im ersten Schritt jeder Runde wird für jedes Byte im Block ein Äquivalent in der S-Box gesucht. Somit werden die Daten monoalphabetisch verschlüsselt.

ShiftRow

Zeilen werden um eine bestimmte Anzahl von Spalten nach links verschoben

Wie oben erwähnt, liegt ein Block in Form einer zweidimensionalen Tabelle mit vier Zeilen vor. In diesem Schritt werden die Zeilen um eine bestimmte Anzahl von Spalten nach links verschoben. Überlaufende Zellen werden von rechts fortgesetzt. Die Anzahl der Verschiebungen ist zeilen- und blocklängenabhängig:

Je nach Blocklänge b und Zeile in der Datentabelle wird die Zeile um 1 bis 4 Spalten verschoben

Für den AES sind nur die fett markierten Werte relevant

r	b=128	b=160	b=192	b=224	b=256
Zeile 1	0	0	0	0	0
Zeile 2	1	1	1	1	1
Zeile 3	2	2	2	2	3
Zeile 4	3	3	3	4	4

MixColumn

Die Spalten werden vermischt

→ Hauptartikel: Rijndael MixColumns

Schließlich werden die Spalten vermischt. Es wird zunächst jede Zelle einer Spalte mit einer Konstanten multipliziert und anschließend die Ergebnisse XOR verknüpft. Die Konstante (als Hexadezimal-Wert) wird folgendermaßen bestimmt:

	Spalte 1	Spalte 2	Spalte 3	Spalte 4
Zeile 1	02	03	01	01
Zeile 2	01	02	03	01
Zeile 3	01	01	02	03
Zeile 4	03	01	01	02

Entschlüsselung

Bei der Entschlüsselung von Daten wird genau rückwärts vorgegangen. Die Daten werden zunächst wieder in zweidimensionale Tabellen gelesen und die Rundenschlüssel generiert. Allerdings wird nun mit der Schlussrunde angefangen und alle Funktionen in jeder Runde in der umgekehrten Reihenfolge aufgerufen. Durch die vielen XOR-Verknüpfungen unterscheiden sich die meisten Funktionen zum Entschlüsseln nicht von denen zum Verschlüsseln. Jedoch muss eine andere S-Box genutzt werden (die sich aus der original S-Box berechnen lässt) und die Zeilenverschiebungen erfolgen in die andere Richtung.

Anwendung

AES wird u. a. vom Verschlüsselungsstandard IEEE 802.11i für Wireless LAN und seinem Wi-Fi-Äquivalent WPA2 sowie bei SSH und bei IPsec genutzt. Auch in der VoIP-Kommunikation kommt AES sowohl in offenen Protokollen wie SRTP oder proprietären Systemen wie Skype^[1] zum Einsatz. Mac OS X benutzt AES als Standardverschlüsselungsmethode für Disk-Images, außerdem verwendet der Dienst FileVault AES. Moderne externe Festplatten verschlüsseln den gesamten Datenzugriff per AES.^[2] Ebenso verwendete die transparente Verschlüsselung EFS in Windows XP ab SP 1 diese Methode. Außerdem wird der Algorithmus zur Verschlüsselung diverser komprimierter Dateiarchive verwendet, z. B. bei 7-Zip und RAR. In PGP und GnuPG findet AES ebenfalls einen großen Anwendungsbereich.

AES gehört zu den vom Projekt NESSIE empfohlenen kryptografischen Algorithmen.

Schwächen und Angriffe

Kurz vor der Bekanntgabe des AES-Wettbewerbs stellten verschiedene Autoren eine einfache algebraische Darstellung von AES als Kettenbruch vor. Dies könnte für erfolgreiche Angriffe genutzt werden. Hierzu gibt es einen Videovortrag von Niels Ferguson auf der HAL 2001 ^[3].

2002 wurde von Courtois and Pieprzyk ein theoretischer Angriff namens XSL gegen Serpent und Rijndael vorgestellt (siehe Serpent).

Im Mai 2005 veröffentlichte Daniel Bernstein einen Artikel (PDF-Version) über eine unerwartet einfache Timing-Attacke (eine Art der Seitenkanalattacke) auf den Advanced Encryption Standard.

Literatur

• Joan Daemen, Vincent Rijmen: The Design of Rijndael. AES: The Advanced Encryption Standard. ISBN 3-540-42580-2. (Englisch)

Weblinks

• http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf – Offizielle Spezifikation des AES vom NIST
• http://www.cryptosystem.net/aes/ – Angriffe auf die Sicherheit von AES
• http://www.realtec.de/privat/arbeiten.shtml – Ausführlichere deutsche Erklärung des Algorithmus (PDF) und Historie des Auswahlverfahrens
• Beschreibung von Markus Repges der AES-Kandidaten (Finalisten)
• NIST, Report on the Development of the Advanced Encryption Standard (AES), 2. Oktober 2000
• Flashanimation von AES – AES als Flash erklärt und animiert (Animation by Enrique Zabala / Universität ORT / Montevideo / Uruguay)
• AESPipe – Komfortable Ver-/Entschlüsselung von Datenströmen für die Linuxshell (StdIn nach StdOut)
• AES Artikel – Sehr detaillierte deutsche Erklärung des AES mitsamt Rechenbeispielen und Implementierung in der Programmiersprache C

Implementierungen

C++-Bibliotheken

• Crypto++ Eine vom NIST offiziell genehmigte sehr umfangreiche C++ Open-Source Kryptographie-Bibliothek mit diversen Verschlüsselungs- und Hash-Algorithmen.
• Chris Lomont's Public-Domain Version des AES

Java

• Bouncy castle (cryptography) Offizielle Bouncy Castle Crypto Library

Andere Sprachen

• tcllib zur Sprache Tcl, ab Version 1.8
• mcrypt zur Sprache PHP
• System.Security.Cryptography C#, .NET
• Crypt::Rijndael Perl
• Delphi Encryption Compendium zur Sprache Delphi
• pidCrypt für JavaScript

Einzelnachweise

1. ↑ Tom Berson: Skype Security Evaluation auf skype.com mit Signatur, 18. Oktober 2005, englisch, PDF
2. ↑ Allround-PC: Digittrade Security Festplatte – Datensicherheit mit RFID und AES auf 2,5″, 26. November 2008
3. ↑ ftp://ftp.ccc.de/events/hal2001/video/hal2001_cryptoanalis_of_rijndael_48.mp4

Symmetrische Verschlüsselungsverfahren

Blockchiffren: 3DES (Triple DES) | A5/3 (KASUMI) | AES | Anubis | Blowfish | Camellia | CAST | DES | FEAL | FOX | IDEA | Lucifer | Magenta | MARS | MISTY1 | RC2 | RC5 | RC6 | SEED | Serpent | SHACAL | Skipjack | TEA | Twofish | XTEA 

Stromchiffren: A5/1 | A5/2 | Rabbit | RC4 | SEAL