\chapter{Blockverschlüsselungsverfahren}\label{Blockverschlüsselungsverfahren}
    Ein Verschlüsselungsverfahren wird als Blockverschlüsselungsverfahren bezeichnet, 
    wenn die Menge der Nachrichten $\mathscr M$ durch die Menge der Blöcker einer festen Länge $n\in \mathbb{N}$ gegeben ist:
    $$\mathscr M := ({\mathbb{Z}_2}^8)^n = \{(z_1,z_2,...,z_n)\mid z_i\in{\mathbb{Z}_2}^8\}$$
    \textbf{Wichtig}\\
    \begin{itemize}
        \item Häufig wird für Blöcke die aus $n$ Bytewerten die Blocklänge in Bits (Blocklänge$=n\cdot 8$) angegeben
        \item Die Menge der Blöcke $\mathscr M$ kann als Vektorraum über $\mathbb{Z}_2$ aufgefasst werden. 
            Hierbei wird die Summe von zwei Blöcken $m_1,m_2\in\mathscr M$ durch eine bitweise Addition definiert, welcher einer Bitweisen XOR-Verknüpfung ($\oplus$) entspricht.
        \item Da sich die Vektoren aus ${\mathbb{Z}_2}^{8\cdot n}$ in Zahlen aus $\mathbb{Z}_{2^{8\cdot n}}$ umrechnen lassen könnte man sie auch auf diese Art addieren.
            Hierbei erhält man allerdings ein deutlich anderes Ergebnis als bei XOR-Addition.
            Aus diesem Grund wird in diesem Fall das Symbol $\boxplus$ verwendet. 
    \end{itemize}

    \section{Padding-Verfahren}
        Damit Daten beliebiger Länge mit einem Blockverschlüsselungsverfahren verschlüsselt werden können muss die Nachricht auf ein Vielfaches der Blocklänge aufgestockt werden.
        Man spricht von Padding.
        Um dem Empfänger mitzuteilen, welche übertragenen Daten zum Padding und nicht zur Nachricht gehören gibt es mehrere Möglichkeiten:
        \begin{itemize}
            \item Die Anzahl der Padding-Bytes wird mit übertragen
            \item Als Paddingbytes werden Zeichen verwendet, die nicht in die Kodierung passen (z.B. 0x00 bei ASCII)
            \item Es findet immer Padding statt (bei passender Nachrichtenlänge ist der ganze letzte Block Padding), wobei im Padding die Paddinglänge kodiert ist.
        \end{itemize}
    
    \section{Betriebsmodi}
        Es gibt eine Vielzahl von Betriebsmodi, die für die Blockverschlüsselung verwendet werden.
        Auf diese wird im Folgenden eingegangen

        \subsection{ECB (Electronic Code Book)}
            Im ECB-Modus wir mit dem Verschlüsselungsverfahren $E$ jedes Tupel von Blöcken blockweise verschlüsselt:
            $$E_k((m_1,...,m_r)) := (E_k(m_1),...,E_k(m_r))$$
            eine auf diese Weise verschlüsselte Nachricht kann ebenfalls Blockweise entschlüsselt werden:
            $$D_k((c_1,...,c_r)) := (D_k(c_1),...,D_k(c_r))$$
            \includegraphics{ECB.png}\\
            Da diese Modus anfällig für Wörterbuchangriffe ist wird häufig ein Nonce-Wert verwendet, der jeweils mit dem Klartextblock addiert ($\oplus$) wird:\\
            \includegraphics{ECB_Nonce.png}

        \subsection{CBC (Cipher Block Chaining)}\label{CBC}
            Der CBC-Modus ist eine spezielle Form des ECB-Modus, bei dem der errechnete Geheimtextblock als Nonce-Wert für die Verschlüsselung des nächsten Blocks verwendet wird.
            Hierbei wird der erste Nonce-Wert $c_0$ durch einen Initialisierungsvektor $IV\in\mathscr M$ gegeben.
            $$\begin{aligned}
                c_i:=&E_k(m_i+c_{i-1})\\
                E_{k,IV}(m_1,...,m_r) :=&(c_1,...,c_r)
            \end{aligned}$$
            \includegraphics{CBC_enc.png}\\
            Bei der Entschlüsselung wird wie folgt vorgegangen:
            $$\begin{aligned}
                m_i :=&D_k(c_i)+c_{i-1}\\
                D_{k,IV}(c_1,...,c_r):=&(m_1,...,m_r)
            \end{aligned}$$
            \includegraphics{CBC_dec.png}

        \subsection{CBC-CS (Chiphertext Stealing for CBC Mode)}
            Der CBC-CS-Modus wird auch als CTS-Modus (Chiphertext Stealing Mode) bezeichnet.
            Dieser Modus basiert auf dem CBC-Modus (siehe \ref{CBC}), erlaubt aber eine Verschlüsselung von Nachrichten mit beliebiger Länge (ohne Padding).
            Um das Padding zu umgehen gibt es mehrere Varianten:

            \subsubsection{CBC-CS1}
                Bei der Variante 1 der CBC-CS-Verschlüsselung wird der letzte Block $m^*_r$ der Nachricht mit 00-Bytes auf die Blocklänge aufgefüllt (00-Padding).
                Anschließend wird die Nachricht inkl. dem gepaddeten Block $m_r$ mit dem CBC-Verfahren (siehe \ref{CBC}) verschlüsselt.
                Um wieder auf die ursprüngliche Länge der Nachricht zu kommen werden aus dem vorletzten Block $c_{r-1}$ des Geheimtextes die gleiche Anzahl Bytes entfernt, die zu $m^*_r$ hinzugefügt wurden.
                Hierdurch ergibt sich die Geheimtextnachricht $c_1,...,c_{r-2},c^*_{r-1},c_r$, die die gleiche Länge wie $m$ hat.\\
                Wenn die Länge der Nachricht $m$ ein Vielfaches des Blocklänge $l$ ist wird das normale CBC-Verschlüsselungsverfahren angewandt.
            
            \subsubsection{CBC-CS2}
                Bei der Variante 2 der CBC-CS-Verschlüsselung wird auf die gleiche Weise vorgegangen, wie bei Variante 1.
                Allerdings werden, \textbf{falls} ein Padding notwendig ist nach der Verschlüsselung und dem Stealing die letzten beiden Blöcke vertauscht.
                $$E-CBC-CS2_{k,IV}(m_1,...,m_{r-1},m^*_r) := (c_1,...,c_r,c^*_{r-1})$$
                Wenn die Länge der Nachricht $m$ ein Vielfaches des Blocklänge $l$ ist wird das normale CBC-Verschlüsselungsverfahren angewandt.

            \subsubsection{CBC-CS3}
                Die Variante 3 der CBC-CS-Verschlüsselung unterscheidet sich nur darin von der Variante 2, dass immer die letzten beiden Blöcke vertauscht werden.
                Dies geschieht ungeachtet davon, ob die Länge der Nachricht $m$ ein Vielfaches der Blocklänge $l$ ist.
            
        \subsection{CTR (Counter)}
            Im CTR-Modus wird ein Blockverschlüsselungsverfahren $E$ mit einem Schlüssel $k$ und einem Nonce-Wert $Ctr\in\mathscr M$ wie folgt verwendet: 
            $$\begin{aligned}
                c_i :=&m_i+E_k(Ctr\boxplus(i-1))\\
                E-CTR_{k,Ctr}(m_1,...,m_r):=&(c_1,...,c_r)
            \end{aligned}$$ 
            Der CTR-Modus definiert ein synchrones  additives Stromverschlüsselungsverfahren (siehe \ref{synchron additive Stromverschlüsselung}). 
            Die Menge der $z_i=E_k(Ctr\boxplus(i-1))$ definiert hierbei den Schlüsselstrom.\\ 
            Aufgrund dessen ist die Entschlüsselungsfunktion $D$ gleich der Verschlüsselungsfunktion $E$:
            $$D-CTR_{k,Ctr}(c_1,...,c_r)=E-CTR_{k,Ctr}(c_1,...,c_r)$$
            \includegraphics{CTR.png}

        \subsection{OFB (Output Feedback)}\label{OFB}
            Bei der Konstruktion im OFB-Modus handelt es sich um ein synchrones Stromverschlüsselungsverfahren (siehe \ref{synchrone Stromverschlüsselung})
            Hierbei wird die Ausgabe der Verschlüsselungsfunktion jeweils als Eingabe für die nächste Verschlüsselungsfunktion genutzt:\\
            \includegraphics{OFB.png}\\

            \subsubsection{OFB-8$n$}
                bei dieser Variante des des OFB-Modus werden immer nur $n\in\mathbb{N}$ Bytes des verschlüsselten Blocks in der XOR-Verknüpfung genutzt.
                Der Rest des Klartextblocks wird in den folgenden Schritten verschlüsselt.
                $n$ darf hierbei maximal so groß wie die Blocklänge $l$ der Verschlüsselungsfunktion $E$ sein.        

        \subsection{CFB (Cipher-Feedback)}
            Der CFB-Modus hat viele Ähnlichkeiten mit dem OFB-Modus (siehe \ref{OFB}).
            Allerdings wird hierbei immer der verschlüsselte Block als Eingabe für die jeweils nächste Verschlüsselungsfunktion genutzt.
            Anders als beim OFB-Modus handelt es sich beim CFB-Modus aufgrund der Nutzung der Geheimtextblöcke nicht um eine synchrone Stromverschlüsselung.\\
            \includegraphics{CFB.png}

            \subsubsection{CFB-8$n$}
                Diese Sonderfunktion des CFB-Modus stellt das Pendant zum OFB-8$n$-Modus im OFB-Modus (siehe \ref{OFB}) dar.
    \section{Konstruktionsprinzipien von Blockverschlüsselungsverfahren}
        Alle Blockverschlüsselungsverfahren führen innerhalb des jeweiligen Blocks Permutationen aus.
        Diese Permutationen werden in Schleifen (Runden) angewandt.
        Die Permutationen können in folgende elementare Operationen zusammengefasst werden:
        \begin{itemize}
            \item \textit{Transpositionen} von Bitwerten innerhalb eines Blocks
            \item \textit{Substitution} von Werten innerhalb kleinerer Teilblöcke. 
                Hierbei handelt es sich um eine Abbildung, welche durch eine Rechenvorschrift oder eine Wertetabelle gegeben werden kann.
                Wertetabellen werden in diesem Zusammenhang auch als \textit{S-Boxen} bezeichnet.
        \end{itemize}
        Zudem findet der Schlüssel $k$ ebenfalls eine Berücksichtigung.
        Aus ihm werden Rundenschlüssel $k_i$ mit $i\in\{1,...,r\}$ abgeleitet, welche bei jeder Runde mit in die Berechnung einfließen.
        Bei einer Entschlüsselung wird das durch die Runden beschriebene Verfahren einfach rückwärts angewandt.

    \section{DES}
        Das einfach DES wurde 1977 veröffentlicht und 2005 zurückgezogen.
        Sowohl die Blöcke als auch die Schlüssel setzten sich jeweils aus 8 Bytes zusammen:
        $$\begin{aligned}
            \mathscr M=&({\mathbb{Z}_2}^8)^8=\{(m_1,...m_8)\mid m_i\in{\mathbb{Z}_2}^8\}\\
            \mathscr K=&\{(k_1,...k_8)\mid k_i\in{\mathbb{Z}_2}^8,\text{parity}(k_i)=1\}\subseteq ({\mathbb{Z}_2}^8)^8
        \end{aligned}$$
        Die Parität ist definiert durch:
        $${\mathbb{Z}_2}^8\rightarrow\mathbb{Z}_2 \hspace{5mm} \text{parity}\left(\sum_{i=0}^7 b_i\cdot 2^i\right)=\left(\sum_{i=0}^7 b_i\right)\mod 2$$
        Mit anderen Worten: \say{Die Anzahl der 1-Bits im Byte muss ungerade sein}\\
        Durch die Parität ist der Wert des achten Bits schon festgelegt.
        Aufgrund dessen ist hat der Schlüsselraum eine Bitlänge von $8\cdot 7=56$.
        Da dies für moderne PCs mithilfe eines Brute-Force-Angriffs (siehe \ref{brute-force}) in trivialer Zeit zu knacken ist sollte DES nicht mehr verwendet werden.

        \subsection{Triple-DES (3DES)}
            Beim Triple-DES wird das DES verfahren 3mal hintereinander ausgeführt.
            Üblicherweise im EDE-Modus (Encrypt-Decrypt-Encrypt) mit 16Byte langen Schlüsseln.
            Dadurch ergibt sich für den Schlüsselraum eine effektive Länge von 112 Bits.
            Die Menge der 8-Byte-langen Blöcke und der Schlüsselraum definieren sich wie folgt:
            $$\begin{aligned}
                \mathscr M=&({\mathbb{Z}_2}^8)^8=\{(m_1,...m_8)\mid m_i\in{\mathbb{Z}_2}^8\}\\
                \mathscr K=&\{(k_1,...k_8)\mid k_i\in{\mathbb{Z}_2}^8,\text{parity}(k_i)=1\}^{\color{red}{\mathbf{2}}}
            \end{aligned}$$ 
            Die 3-DES Entschlüsselungsfunktion definiert sich durch:
            $$E((k^{(1)},k^{(2)},m)) := E_{DES}\left(k^{(1)},D_{DES}\left(k^{(2)},E_{DES}\left(k^{(1)},m \right)\right)\right)$$
            \includegraphics[scale=0.8]{3DES.png}

    \section{Meet-in-the-Middle-Angriff}\label{meet-in-the-middle}
        Aufgrund des Meet-in-the-Middle-Angriffs führt eine \textbf{zweifache} Hintereinanderreihung von Verschlüsselungsfunktionen nur zu einer kleinen Vergrößerung des Schlüsselraums.
        Bei diesem Angriff handelt es sich um einen known-plaintext-Angriff (siehe \ref{known-plaintext}).
        Es wird angenommen, dass es ein $2E_{k_1,k_2}$ verfahren gibt, dass sich wie folgt definiert:\\
        \includegraphics{meet-in-the-middle.png}\\
        Es wird zudem angenommen, dass genügend Speicher zur Verfügung steht um alle $\tilde{k}_1\in\mathscr K$ zusammen mit den jeweiligen $c_{\tilde{k}_1}(m_1):=E(\tilde{k}_1,m_1)$ in eine Tabelle zu schreiben:
        \begin{center}
            \begin{tabular}{c|c}
                $\tilde{k}_1$ & $c_{\tilde{k}_1}(m_1):=E(\tilde{k}_1,m_1)$\\
                \hline
                0101010101010101 & 8A549EC56733AB66\\
                0101010101010102 & 653148AE6B688132\\
                \vdots & \vdots \\
                FEFEFEFEFEFEFEFE & CE55464B6485684E
            \end{tabular}
        \end{center}
        Anschließend wird die Tabelle nach der zweiten Spalte sortiert.
        Beim Ausprobieren alle Möglichkeiten von $\tilde{k}_2 \in\mathscr K$ kann für $D_{\tilde{k}_2}(c_1)$ nachgeschlagen werden, ob sich dieser in der Tabelle befindet.
        Hierdurch ergeben sich dann $(\tilde{k}_1,\tilde{k}_2)$ Paare, für die gilt:
        $$2E_{\tilde{k}_1,\tilde{k}_2}(m_{\color{red}{\mathbf{1}}})=c_{\color{red}{\mathbf{1}}}$$
        Durchschnittlich ist mit $1+\frac{|\mathscr K|}{|\mathscr M|}$ solcher Paare zu rechnen.
        Die Paare können nun durch Ausprobieren der anderen bekannten Nachrichten $\{m_i\setminus m_1\}$ schnell ausgeschlossen werden.

    \section{AES (Advanced Encryption Standard)}\label{aes}
        Der AES ist für Schlüssel mit den Bitlängen 128, 192 und 256 definiert.
        Im folgenden wird AES-128 als Synonym für alle möglichen Schlüssellängen verwendet.

        \subsection{AES-128}
            Sowohl die Blöcke als auch die Schlüssel setzen sich aus jeweils 16 Bytes zusammen:
            $$\begin{aligned}
                \mathscr M =& ({\mathbb{Z}_2}^8)^{16}=\{(m_1,...m_{16})\mid m_i\in{\mathbb{Z}_2}^8\}\\
                \mathscr K =& ({\mathbb{Z}_2}^8)^{16}=\{(k_1,...k_{16})\mid k_i\in{\mathbb{Z}_2}^8\}\\
            \end{aligned}$$
            Blöcke werden in Form von Matrizen dargestellt, die als State-Array bezeichnet werden:
            $$S=\begin{pmatrix}
                s_{0,0} & s_{0,1} &s_{0,2} &s_{0,3}\\
                s_{1,0} & s_{1,1} &s_{1,2} &s_{1,3}\\
                s_{2,0} & s_{2,1} &s_{2,2} &s_{2,3}\\
                s_{3,0} & s_{3,1} &s_{3,2} &s_{3,3}\\
            \end{pmatrix}:=\begin{pmatrix}
                m_1 &m_5 & m_9 & m_{13}\\
                m_2 &m_6 & m_{10} & m_{14}\\
                m_3 &m_7 & m_{11} & m_{15}\\
                m_4 & m_8 & m{12} & m_{16}
            \end{pmatrix}$$
            \vspace{5mm}
            Im AES gibt es 4 elementare Operationen auf den State-Arrays:
            \begin{enumerate}
                \item SubBytes()\\
                    Es wird auf Basis der folgenden Tabelle eine Substitution von jedem Element des State-Arrays durchgeführt.\\
                    \includegraphics[scale=0.8]{AES S-Box.png}
                \item ShiftRows()\\
                    auf dem S-Array  wird die folgende Transposition durchgeführt:
                    $$\begin{pmatrix}
                        s_{0,0} & s_{0,1} &s_{0,2} &s_{0,3}\\
                        s_{1,0} & s_{1,1} &s_{1,2} &s_{1,3}\\
                        s_{2,0} & s_{2,1} &s_{2,2} &s_{2,3}\\
                        s_{3,0} & s_{3,1} &s_{3,2} &s_{3,3}\\
                    \end{pmatrix}
                    \mapsto
                    \begin{pmatrix}
                        s_{0,0} & s_{0,1} &s_{0,2} &s_{0,3}\\
                        s_{1,1} & s_{1,2} &s_{1,3} &s_{1,0}\\
                        s_{2,2} & s_{2,3} &s_{2,0} &s_{2,1}\\
                        s_{3,3} & s_{3,0} &s_{3,1} &s_{3,2}\\
                    \end{pmatrix}$$
                \item MixColumns()\\
                    auf dem S-Array wird eine Substitution ausgeführt, die durch die folgende Multiplikation definiert ist:
                    $$S\mapsto M\cdot S\hspace{5mm} \text{mit }M=
                    \begin{pmatrix}
                        02 & 03& 01& 01\\
                        01 & 02 & 03 & 01 \\
                        01 & 01 & 02 & 03 \\
                        03 & 02 & 01 & 02 \\
                    \end{pmatrix}$$
                    Hierbei ist wichtig anzumerken, dass die Multiplikation nicht in $\mathbf{Z}_{256}$ berechnet wird.
                    Stattdessen sind die Elemente als Elemente des Körpers $\mathbf{F}_{256}$ aufzufassen,
                    der bezüglich des irreduziblen Polynoms $m(x)=x^8+x^4+x^3+x+1\in\mathbb{F}_2[x]$ definiert ist.
                \item AddRoundKey()\\
                    Es wird eine XOR-Operation der Einträge des S-Arrays mit den entsprechenden Einträgen aus \textbf{K} durchgeführt.
                    Dies entspricht einer Matrixaddition in $\mathbb{F}_{256}$:
                    $$ \textbf{S}\mapsto\textbf{K}+\textbf{S}$$
            \end{enumerate}
            \vspace{2mm}
            AES-128 führt die zuvor beschriebenen Schritte nach dem folgenden Algorithmus aus:
            \texttt{
            \begin{tabbing}
                AES\_ENCRYPT(\textbf{S},$\textbf{K}_0,...,\textbf{K}_10$)\{\\
                \hspace{5mm}\=AddRoundKey(\textbf{S},$\textbf{K}_0$)\\
                \>for( int i = 1; i < 10; ++i)\{\\
                \>\hspace{5mm}\=SubBytes(\textbf{S});\\
                \>\>ShiftRows(\textbf{S});\\
                \>\>MixColumns(\textbf{S});\\
                \>\>AddRoundKey(\textbf{S},$\textbf{K}_0$)\\
                \>\}\\
                \>SubBytes(\textbf{S});\\
                \>ShiftRows(\textbf{S});\\
                \>AddRoundKey(\textbf{S},$\textbf{K}_0$)\\
                \}
            \end{tabbing}}