path: root/buch/chapters/90-crypto/aes.tex

%
% aes.tex -- Beschreibung des AES Algorithmus
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Advanced Encryption Standard -- AES
\label{buch:section:aes}}
\rhead{Advanced Encryption Standard}
Eine wichtige Forderung bei der Konzeption des damals neuen
Advanced Encryption Standard war, dass darin keine ``willkürlich''
erscheinenden Operationen geben darf, bei denen der Verdacht
entstehen könnte, dass sich dahinter noch offengelegtes Wissen
über einen möglichen Angriff auf den Verschlüsselungsalgorithmus
verbergen könnte.
Dies war eine Schwäche des vor AES üblichen DES Verschlüsselungsalgorithmus.
In seiner Definition kommt eine Reihe von Konstanten vor, über deren
Herkunft nichts bekannt war.
Die Gerüchteküche wollte wissen, dass die NSA die Konstanten aus dem
ursprünglichen Vorschlag abgeändert habe, und dass dies geschehen sei,
um den Algorithmus durch die NSA angreifbar zu machen.

Eine weiter Forderung war, dass die Sicherheit des neuen
Verschlüsselungsstandards ``skalierbar'' sein soll, dass man also
die Schlüssellänge mit der Zeit von 128~Bit auf 196 oder sogar 256~Bit
steigern kann.
Der Standard wird dadurch langlebiger und gleichzeitig entsteht die
Möglichkeit, Sicherheit gegen Rechenleistung einzutauschen.
Weniger leistungsfähige Systeme können den Algorithmus immer noch
nutzen, entweder mit geringerer Verschlüsselungsrate oder geringerer
Sicherheit.

In diesem Abschnitt soll gezeigt werde, wie sich die im AES
spezifizierten Operationen mit der Arithmetik 
eines endlichen Körpers beschreiben lassen.
Im Abschnitt~\ref{buch:subsection:byte-operationen} werden
Bytes als Elemente in einem endlichen Körper $\mathbb{F}_{2^8}$
interpretiert.
Damit kann dann die sogenannte $S$-Box konstruiert werden und
es ist leicht zu verstehen, dass sie invertierbar ist.
Aus den Byte-Operationen können dann Mischoperationen erzeugt
werden, die Bytes untereinander verknüpfen, die aber auch wieder
als Operationen in einem endlichen Körper verstanden werden können.

\subsection{Byte-Operationen
\label{buch:subsection:byte-operationen}}
Moderne Prozessoren operieren auf Wörtern, die Vielfache von Bytes sind.
Byte-Operationen sind besonders effizient in Hardware zu realisieren.
AES verwendet daher als Grundelemente Operationen auf Bytes, die als
Elemente eines endlichen Körpers $\mathbb{F}_{2^8}$ interpretiert werden.

\subsubsection{Bytes als Elemente von $\mathbb{F}_{2^8}$}
Das Polynom $m(X)=X^8+X^4+X^3+X+1\in \mathbb{F}_2[X]$ ist irreduzibel,
somit ist $\mathbb{F}_{2^8} = \mathbb{F}_2[X]/(m)$ ein Körper.
Die Elemente können dargestellt werden als Polynome, das Byte
$\texttt{63}_{16}$ bekommt die Form
\[
p(X) = p_7X^7 + p_6X^6 + \dots + p_2X^2+p_1X + p_0,
\]
sie bestehen daher aus den $8$ Bits $p_7,\dots,p_0$.

Die Interpretation der Bytes als Elemente eines Körpers bedeutet,
dass jede Multiplikation mit einem nicht verschwindenden Byte 
invertierbar ist.
Ausserdem mischen diese Operationen die einzelnen Bits auf einigermassen
undurchsichtige, aber umkehrbare Art durcheinander, wie dies für ein
Verschlüsselungsverfahren wünschenswert ist.

\subsubsection{$S$-Box}
Für die Operation der $S$-Box wird wie folgt zusammengesetzt.
Zunächst wird ein Byte $x$ durch das zugehörige multiplikative
inverse Element
\[
x\mapsto \bar{x} = \begin{cases}
x^{-1}&\qquad \text{für $x\in \mathbb{F}_{2^8}^*$}\\
0     &\qquad \text{für $x=0$}
\end{cases}
\]
ersetzt.

Im zweiten Schritt betrachten wir $\mathbb{F}_{2^8}$ als einen
$8$-dimensionalen Vektorraum über $\mathbb{F}_2$.
Einem Polynom $p(X)=p_7X^7 + \dots + p_1X+p_0$ wird der Spaltenvektor
mit den Komponenten $p_0$ bis $p_7$ zugeordnet.

\begin{figure}
\centering
\includegraphics[width=\textwidth]{chapters/90-crypto/images/sbox.pdf}
\caption{Berechnung der Inversen der Matrix $A$ in der $S$-Box  des
AES-Algorithmus mit dem Gauss-Algorithmus
\label{buch:crypto:fig:sbox}}
\end{figure}

Eine lineare Transformation in diesem Vektorraum kann durch eine
$8\times 8$-Matrix in $M_8(\mathbb{F}_2)$ betrachtet werden.
In der $S$-Box wird die Matrix
\[
A=
\begin{pmatrix}
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{pmatrix},
\qquad
A^{-1}
=
\begin{pmatrix}
0&0&1&0&0&1&0&1\\
1&0&0&1&0&0&1&0\\
0&1&0&0&1&0&0&1\\
1&0&1&0&0&1&0&0\\
0&1&0&1&0&0&1&0\\
0&0&1&0&1&0&0&1\\
1&0&0&1&0&1&0&0\\
0&1&0&0&1&0&1&0
\end{pmatrix}
\]
verwendet.
Mit dem Gauss-Algorithmus, schematisch dargestellt in
Abbildung~\ref{buch:crypto:fig:sbox}, kann man die Inverse
bestimmen, die Multiplikation mit $A$ ist also eine invertierbare
Abbildung.

Der letzte Schritt ist dann wieder eine Addition von
$q(X)=X^7+X^6+X+1\in \mathbb{F}_{2^8}$, durch Subtraktion
von $q(X)$ invertiert werden kann.
Die $S$-Box-Operation kann also vektoriell geschrieben werden als
\[
	S(x) = A\overline{x}+q.
\]

Die Implementation ist möglicherweise mit einer Tabelle am schnellsten,
es sind ja nur 256 Bytes im Definitionsbereich der $S$-Box-Abbildung
und ebenso nur 256 möglich Werte.

\subsection{Block-Operationen
\label{buch:subsection:block-operationen}}
Die zu verschlüsselnden Daten werden in in Blöcke aufgeteilt, deren
Länge Vielfache von $32$ bit sind.
Die kleinste Blockgrösse ist 128\,Bit, die grösste ist 256\,Bit.
Die Bytes eines Blockes werden dann in einem Rechteck angeordnet
als
\begin{equation}
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 b_{0} & b_{4} & b_{8}  & b_{12} & b_{16} & b_{20} & b_{24} & b_{28} \\
 b_{1} & b_{5} & b_{9}  & b_{13} & b_{17} & b_{21} & b_{25} & b_{29} \\
 b_{2} & b_{6} & b_{10} & b_{14} & b_{18} & b_{22} & b_{26} & b_{30} \\
 b_{3} & b_{7} & b_{11} & b_{15} & b_{19} & b_{23} & b_{27} & b_{31} \\
\hline
\end{tabular}
\label{buch:crypto:eqn:block}
\end{equation}
für eine Blocklänge von 256\,Bits.



\subsubsection{Zeilenshift}
\begin{figure}
\centering
\includegraphics[width=\textwidth]{chapters/90-crypto/images/shift.pdf}
\caption{Zeilenshift in einem Block von 256 bits
\label{buch:crypto:fig:shift}}
\end{figure}
Die Verschlüsselung muss sicherstellen, dass die Bytes des Blockes
untereinander gut gemischt werden.
Die bisher beschriebenen Operationen operieren immer nur auf einzelnen
Bytes während
die im nächsten Abschnitt beschriebene Spalten-Mischoperation
nur auf Spalten wird.
Die Zeilenmischoperation permutiert die Zeilen in den vier Zeilen
eines Blocks zyklisch, die erste Zeile bleibt an Ort, die zweite
Zeile wird um ein Byte rotiert, die dritte um zwei und die letzte
um 3 Bytes, wie in Abbildung~\ref{buch:crypto:fig:shift}
dargestellt.
Diese Operation könnte mit einer Permutationsmatrix beschrieben werden,
dies wäre jedoch keine effiziente Implementation.
Der Zeilenschift hat ansonsten keine elegante algebraische Beschreibung.

\subsubsection{Spalten mischen}
Jede Spalte von \eqref{buch:crypto:eqn:block} kann als Vektor des
vierdimensionalen Vektorraumes $\mathbb{F}_{2^8}^4$ angesehen werden.
Die Zeilenmischoperation wendet ein lineare Abbildung auf jeden
Spaltenvektor von~\eqref{buch:crypto:eqn:block}.
Die Koeffizienten der Matrix sind Elemente von $\mathbb{F}_{2^8}$.
Die Matrix ist
\[
C=\begin{pmatrix}
\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\
\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}
\end{pmatrix}.
\]
Um nachzuprüfen, dass die Matrix $C$ invertierbar ist, könnte man den
Gauss-Algorithmus verwenden und damit die Inverse berechnen.
Dazu müsste man die multiplikativen Inversen kennen, was etwas mühsam
ist.
Man kann aber aber auch die Determinante bestimmen, dazu braucht man
nur multiplizieren zu können, was in diesem Fall sehr leicht möglich ist,
weil kein Überlauf entsteht.
Dabei hilft es zu beachten, dass die Multiplikation mit $\texttt{02}_{16}$
nur eine Einbit-Shiftoperation nach links ist.
Nur die Multiplikation $\texttt{03}_{16}\cdot\texttt{03}_{16}=\text{05}_{16}$
gibt etwas mehr zu überlegen.
Mit geeigneten Zeilen-Operationen kann man die Berechnung der Determinante
von $C$ mit dem Entwicklungssatz etwas vereinfachen.
Man erhält
\begin{align*}
\det(C)
&=
\left|
\begin{matrix}
\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
\texttt{00}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\
\texttt{00}_{16}&\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
\\
&=
\texttt{02}_{16}
\left|
\begin{matrix}
\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\
\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
+
\texttt{01}_{16}
\left|
\begin{matrix}
\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
\texttt{03}_{16}&\texttt{01}_{16}&\texttt{02}_{16}\\
\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
\\
&=
\texttt{02}_{16}
\left|
\begin{matrix}
\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\
\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
+
\texttt{01}_{16}
\left|
\begin{matrix}
\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
\texttt{00}_{16}&\texttt{00}_{16}&\texttt{01}_{16}\\
\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
\\
&=
\texttt{02}_{16}
\left(
\texttt{02}_{16}
\left|
\begin{matrix}
\texttt{02}_{16}&\texttt{03}_{16}\\
\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
+
\texttt{01}_{16}
\left|
\begin{matrix}
\texttt{03}_{16}&\texttt{01}_{16}\\
\texttt{03}_{16}&\texttt{02}_{16}
\end{matrix}
\right|
\right)
+
\texttt{01}_{16}
\left|
\begin{matrix}
\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
\texttt{00}_{16}&\texttt{03}_{16}&\texttt{02}_{16}\\
\texttt{00}_{16}&\texttt{00}_{16}&\texttt{01}_{16}
\end{matrix}
\right|
\\
&=
\texttt{02}_{16}
(
\texttt{02}_{16}(\texttt{04}_{16}+\texttt{05}_{16})
+
(\texttt{06}_{16}+\texttt{03}_{16})
)
+
\texttt{03}_{16}\texttt{03}_{16}
\\
&=
\texttt{02}_{16}
(
\texttt{02}_{16}
+
\texttt{05}_{16}
)
+
\texttt{05}_{16}
=
\texttt{0e}_{16}+\texttt{05}_{16}
=
\texttt{0a}_{16}
\ne 0.
\end{align*}
Damit ist gezeigt, dass die Matrix $C$ invertierbar auf den
Spaltenvektoren wirkt.
Die Inverse der Matrix kann einmal berechnet und anschliessend
für die Entschlüsselung verwendet werden.

Alternativ kann man die Multiplikation mit der Matrix $C$ auch
interpretieren als eine Polynommultiplikation.
Dazu interpretiert man die Spalten des Blocks als Polynom vom Grad~3
mit Koeffizienten in $\mathbb{F}_{2^8}$.
Durch Reduktion mit dem irreduziblen Polynom
$n(Z)=Z^4+1\in\mathbb{F}_{2^8}[X]$ entsteht aus dem Polynomring
wieder ein Körper.
Die Wirkung der Matrix $C$ ist dann nichts anderes als Multiplikation
mit dem Polynom
\[
c(Z) = \texttt{03}_{16}Z^3 + Z^2+Z^1+\texttt{02}_{16},
\]
die natürlich ebenfalls umkehrbar ist.

\subsection{Schlüssel
\label{buch:subsection:schlüssel}}
Die Byte- und Blockoperationen mischen die einzelnen Bits
der Daten zwar ganz schön durcheinander, aber es wird noch kein
Schlüsselmaterial eingearbeitet, welches den Prozess einzigartig
macht.

\subsubsection{Schlüsseladdition}
Nach jeder Spaltenmischoperation wird ein Rundenschlüssel
zum Blockhinzuaddiert.
Beim ersten Mal wird dazu einfach das vom Benutzer vorgegebene
Schlüsselmaterial verwendet.
Für die folgenden Runden muss aus diesem Schlüssel neues
Material, die sogenannten Rundenschlüssel, gewonnen werden.

\subsubsection{Rundenschlüssel}
\begin{figure}
\centering
\includegraphics{chapters/90-crypto/images/keys.pdf}
\caption{Erzeugung der erweiterten Schlüsseldaten aus dem Schlüssel
$K_0,\dots,K_7$ für Schlüssellänge 256\,bit.
Die mit $S$ beschrifteten Blöcke wenden die $S$-Box auf jedes einzelne
Byte an.
$\pi$ ist die zyklische Vertauschung der Bytes eines Wortes.
Die Operation $r_i$ ist eine Addition einer Konstanten, die in jeder
Runde anders ist.
\label{buch:crypto:fig:keys}}
\end{figure}
Die Erzeugung der Rundenschlüssel ist in Abbildung
\ref{buch:crypto:fig:keys}
schematisch dargestellt.
Die Blöcke beschreiben wieder Spaltenvektoren im vierdimensionalen
Raum $\mathbb{F}_{2^8}^4$.
Die Blöcke $K_0$ bis $K_7$ stellen den ursprünglichen Schlüssel dar.
Die Erzeugung eines neuen Blocks Schlüsselmatrial beginnt damit,
dass der letzte Vektor des vorangegangenblocks drei Operationen
unterworfen werden.
\begin{itemize}
\item
Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch:
\begin{center}
\begin{tikzpicture}[>=latex,thick]
\def\s{0.6}
\begin{scope}
\draw (0,0) rectangle (\s,{4*\s});
\foreach \y in {1,...,3}{
	\draw (0,{\y*\s}) (\s,{\y*\s});
}
\node at ({0.5*\s},{0.5*\s}) {$b_3$};
\node at ({0.5*\s},{1.5*\s}) {$b_2$};
\node at ({0.5*\s},{2.5*\s}) {$b_1$};
\node at ({0.5*\s},{3.5*\s}) {$b_0$};
\end{scope}
\draw[->] ({1.1*\s},{2*\s}) -- ({4.9*\s},{2*\s});
\node at ({3*\s},{2*\s}) [above] {$\pi$};
\begin{scope}[xshift=3cm]
\draw (0,0) rectangle (\s,{4*\s});
\foreach \y in {1,...,3}{
	\draw (0,{\y*\s}) (\s,{\y*\s});
}
\node at ({0.5*\s},{0.5*\s}) {$b_0$};
\node at ({0.5*\s},{1.5*\s}) {$b_3$};
\node at ({0.5*\s},{2.5*\s}) {$b_2$};
\node at ({0.5*\s},{3.5*\s}) {$b_1$};
\end{scope}
\end{tikzpicture}
\end{center}
\item
Die $S$-Operation wendet die $S$-Box auf alle Bytes eines Vektors an.
\item
Die $r_i$ Operation addiert in Runde $i$ eine Konstante $r_i$ zur $0$-Komponente.
\end{itemize}
Die Konstante $r_i$ ist wieder ein einzelnes Byte und es ist daher
naheliegend, diese Bytes mit Hilfe der Arithmetik in $\mathbb{F}_{2^8}$
zu erzeugen.
Man kann daher $r_i$ definieren als
$(\texttt{02}_{16})^{i-1}\in\mathbb{F}_{2^8}$.

\subsection{Runden}
Der AES-Verschlüsselungsalgorithmus besteht jetzt darin, die bisher
definierten Operationen wiederholt anzuwenden.
Eine einzelne Runde besteht dabei aus folgenden Schritten:
\begin{enumerate}
\item Wende die $S$-Box auf alle Bytes des Blocks an.
\item Führe den Zeilenshift durch.
\item Mische die Spalten (wird in der letzten Runde)
\item Erzeuge den nächsten Rundenschlüssel
\item Addiere den Rundenschlüssel
\end{enumerate}
Der AES-Verschlüsselungsalgorithmus beginnt damit, dass der Schlüssel
zum Datenblock addiert wird.
Anschliessend werden je nach Blocklänge verschiedene Anzahlen von
Runden durchgeführt, 10 Runden für 128\,bit, 12 Runden für 192\,bit und
14 Runden für 256\,bit.