Advanced Encryption Standard (AES)

Dozent:

Prof. Dr. Michael Eichberg

Version:

2024-05-09

Basierend auf:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Quellen:

NIST FIPS PUB 197, "Advanced Encryption Standard (AES)"

Arithmetik endlicher Körper

• Ein Körper ist eine Menge, in der wir Addition, Subtraktion, Multiplikation und Division durchführen können, ohne die Menge zu verlassen.

• Die Division ist mit der folgenden Regel definiert: \(a/b = a(b^{-1})\).

Arithmetik endlicher Körper

• Der Einfachheit halber und aus Gründen der Implementierungseffizienz möchten wir mit ganzen Zahlen arbeiten, die genau in eine bestimmte Anzahl von Bits passen, ohne dass Bitmuster verschwendet werden.

  Ganze Zahlen im Bereich 0 bis \(2^n - 1\), die in ein n-Bit-Wort passen.

• Wenn eine Operation des verwendeten Algorithmus die Division ist, dann müssen wir Arithmetik anwenden, die über einem (ggf. endlichen) Körper definiert ist.

  Division erfordert, dass jedes nichtnull-Element ein multiplikatives Inverses hat.

• Wenn wir modulare Arithmetik auf die Menge der ganzen Zahlen \(Z_{2^n}\) (mit \(n > 1\)) anwenden, dann erhalten wir keinen Körper!

  Zum Beispiel hat die ganze Zahl \(2\) keine multiplikative Inverse in \(Z_{2^n}\) (mit \(n > 1\)), d. h. es gibt keine ganze Zahl \(b\), so dass \(2b\; mod\; 2^n = 1\)

• Ein endlicher Körper der \(2^n\) Elemente enthält, wird als \(GF(2^n)\) bezeichnet.

  Jedes Polynom in \(GF(2^n)\) kann durch eine n-Bit-Zahl dargestellt werden.

Arithmetik endlicher Körper in Hinblick auf AES

• Beim Advanced Encryption Standard (AES) werden alle Operationen mit 8-Bit-Bytes durchgeführt

• Die arithmetischen Operationen: Addition, Multiplikation und Division werden über den endlichen Körper \(GF(2^8)\) durchgeführt.

AES Schlüsseleigenschaften

• AES verwendet eine feste Blockgröße von 128 Bit.

• AES arbeitet mit einem 4x4-Array von 16 Bytes/128 Bits in Spaltenhauptordnung (column-major order): \(b_0,b_1,\dots,b_{15}\) genannt State (Zustand):

  \begin{equation*} \begin{bmatrix}b_{0}&b_{4}&b_{8}&b_{12}\\b_{1}&b_{5}&b_{9}&b_{13}\\b_{2}&b_{6}&b_{10}&b_{14}\\b_{3}&b_{7}&b_{11}&b_{15}\end{bmatrix} \end{equation*}

AES Verschlüsselungsprozess

AES Parameter

AES verwendet vier verschiedene Stufen

Substitute Bytes:

verwendet eine S-Box, um eine byteweise Ersetzung des Blocks vorzunehmen.

ShiftRows:

ist eine einfache Permutation.

MixColumns:

ist eine Substitution, mit Hilfe von Polynomarithmetik über \(GF(2^8)\).

AddRoundKey:

ist ein einfaches bitweises XOR des aktuellen Blocks mit einem Teil des expandierten Schlüssels.

AES Substitute Byte Transformation

AES S-box

AES Inverse S-box

S-Box Design Grundlagen

• Die S-Box ist so konzipiert, dass sie gegen bekannte kryptoanalytische Angriffe resistent ist.

• Die Rijndael-Entwickler suchten nach einem Design, das eine geringe Korrelation zwischen Eingabe- und Ausgabebits aufweist und die Eigenschaft hat, dass die Ausgabe keine lineare mathematische Funktion der Eingabe ist.

• Die Nichtlinearität ist auf die Verwendung der multiplikativen Inversen bei der Konstruktion der S-Box zurückzuführen.

Shift Row Transformation

Shift Row Transformation - Begründung

• Wesentlicher als es auf den ersten Blick scheint!

• Der Zustand (State) wird ebenso wie die Chiffrierein- und -ausgabe als Array aus vier 4-Byte-Spalten behandelt.

• Bei der Verschlüsselung werden die ersten 4 Bytes des Klartextes in die erste Spalte vom Zustands (State) kopiert, und so weiter.

• Der Rundenschlüssel wird spaltenweise auf den Zustand (State) angewendet.

• Bei einer Zeilenverschiebung wird also ein einzelnes Byte von einer Spalte in eine andere verschoben, was einem linearen Abstand von einem Vielfachen von 4 Byte entspricht.

• Die Transformation sorgt dafür, dass die 4 Bytes einer Spalte auf vier verschiedene Spalten verteilt werden.

Mix Column Transformation

Inverse Mix Column Transformation

Mix Colum Transformation - Beispiel

Mix Column Transformation - Begründung

• Die Koeffizienten einer Matrix, die auf einem linearen Code mit maximalem Abstand zwischen den Codewörtern basiert, gewährleisten eine gute Mischung zwischen den Bytes jeder Spalte.

• Die Mix Column Transformation (~ Vermischung der Spalten) - kombiniert mit der Shift Row Transformation (Zeilenverschiebung) - stellt sicher, dass nach einigen Runden alle Ausgangsbits von allen Eingangsbits abhängen.

AddRoundKey Transformation

• Die 128 Bits des Zustands (State) werden bitweise mit den 128 Bits des Rundenschlüssels XOR-verknüpft.

• Die Operation wird als spaltenweise Operation zwischen den 4 Bytes einer Spalte des Zustands (State) und einem Wort des runden Schlüssels betrachtet.

• Kann auch als eine Operation auf Byte-Ebene betrachtet werden.

AES Schlüsselexpansion

• Nimmt als Eingabe einen (hier: 128-Bit) Schlüssel mit vier Wörtern (16 Byte) und erzeugt ein lineares Array mit 44 Wörtern (176 Byte).

• Dies liefert einen vier Worte umfassenden Rundenschlüssel für die initiale AddRoundKey-Stufe sowie für jede der folgenden 10 Runden der Chiffre.

• Der Schlüssel wird in die ersten vier Wörter des erweiterten Schlüssels kopiert.

• Der Rest des expandierten Schlüssels wird in Blöcken von jeweils vier Wörtern aufgefüllt.

• Jedes hinzugefügte Wort \(w[i]\) hängt vom unmittelbar vorangehenden Wort \(w[i - 1]\), und dem vier Positionen zurückliegenden Wort, \(w[i - 4]\), ab.

• In drei von vier Fällen wird ein einfaches XOR verwendet.

• Für ein Wort dessen Position im Array \(w\) ein Vielfaches von 4 ist, wird die komplexere Funktion \(g\) angewandt.

AES Round Key Berechnung

AES Schlüsselexpansion - Begründung

• Die Rijndael-Entwickler haben den Expansionsschlüssel-Algorithmus so konzipiert, dass er gegen bekannte kryptoanalytische Angriffe resistent ist.

• Die Einbeziehung einer rundenabhängigen Rundenkonstante beseitigt die Symmetrie, die sonst bei der Erzeugung der Rundenschlüssel in den verschiedenen Runden entstehen würde.

Äquivalente inverse Chiffre

Zwei unabhängige, separate Änderungen sind erforderlich, um die Entschlüsselungsstruktur mit der Verschlüsselungsstruktur in Einklang zu bringen:

1. Die ersten beiden Stufen der Entschlüsselungsrunde müssen vertauscht werden.

2. Die zweiten beiden Stufen der Entschlüsselungsrunde müssen vertauscht werden.

Vertausch von InvShiftRows und InvSubBytes

InvShiftRows:

beeinflusst die Reihenfolge der Bytes im Zustand (State), ändert aber nicht den Inhalt der Bytes und ist nicht vom Inhalt der Bytes abhängig, um seine Transformation durchzuführen.

InvSubBytes:

beeinflusst den Inhalt von Bytes im Zutand (State), ändert aber nicht die Byte-Reihenfolge und hängt nicht von der Byte-Reihenfolge ab, um seine Transformation durchzuführen.

Vertausch von AddRoundKey und InvMixColumns

• Die Transformationen AddRoundKey und InvMixColumns ändern die Reihenfolge der Bytes im Zustand (State) nicht.

• Betrachtet man den Schlüssel als eine Folge von Wörtern, so wirken sowohl AddRoundKey als auch InvMixColumns jeweils nur auf eine Spalte des Zustands (State).

• Diese beiden Operationen sind linear in Bezug auf die gegebene Spalte.

  Das heißt, für einen bestimmten Zustand \(S_i\) und einen bestimmten Rundenschlüssel \(w_j\):

  \begin{equation*} InvMixColumns(S_i \oplus w_j) = InvMixColumns(S_i) \oplus InvMixColumns(w_j) \end{equation*}

Aspekte der Umsetzung auf 8-bit Prozessoren

AES kann sehr effizient auf einem 8-Bit-Prozessor implementiert werden:

AddRoundKey:

ist eine byteweise XOR-Operation.

ShiftRows:

ist eine einfache Byte-Verschiebeoperation.

SubBytes:

arbeitet auf Byte-Ebene und benötigt nur eine Tabelle von 256 Bytes.

MixColumns:

erfordert eine Matrixmultiplikation im Körper \(GF(2^8)\), was bedeutet, dass alle Operationen mit Bytes durchgeführt werden.

Aspekte der Umsetzung auf 32-bit Prozessoren

AES kann effizient auf einem 32-Bit-Prozessor implementiert werden:

• Die einzelnen Schritte können so umdefiniert werden, dass sie 32-Bit-Wörter verwenden.

• Es ist möglich 4 Tabellen für die MixColumns Transformation mit je 256 Wörtern vorzuberechnen.

  • Dann kann jede Spalte in jeder Runde mit 4 Tabellen-Lookups + 4 XORs berechnet werden.

  • Die Kosten für die Speicherung der Tabellen belaufen sich auf 4Kb.

• Die Entwickler glauben, dass die Möglichkeit einer effizienten Implementierung ein Schlüsselfaktor für die Wahl der AES-Chiffre zum neuen Standard war.