weiter

AES (Rijndael)

Die Belgier Joan Daemen und Vincent Rijmen nahmen von 1998 bis 2000 an der Ausschreibung des NIST für den Advanced Encryption Standard AES mit ihrer Chiffre Rijndael teil. Am 2. Oktober 2000 wurde Rijndael zum Sieger der Ausschreibung erklärt und firmiert seitdem unter dem Namen AES.

Alle Kandidaten für den AES mussten die Schlüssellängen 128, 192 und 256 Bit unterstützen. Genau diese unterstützt auch der AES, jedoch keine weiteren. Die Blocklänge war für alle AES-Kandidaten auf 128 Bit vorgeschrieben, wobei AES auch die Blocklängen 192 und 256 Bit unterstützt. Dieses Dokument beschränkt sich jedoch auf die Betrachtung einer Blocklänge von 128 Bit. Die Rundenzahl ist bei allen AES-Kandidaten verhandelbar, die Defaultrundenzahlen richten sich beim AES nach der Schlüssellänge. Wird ein 128-Bit-Schlüssel eingesetzt, so durchläuft der Klartext 10 Runden des AES. Bei Einsatz eines 192-Bit-Schlüssels werden 12 Runden durchlaufen und wenn die Schlüssellänge 256 Bit beträgt, werden 14 Runden durchlaufen.

Der Textblock wird beim AES als 4xNb-Matrix betrachtet, wobei Nb für die Blocklänge in Bit dividiert durch 32 steht. Bei einer Blocklänge von 128 Bit ist Nb demnach 4 und es handelt sich um eine 4x4-Matrix. Die Einträge dieser Matrix, die im Folgenden als T bezeichnet wird, besitzen die Länge 1 Byte.

Zu Beginn des Algorithmus werden alle Einträge der Matrix T mit jeweils einem Byte eines Teilschlüssels XOR-verknüpft. Anschließend beginnen die einzelnen Runden, die nach folgendem Schema bearbeitet werden.

Zunächst wird die Matrix T einer Substitution, die als „ByteSub“ bezeichnet ist, unterzogen. Dabei ist jedes Byte der Matrix Input für eine S-Box, deren Output wiederum ein Byte ist. Die S-Box ist die Komposition aus zwei Transformationen. Zuerst wird die multiplikative Inverse über das Galoisfeld GF(2⁸) gebildet. Anschließend wird eine affine Transformation über GF(2) nach folgender Definition durchgeführt:

Die Substitution wird im folgenden Bild veranschaulicht.

Anschließend wird der Textblock T einer Zeilenrotation unterworfen, die als „ShiftRow“ bezeichnet ist. Die Art der Rotation ist hierbei von der Größe der Matrix bzw. von der Blocklänge abhängig. Im betrachteten Fall, bei dem die Blocklänge 128 Bit beträgt, es sich also bei T um eine 4x4-Matrix handelt, rotiert die erste Zeile um 0, die zweite um 1, die dritte um 2 und die vierte Zeile um 3 Positionen nach links.

Nun werden die Einträge der Matrix T als Polynome über GF(2⁸) betrachtet. Jede Spalte der Matrix T wird in der Funktion „MixColumn“ mit einem fest definierten Polynom c(x) modulo (x⁴ + 1) multipliziert. Dies kann auf Grund des Moduls als Matrixmultiplikation geschrieben werden.

Das Polynom c(x) ist gegeben durch:

c(x) = ´03´× x³ + ´01´× x² + ´01´× x + ´02´

Die Koeffizienten entsprechen hierbei der hexadezimalen Schreibweise von Polynomen modulo (x⁴ + 1). Daraus ergibt sich die Matrix C:

Die einzelnen Spalten der Matrix T werden also mit der Matrix C multipliziert, wobei die Addition der Einträge einer XOR-Verknüpfung entspricht und die Multiplikation der Einträge modulo (x⁴ + 1) durchgeführt werden muss.

Abschließend werden alle Einträge der Matrix T mit den Einträgen einer rundenabhängigen Teilschlüsselmatrix XOR-verknüpft. Dabei hat die Teilschlüsselmatrix natürlich die gleiche Größe, wie die Textmatrix T.

In der letzten Runde des Algorithmus wird die Funktion „MixColumn“ nicht durchgeführt.

Zur Entschlüsselung wird der gesamte Algorithmus rückwärts durchlaufen und auch die Teilschlüssel werden umgekehrt zugeordnet. Die XOR-Verknüpfung ist selbstinvers, daher muss keine gesonderte Funktion eingesetzt werden.

Für die Funktion „MixColumn“ muss einen inverse Operation definiert werden. Die Einträge der Matrix T werden wiederum mit einer Matrix, der inversen Matrix zu C, im Folgenden als D bezeichnet, multipliziert.

Die Matrix D ist gegeben durch:

D repräsentiert das Polynom d(x), das sich aus der Bedingung

c(x)Ä d(x) = ´01´

ergibt.

Die inverse Funktion von „ShiftRow“ entspricht einfach einer Rotation nach rechts um die entsprechende Anzahl an Positionen für die jeweilige Zeile der Matrix T.

Zur Invertierung der Funktion „ByteSub“ müssen die inversen S-Boxen gebildet werden. Hierzu muss zunächst die Inverse der affinen Transformation über GF(2) gebildet werden und anschließend muss die multiplikative Inverse über GF(2⁸) gebildet werden.

Zu Beginn des Algorithmus und in jeder Runde wird eine Teilschlüsselmatrix K der Größe 4xNb benötigt. Jeder Teilschlüsseleintrag ist vier Byte oder 32 Bit lang. Mit der Rundenzahl Nr ergibt sich so eine Gesamtlänge des Teilschlüssels von 4 × Nb × (Nr + 1) Byte. Für den Fall, dass die Blocklänge und die Schlüssellänge 128 Bit betragen und 10 Runden des Algorithmus durchlaufen werden, ergibt sich also ein benötigter Gesamtschlüssel von 176 Byte oder 1408 Bit.

Die Länge Nk des geheimen Schlüssels wird in Byte geteilt durch vier angegeben. Bei einer Schlüssellänge von 128 Bit ist Nk = 4. Die ersten Teilschlüssel werden durch Kopieren des geheimen Schlüssels gesetzt. Ist der geheime Schlüssel ausgeschöpft, werden die weiteren Teilschlüssel aus einer XOR-Verknüpfung des vorangegangenen Teilschlüssels und des Teilschlüssels, der Nk Positionen zurück liegt, gesetzt. Ist die Nummer i des zu erzeugenden Teilschlüssels ein Vielfaches von Nk, so wird der vorangegangene Teilschlüssel vor der XOR-Verknüpfung einer Rotation und einer Substitution mit den oben definierten Funktionen unterzogen. Außerdem wird der Teilschlüssel mit einer Rundenkonstanten XOR-verküpft, die dem Polynom x^j-1, mit j = i¸Nk, entspricht. Zudem wird bei Schlüssellängen über 192 Bit der vorangegangene Teilschlüssel einer Substitution unterzogen, falls für die Nummer i des zu erzeugenden Teilschlüssels gilt, dass (i – 4) ein Vielfaches von Nk ist.

Die so erzeugten Teilschlüssel werden in den einzelnen Runden nacheinander genutzt. Hierbei bestimmt die Blocklänge, wie viele der 32-Bit-Teilschlüssel benötigt werden.

Man geht davon aus, dass der einzige durchführbare Angriff gegen den AES durch eine Brute Force Attack durchgeführt werden kann. Es gibt mittlerweile zwar einen Angriff nach der sogenannten XSL Methode, aber dieser Angriff wird derzeit noch als rein theoretischer Angriff gewertet.
Dementsprechend ist die gebotene Sicherheit von der Länge des geheimen Schlüssels abhängig. Die Auswahl von Rijndael als AES wurde durch seine Effizienz und Geschwindigkeit begründet.

Zum besseren Verständnis können Sie hier den Quelltext einer AES-Verschlüsselung, implementiert in Pascal mit der IDE Lazarus, herunterladen. Vielen Dank an den Autor Henner Heck!

weiter

[Home] [IPSec] [SSL] [AES-Kandidaten] [Über mich] [Rechtliche Hinweise]