Klausurvorbereitung 3 – Advanced Encryption Standard (AES)

 

Prinzipieller Aufbau:

advanced-encryption-standard-aufbau-funktion-diagramm

Die Funktion der einzelnen Blöcke muss bekannt sein. Der Algorithmus für die Schlüsselerzeugung muss nicht bekannt sein.

AddRoundKey führt die Operation XOR für die State-Matrix mit dem Rundenschlüssel durch.

SubBytes führt eine Substitution der Bytes der State-Matrix durch (monoalphabetische Chiffre). Wird meist nicht gerechnet, sondern aus Tabelle mit allen 256 möglichen Bytes ausgelesen.

ShiftRows verschiebt die Zeilen unterschiedlich weit nach links. Eselsbrücke: Zeilen mit 0 bis 3 durchnummerieren. Zeile 0 wird um 0 Stellen nach links verschoben, Zeile 1 um eine Stelle, Zeile 2 um zwei Stellen und Zeile 3 um drei Stellen.

Beispiel:

\left( {\begin{array}{*{20}{c}}{FE} & {01} & {02} & {AB} \\{AB} & {03} & {34} & {C1} \\{05} & {5B} & {71} & {D3} \\{07} & {CF} & {87} & {9E} \\ \end{array} } \right)\quad \mapsto \quad \left( {\begin{array}{*{20}{c}}{FE} & {01} & {02} & {AB} \\{03} & {34} & {C1} & {AB} \\{71} & {D3} & {05} & {5B} \\{9E} & {07} & {CF} & {87} \\ \end{array} } \right)

MixColumns fasst die 4 Bytes einer Spalte zusammen, um ein Byte zu berechnen. Dies funktioniert mit der Abbildung:

mix-columns-advanced-encryption-standard-aes

Die einzelnen Multiplikationen sind dabei Polynommultiplikationen. Beispiel:

{s_0} = \left( {\begin{array}{*{20}{c}}{AF} \\{01} \\{05} \\{CE} \\ \end{array} } \right)\quad \Rightarrow \quad s_{0,0}^\prime = 02 \cdot AF+03 \cdot 01+01 \cdot 05+01 \cdot CE

Multiplikation mit 01 ändert nichts. Multiplikation mit 02 entspricht einer Verschiebung um eine Stelle nach links. Multiplikation mit 03 entspricht einer Verschiebung um eine Stelle nach links und einer anschließenden Addition des ursprünglichen Wertes.

3.1 SubBytes (Prüfung FT 2009, Aufgabe 3b)

Betrachtet wird der Advanced Encryption Standard (AES). Welche Ausgabe erzeugt die Funktion SubBytes für das Eingabe-Byte b = 00100011?

Lösung 3.1

Wichtig: Das most significant Bit (MSB) steht ganz links! Wir erhalten:

b = {00100011_2} = {23_{16}}

\overset{\wedge}{=}0 \cdot {x^7}+0 \cdot {x^6}+1 \cdot {x^5}+0 \cdot {x^4}+0 \cdot {x^3}+0 \cdot {x^2}+1 \cdot {x^1}+1 \cdot {x^0}

= {x^5}+x+1 = b\left( x \right)

Das weitere Vorgehen besteht nun im Invertieren mit dem euklidischem Algorithmus (Polynomdivision) und dem erweiterten euklidischer Algorithmus.

Invertieren modulo m\left( x \right) = {x^8}+{x^4}+{x^3}+x+1 mit euklidischem Algorithmus:

m\left( x \right) = {q_1}\left( x \right)b\left( x \right)+{r_1}\left( x \right)

b\left( x \right) = {q_2}\left( x \right){r_1}\left( x \right)+{r_2}\left( x \right)

{r_1}\left( x \right) = {q_3}\left( x \right){r_2}\left( x \right)+{r_3}\left( x \right)

\vdots

Um die einzelnen Polynome q und r zu bestimmen, müssen Polynomdivisionen durchgeführt werden:

aes-subbytes-polynomdivision

Der Rest ist 1, daher wird der nächste Rest 0 sein, wir brechen den Algorithmus ab.
Erweiterter euklidischer Algorithmus:

1 = \left( {{x^4}+{x^3}+{x^2}+x} \right)\left( {x+1} \right)+\left( {{x^5}+x+1} \right)

1 = \left( {{x^4}+{x^3}+{x^2}+x} \right)\left[ {m\left( x \right)+{x^3}\left( {{x^5}+x+1} \right)} \right]+\left( {{x^5}+x+1} \right)

1 = {q_2}\left( x \right)m\left( x \right)+\left( {{x^5}+x+1} \right)\left( {{x^7}+{x^6}+{x^5}+{x^4}} \right)+\left( {{x^5}+x+1} \right)

1 = {q_2}\left( x \right)m\left( x \right)+\left( {{x^5}+x+1} \right)\left( {{x^7}+{x^6}+{x^5}+{x^4}+1} \right)

Modulo m\left( x \right):

1 = \left( {{x^5}+x+1} \right)\left( {{x^7}+{x^6}+{x^5}+{x^4}+1} \right)\bmod m\left( x \right)

\quad \Rightarrow \quad {b^{-1}}\left( x \right) = 11110001

Es muss nicht auswendig gelernt werden: Polynom m\left( x \right), affine Abbildung mit der Matrix.

Fehlerquelle in Klausur 2009: Einsetzen von {b^{-1}}\left( x \right) in affine Abbildung:

\left( {\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{array} } \right)\left( {\begin{array}{*{20}{c}} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \\ \uparrow \\ \end{array} } \right) \oplus \left( {\begin{array}{*{20}{c}} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{array} } \right) = 00100110 = {26_{16}}

Leserichtung von {b^{-1}}\left( x \right) beachten!

3.2 Key-Whitening (Übung 5. 5)

Gegeben sei eine Blockchiffre {F_K}:\mathbb{Z}_2^n \to \mathbb{Z}_2^n,\quad n \in \mathbb{N}, mit Schlüssel K \in \mathbb{Z}_2^m,\quad m \in \mathbb{N}. Stellen Sie in einem Blockschaltbild dar, wie die Blockchiffre mittels „Key Whitening“ gegen vollständige Schlüsselsuche gehärtet werden kann.

Lösung 3.2

key-whitening-advanced-encryption-standard

Key Whitening erhöht die Sicherheit iterierter Blockchiffren. Bei einer Verschlüsselung mit Whitening wird ein Klartextblock vor der ersten Runde mit Teilen des Schlüssels verknüpft (Pre-Whitening); zumeist wird hier XOR verwendet. Einige Chiffren verwenden Whitening zudem auch nach der letzten Runde (post-Whitening). Das Whitening dient vor allem bei Feistelchiffren dazu, Strukturen des Klartexts und der Eingabe der letzten Runde zu verschleiern und so die Komplexität eines Angriffs zu erhöhen.

Beispiele für Chiffren mit Whitening sind RC5, RC6, MARS, Twofish und Rijndael.

3.3 Subbytes 2 (Übung 5.6)

Betrachtet wird das AES-Kryptosystem. Berechnen Sie die Ausgabe der Funktion „SubBytes“ für das Byte b = 0000\;0011.

Lösung 3.3

b = 0000\;0011 \overset{\wedge}{=}x+1

Invertieren modulo m\left( x \right) = {x^8}+{x^4}+{x^3}+x+1 mit euklidischem Algorithmus:

m\left( x \right) = {q_1}\left( x \right)b\left( x \right)+{r_1}\left( x \right)

b\left( x \right) = {q_2}\left( x \right){r_1}\left( x \right)+{r_2}\left( x \right)

{r_1}\left( x \right) = {q_3}\left( x \right){r_2}\left( x \right)+{r_3}\left( x \right)

\vdots

Polynomdivision:

aes-subbytes-polynomdivision

Erweiterter euklidischer Algorithmus:

1 = \underbrace {{x^8}+{x^4}+{x^3}+x+1}_{m\left( x \right)}+\left( {{x^7}+{x^6}+{x^5}+{x^4}+{x^2}+x} \right)\left( {x+1} \right)\quad |\bmod m\left( x \right)

\Rightarrow \quad 1 \equiv \underbrace {\left( {{x^7}+{x^6}+{x^5}+{x^4}+{x^2}+x} \right)}_{{b^{-1}}}\underbrace {\left( {x+1} \right)}_b

\Rightarrow \quad {b^{-1}} = 0111\;{10110_2}

A{b^{-1}} \oplus c = \left( {\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{array} } \right)\left( {\begin{array}{*{20}{c}} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{array} } \right) \oplus \left( {\begin{array}{*{20}{c}} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ \end{array} } \right)

= 7{B_{16}}

Das + bei der Matrizenmultiplikation wird einfach durch \oplus ersetzt.

3.4 SubBytes und Key-Whitening (Prüfung WT 2010, Aufgabe 4)

  1. Welche Ausgabe erzeugt die Funktion SubBytes für das Byte b = 0100\;1101? (4P)
  2. Stellen Sie dar, wie die Anzahl der Schlüsselbits von AES-128 mittels Key-Whitening erhöht werden kann (2P)

Lösung 3.4

a)

b = 0100\;{1101_2} = 4{D_{16}} \overset{\wedge}{=}{x^6}+{x^3}+{x^2}+1

Invertieren modulo m\left( x \right) = {x^8}+{x^4}+{x^3}+x+1 mit euklidischem Algorithmus:

m\left( x \right) = {q_1}\left( x \right)b\left( x \right)+{r_1}\left( x \right)

b\left( x \right) = {q_2}\left( x \right){r_1}\left( x \right)+{r_2}\left( x \right)

{r_1}\left( x \right) = {q_3}\left( x \right){r_2}\left( x \right)+{r_3}\left( x \right)

\vdots

Polynomdivision:

{x^8}+{x^4}+{x^3}+x+1 = \left( {{x^2}} \right)\left( {{x^6}+{x^3}+{x^2}+1} \right)+\left( {{x^5}+{x^3}+{x^2}+x+1} \right)

\underline {{x^8}+{x^5}+{x^4}+{x^2}}

\qquad {x^5}+{x^3}+{x^2}+x+1

{x^6}+{x^3}+{x^2}+1 = \left( x \right)\left( {{x^5}+{x^3}+{x^2}+x+1} \right)+\left( {{x^4}+x+1} \right)

\underline {{x^6}+{x^4}+{x^3}+{x^2}+x}

\qquad {x^4}+x+1

{x^5}+{x^3}+{x^2}+x+1 = \left( x \right)\left( {{x^4}+x+1} \right)+\left( {{x^3}+1} \right)

\underline {{x^5}+{x^2}+x}

\qquad {x^3}+1

{x^4}+x+1 = \left( x \right)\left( {{x^3}+1} \right)+\left( 1 \right)

\underline {{x^4}+x}

\qquad 1

Erweiterter euklidischer Algorithmus:

1 = \left( {{x^4}+x+1} \right)+x\left( {{x^3}+1} \right)

\Rightarrow \quad 1 = \left( {{x^4}+x+1} \right)+x\left[ {\left( {{x^5}+{x^3}+{x^2}+x+1} \right)+x\left( {{x^4}+x+1} \right)} \right]

\Rightarrow \quad 1 = \left( {{x^2}+1} \right)\left( {{x^4}+x+1} \right)+x\left( {{x^5}+{x^3}+{x^2}+x+1} \right)

\Rightarrow \quad 1 = \left( {{x^2}+1} \right)\left[ {\left( {{x^6}+{x^3}+{x^2}+1} \right)+x\left( {{x^5}+{x^3}+{x^2}+x+1} \right)} \right]

+x\left( {{x^5}+{x^3}+{x^2}+x+1} \right)

\Rightarrow \quad 1 = \left( {{x^2}+1} \right)\left( {{x^6}+{x^3}+{x^2}+1} \right)+{x^2}x\left( {{x^5}+{x^3}+{x^2}+x+1} \right)

\Rightarrow \quad 1 = \left( {{x^2}+1} \right)\left( {{x^6}+{x^3}+{x^2}+1} \right)

+{x^3}\left[ {\left( {{x^8}+{x^4}+{x^3}+x+1} \right)+{x^2}\left( {{x^6}+{x^3}+{x^2}+1} \right)} \right]

\Rightarrow \quad 1 = \left( {{x^5}+{x^2}+1} \right)\left( {{x^6}+{x^3}+{x^2}+1} \right)

+{x^3}\left( {{x^8}+{x^4}+{x^3}+x+1} \right)\quad |\bmod m\left( x \right)

\Rightarrow \quad 1 \equiv \underbrace {\left( {{x^5}+{x^2}+1} \right)}_{ = {b^{-1}}}\underbrace {\left( {{x^6}+{x^3}+{x^2}+1} \right)}_{ = b}

\Rightarrow \quad {b^{-1}} = 0010\;0101

A{b^{-1}} \oplus c = \left( {\begin{array}{*{20}{c}} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{array} } \right)\left( {\begin{array}{*{20}{c}} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ \end{array} } \right) \oplus \left( {\begin{array}{*{20}{c}} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ \end{array} } \right)

= E{3_{16}}

b)

Siehe 3.2

SubBytes-Tabelle zur Kontrolle:

aes-subbytes-tabelle-table