AES, der Advanced Encryption Standard, ist der offizielle Nachfolger von DES. Da abzusehen war, dass DES nicht mehr lange sicher sein würde, wurde vom US-amerikanischen National Institute of Standards and Technology (NIST) am 2. Januar 1997 die Suche nach einem Nachfolger offiziell eingeleitet. Am 12. September 1997 folgte die offizielle Ausschreibung (Request for Candidate). Dabei wurden folgende Anforderungen festgelegt:

• Der neue Algorithmus muss eine symmetrische Blockchiffre
• mit einer Blocklänge von mindestens 128 Bit sein, die
• 128, 192 und 256 Bit lange Schlüssel verwenden kann.
• Die Implementierung soll sowohl in Hard- wie auch Software möglich sein und
• überdurchschnittliche Performance haben.
• Für den Einsatz in Smartcards wird ein geringer Ressourcenbedarf gefordert, d.h. z.B. kurzer Code und geringer Speicherbedarf.
• Natürlich muss der neue Algorithmus allen bekannten Methoden der Kryptanalyse widerstehen.
• Außerdem muss der Algorithmus von jedermann unentgeltlich genutzt werden können.

Daraufhin wurden 15 Algorithmen eingereicht, von denen nach einer ersten Auswahlrunde im August 1999 fünf in die engere Wahl kamen (Presseerklärung (PDF)). Am Ende der zweiten Auswahlrunde fiel die Wahl auf den von Joan Daemen und Vincent Rijmen unter den Namen Rijndael eingereichten Algorithmus (Presseerklärung vom 2. Oktober 2000). Am 26. November 2001 wurde der Advanced Encryption Standard (AES) in FIPS 197 (PDF) veröffentlicht.

Der Algorithmus

Während Rijndael für Schlüssellängen und Blockgrößen zwischen 128 und 256 Bit in 32-Bit-Schritten spezifiziert werden kann, wurde für AES die Blockgröße auf 128 Bit und die Schlüssellänge auf 128, 192 oder 256 Bit festgelegt.

AES wendet eine Reihe von Transformationen in mehreren Runden auf die Eingabe an. Die Anzahl der Runden ist abhängig von der Schlüssellänge:

AES verwendet Bytes und Worte aus 4 Bytes. Gerechnet wird im endlichen Körper (Galois Field), der 256 Elemente besitzt. Ein Byte kann darin als Polynom dargestellt werden. Darauf wird dann eine Addition und Multiplikation definiert. Wer an den Grundlagen interessiert ist, findet eine Einführung z.B. im Standard-Dokument FIPS 197.

S-Box

AES verwendet wie DES eine S-Box genannte Substitutionsbox. Auf die mathematischen Grundlagen der S-Box kann hier aus Platzgründen nicht eingegangen werden.

Einlesen der Daten

AES arbeitet mit zweidimensionalen Byte-Arrays mit 8 Bit großen Elementen, genannt State (dt. Zustand). Ein solcher State ist eine Tabelle mit vier Zeilen und vier Spalten, in die zu Beginn der Klartext spaltenweise eingelesen wird.

Eingabeblock:				State:
= 1 Byte

Schlüssel

Für die Verschlüsselung werden (Rundenzahl+1) Rundenschlüssel benötigt. Die Rundenschlüssel werden in einem zweidimensionalen Array aus 32-Bit-Werten gespeichert. Dabei wird der Chiffrierschlüssel in die ersten Elemente des Arrays geschrieben. Bei einem 128-Bit-Schlüssel erhält man also vier Rundenschlüssel. Die fehlenden Rundenschlüssel werden durch die Schlüsselexpansion aus dem Chiffrierschlüssel gebildet.

Schlüsselexpansion

Für die Schlüsselexpansion werden folgende Funktionen benötigt:

• SubWord
  wendet auf einen 4-Byte-Eingabewert die S-Box an, um den Ausgabewert zu ermitteln
• RotWord
  ist eine zyklische Linksrotation: Aus wird
• Rcon[i]
  enthält die Rundenkonstanten, auf deren Berechnung hier aus Platzgründen nicht eingegangen werden kann.

Die eigentliche Expansion erfolgt nach folgendem Pseudocode:

Schlüsselexpansion
 (Schlüssel key, Rundenschlüssel-Array w, Schlüssellänge[Bytes] n) 
BEGIN 
 i = 0
 WHILE (i < n) 
 w[i] = (key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]) 
 i = i+1 
 ENDWHILE
 
 i = n 
 WHILE (i < 4 * (Rundenzahl+1)] 
 temp = w[i-1] 
 IF (i mod n = 0) 
 temp = SubWord(RotWord(temp)) XOR Rcon[i/n] 
 ELSEIF (n > 6 and i mod n = 4) 
 temp = SubWord(temp) 
 ENDIF 
 w[i] = w[i-n] XOR temp 
 i = i + 1 
 ENDWHILE
END 
 

Transformationen

Die benötigten Transformationen:

• SubBytes
  Jedes Byte im aktuellen Block wird durch eine S-Box umgewandelt.
• ShiftRow
  Die Bytes des aktuellen Blocks werden zeilenweise nach links verschoben, übergelaufene Zellen von rechts nachgeschoben.
• MixColumn
  Die Spalten des aktuellen Blocks werden mit einem konstanten Polynom multipliziert, was einer Diffusion entspricht.
• AddRoundKey
  Aktueller Block und aktueller Rundenschlüssel werden bitweise XOR-verknüpft

Die Verschlüsselung

Der prinzipielle Ablauf:

Als Pseudocode:

AES-Verschlüsselung 
 (Klartextblock, Geheimtextblock, Rundenschlüssel-Array w)
BEGIN 
 State = Klartextblock

 AddRoundKey(State, w[0])

 FOR Runde = 1 TO Rundenzahl-1
 SubBytes(State) 
 ShiftRow(State)
 MixColumn(State)
 AddRoundKey(State, w[Runde])
 ENDFOR
 
 SubBytes(State)
 ShiftRow(State)
 AddRoundKey(State, w[Rundenzahl])
 
 Geheimtextblock = State
END

Die Entschlüsselung erfolgt durch Anwendung der inversen Transformationen in umgekehrter Reihenfolge. Mehr dazu und zur Sicherheit und Anwendung von AES in der nächsten Folge.

Carsten Eilers

About Security – Übersicht zum aktuellen Thema "Kryptographie – AES"

• About Security #74: Kryptographie – Advanced Encryption Standard (AES)
• About Security #75: AES – Entschlüsselung, Sicherheit und Anwendung