Code owners
Assign users and groups as approvers for specific file changes. Learn more.
main.tex 52.90 KiB
\input{template.tex}
\begin{document}
%TODO: Notation von Funktionen überführen in
% P: A \to B
% a \mapsto b
% an Stelle von P(x) = y
\section{Einführung}
Ziel dieser Veranstaltung ist die Einführung in die Kryptoanalyse von
symmetrischen Verschlüsselungsverfahren. Dies beinhaltet die Analyse von
möglichen Angriffen auf die Verfahren, deren Beurteilung und schlussendlich das
finden von Designkriterien für die verwendeten Algorithmen.
Nur am Rande werden jedoch Implementierungsfehler oder Seitenkanalangriffe
behandelt, da das keine Angriffe auf die eigentlichen Verfahren sind.
\subsection{Verschlüsselung}
\begin{definition}[Verschlüsselungsverfahren]
Ein Verschlüsselungsverfahren ist ein Tupel aus \((\Plain, \Keys, \Cipher, E, D)\)
wobei der Plaintext \(\Plain\), die Schlüssel \(\Keys\) und der Ciphertext
\(\Cipher\) endliche Mengen sind und die Verschlüsselungsfunktion
\(E: \Plain\times\Keys \to \Cipher\), so, sodass für alle \(k\in\Keys\)
\(E(\cdot,k)\) injektiv ist, sowie die Entschlüsselungsfunktion
\(D(\cdot, k) = E^{-1}(\cdot, k)\).
\end{definition}
%TODO
\subsection{Informations- und Komplexitätstheorie}
\subsection{Blockchiffren, Mode of Operation}
\section{Statistische Analyse von Blockchiffren}
Wir setzen uns in diesem Kapitel mit Substitutions-Permutations-Netzwerken
und Feistelnetzwerken auseinander -- und den am meisten darauf angewendeten
Angriffen, der linearen und der differentiellen Kryptoanalyse. Hierfür
gehen wir in beiden genauer auf die konkreten Konstruktionen ein, um
statistische Muster in diesen zu finden und auszunutzen.
\subsection{Lineare Kryptoanalyse}
%TODO add references Matsui/Yamagishi
Im vorherigen Kapitel haben wir gesen, dass lineare Blockchiffren,
also Abbildungen der Form \(E:\{0,1\}^2\times\{0,1\}^l\to\{0,1\}^n\) unsicher
sind. Wir werden uns nun genauren Angriffen auf Block- (und Strom-) -chiffren
widmen. Einer der am weitesten Verbreiteten Angriffe auf Blockchiffren ist
die lineare Kryptoanalyse, enwickelt durch Matsui/Yamagishi~92. Wir suchen
\enquote{versteckte} Linearitäten oder Affinitäten der Verschlüsselungsroutine,
also lineare Zusammenhängen zwischen Plaintexten, Schlüsseln und Chiffren.
Wenn wir von solchen versteckten Linearitäten reden, meinen wir Zusammenhänge,
die zwar nicht \enquote{rein} linear sind, aber mit einer hohen
Wahrscheinlichkeit bestimmte linearitäten aufweisen. Eine Linearität ist
hierbei die Möglichkeit für bestimmte Vektoren Linearformen zu finden.
\begin{definition}[Linearformen im \(\GF_2\)]
Eine lineare Abbildung heißt Linearform, wenn sie von einem Vektorraum in den
darunter liegenden Körper abbildet. Wir interessieren uns für den Körper
\(\GF_2=\{0,1\}\), also für Abbildungen \(f:\GF_2^n\to\GF_2\).
Wir nennen nun eine mit \(\alpha\in\GF_2^2\) definierte Abbildung
\(\langle\alpha,\cdot\rangle: \GF_2^n\to\GF_2\) eine Linearform, wenn
\[
\forall x\in\GF_2^n: \langle\alpha,x\rangle = \sum_{i=1}^n \alpha_i x_i
\]
\end{definition}
Wir betrachten nun die Wahrscheinlichkeit für eine konkrete Verschlüsselungsfunktionihre Wahrscheinlichkeit \(p_{\alpha,\beta,\gamma}\), dass wir für feste
\(\alpha,\beta\in\GF_2^n\), \(\gamma\in\GF_2^l\) Plaintext-Schlüssel Paare finden
können, sodass wir ihren Zusammenhang zu der dazugehörigen Chiffre als Linearformen
von \(\alpha\), \(\beta\) und \(\gamma\) darstellen können:
\begin{align*}
p_{\alpha,\beta,\gamma}
&:= \Pr(\{(m,k) \mid \langle (\alpha,\gamma),(m,k) \rangle = \langle\beta,E(m,k)\rangle\}) \\
&= \Pr(\{(m,k) \mid \langle\alpha,m\rangle \xor \langle\beta,E(m,k)\rangle = \langle\gamma,k\rangle\})
\end{align*}
Bei einer hohen Nichtlinearität der Verschlüsselungsfunktion erwarten wir
\(p_{\alpha,\beta,\gamma} = 1/2\). Wir nennen nun die mittlere quadratische
Abweichung von diesem Erwartungswert das Potential \(\lambda_{\alpha,\beta,\gamma}\):
\[
\lambda_{\alpha,\beta,\gamma} := (2p_{\alpha,\beta,\gamma} - 1)^2
\]
An dieser Stelle sei angemerkt, dass wir jetzt nur noch Relationen mit
\(p_{\alpha,\beta,\gamma} > 1/2\) betrachten, da wir diese aus Relationen mit
einer Abweichung nach unten einfach konstruieren können, indem wir
\(\langle\gamma',x\rangle := \langle\gamma,x\rangle \xor 1\) setzen.
Fänden wir eine solche lineare Relation \((\alpha,\beta,\gamma)\) (möglichst
mit hohem Potential), würden wir Informationen über den Schlüssel \(k\) gewinnen,
indem wir danach eine known-plaintext Attacke durchführen. D.\,h.\@ wir sammeln
\(N\) Plaintext-Ciphertextpaare \((m_1,c_1),\dotsc,(m_N,c_N)\) und bestimmen
dann die Anzahl derer, wo die Linearformen \(\alpha\) auf den Plain- und
\(\beta\) auf den Ciphertexten das gleiche Bit ergeben:
\[
t := |\{i \leq N \mid \langle\alpha, m_i\rangle\xor\langle\beta,c_i\rangle=0\}|
\]
Ist diese Anzahl \(t>N/2\), dann wissen wir durch das agenommene hohe Potential
unserer linearen Relation, dass auch die Linearform \(\gamma\) über den Schlüssel
\(\langle\gamma,k\rangle=0\) sein muss, andernfalls eben \(1\)\@. Aus dieser
Gleichung gewinnen wir \(\SI{1}{\bit}\) an Informationen über den Schlüssel
\(k\), weil wir nun nicht mehr \(k\) in ganz \(\Cipher\) suchen müssen, sondern
nur noch im von \(\gamma\) aufgespannten Untervektorraum \(V\) mit
\(\dim(V) = l-1\):
\[
k \in V := {\langle\gamma,\cdot\rangle}^{-1} \langle\gamma,k\rangle
\]
Weiter bedeutet das, finden wir \(s\) viele lineare Relationen
\((\alpha_i,\beta_i,\gamma_i)_{i\leq s}\), erhalten wir
\(\SI[parse-numbers=false]{s}{\bit}\) Information über unseren Schlüssel \(k\),
da der Schlüssel im Schnitt der Untervektorräume liegen muss, die durch
\(\gamma_i\) aufgespannt werden, also in einem Untervektorraum der Dimension
\(l-s\):
\[
k \in \bigcap_{i=1}^N {\langle\gamma_i,\cdot\rangle}^{-1}\langle\gamma_i,k\rangle
\]
Wir haben dafür aber angenommen, dass wir eine (bzw.\@ mehere) solche(r) lineare(n)
Relation(en) bereits gegeben haben, und zudem haben wir über Wahrscheinlichkeiten
argumentiert -- es stellen sich also folgende Fragen:
\begin{enumerate}
\item Wie finden wir lineare Relationen mit hohem Potential? Es gibt schließlich
\(2^n\cdot 2^n\cdot 2^l\) viele.
\item Was ist die Erfolgswahrscheinlichkeit unseres Angriffs in Abhängigkeit vom
Potential und der Anzahl \(N\) der Plaintext-Ciphertextpaare?
\end{enumerate}
\paragraph{Finden von guten Relationen}
Gehen wir zuerst der ersten Fragestellung nach.
\begin{remark}
Im Folgenden werden wir das \(\gamma\) nicht weiter betrachten, da es nur
beschreibt \emph{welche} Schlüsselbits (der Rundenschlüssel) wir betrachten,
wir aber nur daran interessiert sind, überhaupt lineare Relationen zu finden.
Auch, ob \(\langle\gamma,k\rangle = 0\) ist oder \(1\) -- da dieWahrscheinlichkeiten affin zu einander sind, ist im ersten Fall die
Wahrscheinlichkeit \(p_{\alpha,\beta,\gamma} > 1/2\), ist im zweiten Fall
\(p'_{\alpha,\beta,\gamma} = 1 - p_{\alpha,\beta,\gamma} < 1/2\).
Das Potential bleibt also gleich und wir müssen in unseren Überlegungen also
nur die Gegenwahrscheinlichkeit betrachten, bzw.\@ die Menge der
\enquote{passenden} Plain-Chiffretextpaare nun genau das Komplement ist,
es wird also wieder der gleiche Untervektorraum aufgespannt in dem wir \(k\)
zu suchen haben.
Wir werden hier \(\langle\gamma,k\rangle:=0\) festlegen, da wir nun umformen
können:
\[
\langle\alpha,m\rangle \xor \langle\beta,c\rangle = \langle\gamma,k\rangle := 0
\Leftrightarrow
\langle\alpha,m\rangle = \langle\beta,c\rangle
\]
\end{remark}
Betrachten wir voerst nur die nichtlinearen S-Boxen von
Substitutions-Permutations-Netzwerken. Eine S-Box ist eine Abbildung
\(S: \GF_2^s \to \GF_2^s\)\footnote{
Meist ist hierbei \(s = 8, 16\). Es gibt aber auch S-Boxen die
unterschiedlich viele Input wie Output-Bits habenk im Beispiel von DES
\(S: \GF_2^6 \to \GF_2^4\).
}. Wir betrachten also die linearen Zusammenhänge zwischen dem Input \(x\) und
dem output \(S(x)\) und suchen lineare Relationen.
Um die Wahrscheinlichkeit \(p_{\alpha,\beta}\) zu berechnen, müssen wir für jede
lineare Relation \((\alpha,\beta)\) \(2^8\) mal die S-Box \(S\) auswerden.
Mit \(\alpha,\beta\neq 0\) haben insgesamt \((2^8 -1)(2^8-1)\) viele Relationen,
wir haben also einen Aufwand von \(\mathcal{O}(2^24)\). %TODO T(n), nicht O(n)?
Tatsächlich können wir das sogar effizienter machen, dazu mehr später.
%TODO ref. Kapitel 13
Möchten wir jetzt mehrere lineare Relationen von \emph{parallel ausgeführten}
S-Boxen kombinieren, können wir die Gesamtwahrscheinlichkeit aus den
Einzelwahrscheinlichkeiten berechnen:
\begin{theorem}[Piling-Up Lemma]\label{thm:piling-up-lemma}
Seien \((\alpha_i,\beta_i)\) lineare Relationen für parallele \(S_i\) mit den
einzelnen Wahrscheinlichkeiten
\[
p_{\alpha_i,\beta_i}
:= \Pr(\{x \mid \langle\alpha_i,x\rangle = \langle\beta_i, S_i(x)\rangle\})
= \frac{1}{2} + \varepsilon_i
\]
Dann gilt für die zusammengesetzte lineare Relation
\((\alpha,\beta) := ((\alpha_1,\dotsc,\alpha_n),(\beta_1,\dotsc,\beta_n))\):
\[
p_{\alpha,\beta} = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \varepsilon_i
\]
\end{theorem}
\begin{proof}[Ansatz für \(n=2\)]
Wir kombinieren für nur zwei S-Boxen:
\begin{align*}
& \Pr(\{ (x_1,x_2) \mid \langle(\alpha_1,\alpha_2),(x_1,x_2)\rangle = \langle(\beta_1,\beta_2),(S_1(x_1),S_2(x_2))\rangle \}) \\
=& \Pr(\{ (x_1,x_2) \mid \langle\alpha_1,x_1\rangle\xor\langle\alpha_2,x_2\rangle = \langle\beta_1,S_1(x_1)\rangle\xor\langle\beta_2,S_2(x_2)\rangle \}) \\
=& \Pr(\{ (x_1,x_2) \mid \langle\alpha_1,x_1\rangle\xor\langle\beta_1,S_1(x_1)\rangle = \langle\alpha_2,x_2\rangle\xor\langle\beta_2,S_2(x_2)\rangle \}) \\
=& \Pr(\{ (x_1,x_2) \mid \langle\alpha_1,x_1\rangle\xor\langle\beta_1,S_1(x_1)\rangle = 0 \land \langle\alpha_2,x_2\rangle\xor\langle\beta_2,S_2(x_2)\rangle = 0 \}) \; + \\
& \Pr(\{ (x_1,x_2) \mid \langle\alpha_1,x_1\rangle\xor\langle\beta_1,S_1(x_1)\rangle = 1 \land \langle\alpha_2,x_2\rangle\xor\langle\beta_2,S_2(x_2)\rangle = 1 \}) \\
=& \left(\frac{1}{2} + \varepsilon_1\right)\cdot\left(\frac{1}{2} + \varepsilon_2\right) +
\left(\frac{1}{2} - \varepsilon_1\right)\cdot\left(\frac{1}{2} - \varepsilon_2\right) \\
=& \frac{1}{4} + \frac{1}{2}(\varepsilon_1+\varepsilon_2) + \varepsilon_1\varepsilon_2 +
\frac{1}{4} - \frac{1}{2}(\varepsilon_1+\varepsilon_2) + \varepsilon_1\varepsilon_2 \\
=& \frac{1}{2} + 2\varepsilon_1\varepsilon_2
\end{align*}
Den Rest zeigt man analog per Induktion.
\end{proof}
\subparagraph{Lineare Relationen für S-Boxen und Permutationen}
Wir überlegen uns nun was passiert, wenn wir eine Permutation \(P\) hinzunehmen.Permutationen sind nur bijektive Abbildungen, und für diese können wir sehr leicht
lineare Relationen finden mit
\[
\Pr(\{ x \mid \langle\alpha,x\rangle = \langle\beta,A(x)\rangle = 1\rangle \}) = 1
\]
\begin{lemma}
Sei \(A: \GF_2^n \to \GF_2^n\) eine bijektive lineare Abbildung. Dann:
\[
\forall\alpha\in\GF_2^n \; \exists\beta\in\GF_2^n \; \forall x\in\GF_2^n:
\langle\alpha,x\rangle = \langle\beta, A(x)\rangle
\]
\end{lemma}
\begin{proof}[Ansatz]
Es gilt
\[
\langle\beta,A(x)\rangle = \langle A^t(\beta),x\rangle
\]
Mit \(\beta = {(A^t)}^{-1}(\alpha)\) folgt die Behauptung.
\end{proof}
Wir können also ebenfalls für Kombinationen \(R=P\circ S\) aus Permutationen
und S-Boxen lineare Relationen konstruieren, die die Wahrscheinlichkeit auch
nicht weiter beeinflussen. Angenommen, wir haben nun eine solche Relation,
dann können wir umformen:
\begin{alignat*}{2}
&& \langle\beta, c\rangle
&= \langle\beta, R(m\xor k^0)\xor k^1\rangle \\
&& &= \langle\beta, R(m\xor k^0)\rangle \xor \langle\beta, k^1\rangle \\
&& &\stackrel{p_{\alpha,\beta}}{=} \langle\alpha, m\xor k^0\rangle \xor \langle\beta, k^1\rangle \\
&& &= \langle\alpha, m\rangle \xor \langle\alpha, k^0\rangle \xor \langle\beta, k^1\rangle \\
\Leftrightarrow
&& \langle\alpha,m\rangle \xor \langle\beta,c\rangle
&\stackrel{p_{\alpha,\beta}}{=} \langle\alpha,k^0\rangle \xor \langle\beta,k^1\rangle
\end{alignat*}
Analog zeigt man
\[
\langle\alpha,m\rangle\xor\langle\beta,c\rangle
\stackrel{1-p_{\alpha,\beta}}{\neq}
\langle\alpha,k^0\rangle\xor\langle\beta,k^1\rangle
\]
Wir haben nun aus einer Relation für \(R\) \((\alpha,\beta)\) eine Relation
\((\alpha,\beta,\gamma)\) für \(E\) gefunden, mit
\[
\langle\gamma,k\rangle = \langle\alpha,k^0\rangle \xor \langle\beta,k^1\rangle
\]
Wenn wir nun eine Menge an Plaintext-Ciphertext-Paaren haben, mit einer Relation
mit Wahrscheinlichkeit \(p\). Falls \(p>1/2\), haben wir wie gehabt eine
Gleichheit also \(\langle\gamma,k\rangle=0\) -- andernfalls nutzen wir die
zweite Wahrscheinlichkeit \(1-p>1/2\), also \(\langle\gamma,k\rangle=1\).
\begin{theorem}
Sei \((\alpha,\beta)\) für \(R=P\circ S\) mit Wahrscheinlichkeit \(p\). Dann ist
\(\max\{p,1−p\}\geq 1/2\) die Erfolgswahrscheinlichkeit einer lineare Kryptoanalyse für
ein bekanntest Plain\-text-Cipher\-text\-paar.
\end{theorem}
\subparagraph{Mehrere Runden}
Wir müssen uns nun noch damit beschäftigen, wie wir unsere Erkenntnisse auf
mehrere Runden ausweiten. Wir gucken uns hierfür ein SPN mit \(r\) Runden
\(R_1,\dotsc,R_r\) an, wobei \(\alpha_i,\beta_i\) jeweils die lineare Relation
für \(R_i\) mit einer Runden-Erfolgswahrscheinlichkeit von
\(p_i = 1/2 + \varepsilon_i\) ist. Damit wir die Relationen kombinieren können,
brauchen wir einen sogenannten linearen Pfad \((\alpha_i,\beta_i)_{i\leq r}\)
von \(\alpha_1\) nach \(\beta_r\), das bedeutet, dass
\[
\forall i\in [1,r): \beta_i = \alpha_{i+1}
\]
In diesem Fall ist die lineare Relation für die volle Chiffre \(E\) schlicht die
Relation \((\alpha_1,\beta_r)\).
Betrachten wir das erstmal für zwei Runden, d.\,h.\@ unser Ciphertext wird
berechnet als
\[
c = R_2(R_1(m\xor k^0)\xor k^1)\xor k^2
\]
Wir können nun umformen:
\begin{alignat*}{2}
&& \langle\beta_2,c\rangle
&= \langle\beta_2,R_2(R_1(m\xor k^0)\xor k^1)\xor k^2 \\
&& &= \langle\beta_2,R_2(R_1(m\xor k^0)\xor k^1)\rangle \xor \langle\beta_2,k^2\rangle \\
&& &\stackrel{p_2}{=}
\langle\beta_1,R_1(m\xor k^0)\xor k^1\rangle \xor \langle\beta_2,k^2\rangle \\
&& &= \langle\beta_1,R_1(m\xor k^0)\rangle \xor \langle\beta_1,k^1\rangle \xor \langle\beta_2,k^2\rangle \\
&& &\stackrel{p_1}{=}
\langle\alpha_1,m\xor k^0\rangle \xor \langle\beta_1,k^1\rangle \xor \langle\beta_2,k^2\rangle \\
&& &= \langle\alpha_1,m\rangle \xor \langle\alpha_1,k^0\rangle \xor \langle\beta_1,k^1\rangle \xor \langle\beta_2,k^2\rangle \\
\Leftrightarrow
&& \langle\beta_2,c\rangle \xor \langle\alpha_1,m\rangle
&\stackrel{p}{=}
\langle\alpha_1,k^0\rangle \xor \langle\beta_1,k^1\rangle \xor \langle\beta_2,k^2\rangle
\end{alignat*}
Wie groß ist nun die kombinierte Wahrscheinlichkeit \(p\)?
\begin{theorem}\label{thm:piling-up-lemma'}
Sei \(E\) ein Chiffre basierend auf einem \(r\)-Runden SPN mit den unabhängig gewählten
Rundenschlüsseln \(k^0,\dotsc,k^r\) und \((\alpha_i,\beta_i)\) lineare Relationen
für die einzelnen Runden die einen linearen Pfad \((\alpha_i,\beta_r)\) bilden.
Dann gilt
\[
\langle\beta_r,c\rangle \xor \langle\alpha_1,m\rangle
\stackrel{p}{=}
\langle\alpha_1,k^0\rangle \xor \dotsb \xor \langle\beta_r,k^r\rangle
\]
mit einer Erfolgswahrscheinlichkeit \(p\) aus den kombinierten
Einzelwahrscheinlichkeiten der Runden \(p_i\):
\[
p \geq 1/2 + 2^{r-1} \prod_{i=1}^r \varepsilon_i
\]
\end{theorem}
\begin{proof}[Ansatz]
Wir zeigen die Abschätzung für die Gesamtwahrscheinlichkeit für den Fall \(r=2\).
Es gilt
\[
\langle\alpha_1,x\rangle \stackrel{p_1}{=} \langle\beta_1,R_1(x)\rangle
\qquad\qquad
\langle\alpha_2,x\rangle \stackrel{p_2}{=} \langle\beta_2,R_2(x)\rangle
\]
Da die Rundenschlüssel unabhängig gewählt sind, ist auch die Ausgabe
\(y_0 := R_1(m\xor k^0)\) von \(R_1\) unabhängig von der Eingabe
\(y_1 := R_1(m\xor k^0)\xor k^1\) von \(R_2\). Somit gilt mit der Ausgabe
\(y_2 := R_2(y_1)\xor k^2\) von \(R_2\) folgende Abschätzung:
\begin{align*}
p
:=& \Pr(\{ (m,c) \mid \langle\alpha_1,m\rangle = \langle\beta_2,c\rangle \}) \\
\geq& \Pr(\{ (m,c) \mid \langle\alpha_1,m\rangle = \langle\beta_1,y_1\rangle \land
\langle\beta_1,y_1\rangle = \langle\beta_2,y_2\rangle \}) \; + \\
& \Pr(\{ (m,c) \mid \langle\alpha_1,m\rangle \neq \langle\beta_1,y_1\rangle \land
\langle\beta_1,y_1\rangle \neq \langle\beta_2,y_2\rangle \}) \\
=& p_1\cdot p_2 + (1-p_1) \cdot (1-p_2) \\
=& \frac{1}{2} + 2\varepsilon_1\varepsilon_2
\end{align*}
Wir schätzen nach oben ab, da es auch andere (bessere) Möglichkeiten geben kann, einen
linearen Pfad von \((\alpha_1,\beta_2)\) zu bauen.
Es gilt somit
\[
\langle\alpha_1,m\rangle \stackrel{p}{=} \langle\beta_2,c\rangle
\]
\end{proof}
Für die volle Chiffre ist nun die Erfolgswahrscheinlichkeit, basierend auf obigerAbschätzung \(\max\{p,1-p\}\).
\begin{remark}
Damit haben wir nun unsere erste Frage beantwortet. Wir können hierbei erkennen, dass
die Erfolgswahrscheinlichkeit mit hoher Rundenzahl abnimmt und wir nur eine untere
Schranke für die Erfolgswahrscheinlichkeit zeigen können -- sprich eine obere Schranke
für die Misserfolgswahrscheinlichkeit. Für Sicherheit möchten wir aber die
Erfolgswahrscheinlichkeit nach oben begrenzen -- das ist jedoch nicht möglich.
Zudem nimmt unsere Abschätzung aber nur, wenn wir die Unabhängigkeit der einzelnen
Rundenschlüssel voneinander annehmen -- dies ist aber keine Schwäche der Analyse, denn
man kann zeigen, dass mit abhängigen Rundenschlüsseln die Erfolgswahrscheinlichkeit sich
deutlich erhöht.
%TODO cite Rijmen Dissertation
\end{remark}
\paragraph{Anzahl der benötigten Plaintext-Chiffretextpaare}
Wir haben nun eine Metrik gefunden um unsere linearen Relationen zu finden und zu
bewerten. Wir möchten nun sehen, wie viele Plaintext-Chiffretextpaare benötigt
werden um die tatsächliche Attacke durchzuführen.
Sei nun \((\alpha,\beta)\) (bzw.\@ \((\alpha,\beta,\gamma)\)) eine lineare
Relation für die Gesamtchiffre nach vorheriger Konstruktion, mit einer
(Mindest-)Erfolgswahrscheinlichkeit \(p\) für
\[
\langle\alpha,m\rangle \xor \langle\beta,E(m,k)\rangle
= \langle\gamma,(k^0,k^1)\rangle
\]
Mit der Gegenwahrscheinlichkeit \(1-p\) gilt diese Gleichung jedoch nicht.
Damit unsere Strategie (Majoritätsentscheidung) aufgeht, darf aber nicht
nur die \emph{Wahrscheinlichkeit} höher als \(1/2\) sein, dass wir ein
Plaintext-Chiffretextpaar haben, für das diese Gleichung gilt, sondern
die Mehrheit der gesammelten Plaintexte muss diese Gleichung erfüllen.
Wir möchten also die Wahrscheinlichkeit berechnen, dass wir aus der Menge
der Menge der Plaintexte \(T:=2^n=|\Plain|\) mit \(N\) Versuchen auch mehr
als \(N/2\) Paare tatsächlich die obige Gleichung erfüllen. Wir wissen hierbei,
dass \(pT\) die Gesamtzahl solcher Paare ist.
Somit können wir die Wahrscheinlichkeit als hypergeometrische Verteilung
(Urnenmodell) modellieren.
\begin{theorem}
Bei einer Erfolgswahrscheinlichkeit pro Plaintext von \(p\), ergibt sich
eine Erfolgswahrscheinlichkeit für den Angriff in Abhängigkeit der gesammelten
Plaintext-Chiffretextpaare \(N\) als hypergeometrische Verteilung mit
\(p \approx 1/2\) und dem Potential \(\lambda := (2p-1)^2\), sowie
\(N \ll T = 2^n\):
\[
p(N) \approx \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\sqrt{N\lambda}} e^{\frac{t^2}{2}} \mathrm{d}t
\]
\end{theorem}
\begin{remark}
Da wir die hypergeometrische Verteilung mit der Normalverteilung approximieren
können, benötigen wir für eine Erfolgswahrscheinlichkeit von \(\SI{96.7}{\percent}\)
für den Angriff \(N/\lambda\) viele Paare.
\end{remark}
\subsubsection{FEAL-4}
Der Fast data Encipherment ALgorithm (1978) ist eine Blockchiffre auf
Blöcken aus \SI{64}{\bit}, wobei FEAL-4 einen \SI{64}{\bit} Rundenschlüssel
nutzt und aus \num{4} Runden besteht.
Zur Verschlüsselung wird ein Feistelnetzwerk mit der Rundenfunktion \(F\)
genutzt.
\begin{definition}[Feistel Netzwerk]
Sei \(F\) eine Rundenfunktion und \(K_i\) the Subkeys für die \(n\) Runden. Wir
definieren ein Tupel \((R_0,L_0) := P\) als die vertauschten linke und rechte
Hälften des Plaintextes. Für jede Runde berechnen wir:
\begin{align*}
L_{i+1} := R_i \xor F(L_i,K_i) && R_{i+1} := L_i\end{align*}
Die Chiffretext ist definiert als \(C := (L_n,R_n)\).
\end{definition}
\begin{remark}
Die Entschlüsselung einer Feistelchiffre ist schlicht eine Traversion durch das
gleiche Netzwerk in umgekehrte Richtung (wir nutzen also \(K_n\) zuerst).
Es ist hierbei \emph{nicht} notwendig, dass \(F\) invertierbar ist -- im
Gegensatz zu SPNs.
\end{remark}
\begin{definition}[FEAL-4]
Die FEAL-4 Chiffre nutzt ein Feistelnetzwerk mit vier Runden und zwei kleinen
Modifikationen, nämlich wird vor und nach dem Durchlauf die rechte Hälfte noch
mit der linken Hälfte verxodert. Außerdem nutzen wir zwei zusätzliche Subkeys
\(K_L\) und \(K_R\) für die linke, respektive rechte Hälfte nach dem kompletten
Durchlauf des Netzwerks.
\begin{align*}
(R_0',L_0') := P, && & L_0 := L_1' \xor R_1 && R_0 := R_0' \\
(L_4',R_4') =: C, && & L_4' := K_L \xor L_4 && R_4' := K_R \xor (L_4 \xor R_4)
\end{align*}
Die Rundenfunktion von FEAL \(F(R,K)\) ist definiert als \(F(R,K) := F'(R\xor K)\)
wobei \(F'(X) = Y\) auf \SI{4}{\byte} \((x_0,x_1,x_2,x_3) := X\) der \SI{32}{\bit}
input arbeitet und \SI{4}{\byte} output \(Y := (y_0,y_1,y_2,y_3)\) geniert:
\begin{align*}
y_0 &:= G_0(x_0, x_1) & y_1 &:= G_1(x_0\xor x_1, x_2\xor x_3) \\
y_2 &:= G_1(y_1, x_2\xor x_3) & y_3 &:= G_1(y_2, x_3)
\end{align*}
Hierbei arbeiten \(G_0,G_1\) wiederum auf \SI{4}{\byte}, die wiefolgt definiert
sind (wobei \(\lll\) ein zyklischer Shift bzw.\@ eine Bitrotation ist):
\begin{align*}
G_0(a,b) &:= (a + b \bmod 2^8) \lll 2 \\
G_1(a,b) &:= (a + b + 1 \bmod 2^8) \lll 2
\end{align*}
\end{definition}
Abbildung~\ref{fig:feal-4-feistel} zeigt eine schmatische Darstellung des
genutzten Feistelnetzwerks, Abbildung~\ref{fig:feal-4-round} eine detaillierte
Ansicht der schlüssellosen Subroutine \(F'\).
\begin{figure}[H]
\centering
\def\N{4}
\begin{tikzpicture}[->=latex']
% initial plain-text node
\node[draw] (plain) at (0, 0) {\(P = (L_0',R_0')\)};
% position F', key-ing, and L/R xor and connections within rounds
\foreach \n in {1, 2, ..., \N} {
\pgfmathtruncatemacro{\prev}{\n - 1}
\node[draw] (F'-\n) at ($(plain)+(0,-0.25)+\n*(0,-1.5)$) {\(F'\)};
\node[inner sep=0] (Fxor-\n) at ($(F'-\n)+(1,0 )$) {\(\xor\)};
\node[] (K-\prev) at ($(F'-\n)+(3,0.3)$) {\(K_\prev\)};
\node[inner sep=0] (lxor-\n) at ($(F'-\n)+(-2,0)$) {\(\xor\)};
\coordinate (rnop-\n) at ($(F'-\n)+( 2,0)$);
\draw[->] (F'-\n) -- (lxor-\n);
\draw[->] (Fxor-\n) -- (F'-\n);
\draw[->] (K-\prev) -| (Fxor-\n);
}
% final cipher-text node
\node[draw] (cipher) at ($(F'-\N)+(0,-0.25)+(0,-1.5)$) {\(C = (L_\N',R_\N')\)};
% final L/R keying
\coordinate (xor-L') at ($(plain.south) +(-0.25, -0.25)$);
\coordinate (xor-R') at ($(plain.south) +( 0.25, -0.25)$); \node[inner sep=0] (xor-L) at ($(cipher.north) +(-1 , 0.25)$) {\(\xor\)};
\node[inner sep=0] (xor-R) at ($(cipher.north) +( 1 , 0.25)$) {\(\xor\)};
\node (K-L) at ($(xor-L)+(-2,0.3)$) {\(K_L\)};
\node (K-R) at ($(xor-R)+( 2,0.3)$) {\(K_R\)};
% init/final L\xor R
\node[inner sep=0] (xor-P) at ($(plain) +( 2,-1 )$) {\(\xor\)};
\coordinate (xor-P') at ($(plain) +(-2,-1 )$);
\node[inner sep=0] (xor-C) at ($(cipher)+( 2,+1.25)$) {\(\xor\)};
\coordinate (xor-C') at ($(cipher)+(-2,+1.25)$);
% connections for final L/R keying
\draw[->] (K-L) -| (xor-L);
\draw[->] (K-R) -| (xor-R);
% connections for init/final L\xor R
\draw[->] ($(plain.south)+ (-0.25,0)$) -- (xor-L') -| (lxor-1);
\draw[->] ($(plain.south)+ ( 0.25,0)$) -- (xor-R') -| (xor-P);
\draw[->] (xor-P') -- (xor-P);
\draw[->] (xor-P) |- (Fxor-1);
\draw[<-] ($(cipher.north)+( 0.25,0)$) |- (xor-R);
\draw[<-] (xor-R) -| (xor-C);
\draw[<-] ($(cipher.north)+(-0.25,0)$) |- (xor-L);
\draw[<-] (xor-L) -| (lxor-\N);
\draw[<-] (xor-C) -- (xor-C');
\draw[<-] (xor-C) |- (Fxor-\N);
% connections in-between rounds
\pgfmathtruncatemacro{\NX}{\N - 1}
\foreach \n in {1, 2, ..., \NX} {
\pgfmathtruncatemacro{\next}{\n + 1}
\draw[->] (rnop-\n) -- +(0,-0.5) -- ($(F'-\next)+(-2,0)+(0,0.5)$) -- (lxor-\next);
\draw[->] (lxor-\n) -- +(0,-0.5) -- ($(F'-\next)+( 2,0)+(0,0.5)$) |- (Fxor-\next);
}
\end{tikzpicture}
\caption{FEAL-4: Feistelnetzwerk}
\label{fig:feal-4-feistel}
\end{figure}
\begin{figure}[H]
\centering
\def\N{4}
\begin{tikzpicture}
\pgfmathtruncatemacro{\NX}{\N - 1}
\foreach \n in {0, 1, ..., \NX} {
\node[] (x\n) at (\n,0) {\(x_\n\)};
\node[] (y\n) at (\n,-5) {\(y_\n\)};
}
\node[] (xor-1) at (1,-1) {\(\xor\)};
\node[] (xor-2) at (2,-1) {\(\xor\)};
\node[draw] (G-1) at (1,-2) {\(G_1\)};
\node[draw] (G-2) at (2,-3) {\(G_0\)};
\node[draw] (G-0) at (0,-4) {\(G_0\)};
\node[draw] (G-3) at (3,-4) {\(G_1\)};
\draw[->] (x0) -- (G-0);
\draw[->] (x3) -- (G-3);
\draw[->] (x0) |- (xor-1);
\draw[->] (x3) |- (xor-2);
\draw[->] (x1) -- (xor-1);
\draw[->] (x2) -- (xor-2);
\draw[->] (xor-1) -- (G-1);
\draw[->] (xor-2) -- (G-2);
\draw[->] (xor-2) |- (G-1);
\draw[->] (G-1) |- (G-2);
\draw[->] (G-1) |- (G-0); \draw[->] (G-2) |- (G-3);
\foreach \n in {0, 1, ..., \NX} {
\draw[->] (G-\n) -- (y\n);
}
\end{tikzpicture}
\caption{FEAL-4: Schlüssellose Rundenfunktion \(F'\)}
\label{fig:feal-4-round}
\end{figure}
\paragraph{Angriff mit linearer Kryptoanalyse}
Wir möchten nun eine lineare Relation für die Subroutine \(F'\) finden. Wir werden
sehen, dass wir einige Bits des Outputs mehr oder weniger direkt von der Eingabe
ableiten können, \emph{ohne den Schlüssel zu kennen}.
Da wir häufig uns nur einzelne Bits des Bitstrings angucken werden, oder nur
das XOR (oder Skalarprodukt) der selbsen, definieren wir das indizierte
\(\alpha_i\) als diejenige lineare Relation, wo genau die indizierten Bits \(1\)
sind:
\begin{align*}
\alpha_i &:= (0,\dotsc,0,1,0,\dotsc,0) \\
\alpha_{i,j} &:= (0,\dotsc,0,1,0,\dotsc,0,1,0,\dotsc,0) \\
\alpha_{i,j,k} &:= \ldots
\end{align*}
Das vereinfacht unsere Notation eines XOR von nur einem Teil der Bits eines
beliebigen Bitstrings \(s\):
\[
\langle\alpha_i,s\rangle = 0\cdot s_0 + \dotsb + 1\cdot s_i + \dotsb
\]
Wir können nun binäre \SI[parse-numbers=false]{n}{\bit} Addition als ein XOR
auffassen, d.\,i.\@ für alle \(i<n\) und \(a,b\in\GF_2^n\):
\[
\langle\alpha_i,a\xor b\rangle = \langle\alpha_i,a+b \bmod 2^n\rangle
\]
Gucken wir nun in die Subroutine \(F'\) \enquote{herein}. Wir beobachten folgende
Gleichheiten (man beachte die Indexverschiebung durch den Leftshift in \(G\)):
\begin{align*}
\langle\alpha_5, G_0(a,b)\rangle = \langle\alpha_7, a\xor b\rangle &&
\langle\alpha_5, G_1(a,b)\rangle = \langle\alpha_7, a\xor b\rangle \xor 1 &&
\end{align*}
Wir können nun folgende Information über die Ausgabe \(F'(X)\) für eine beliebige
\SI{4}{\byte} Eingabe gewinnen:
\begin{align}
\langle\alpha_{13},F'(X)\rangle &= \langle\alpha_{7,15,23,31}\,, x\rangle \xor 1 \\
\langle\alpha_{5,15},F'(X)\rangle &= \langle\alpha_7, x\rangle \label{eqn:feal-4-F2}\\
\langle\alpha_{15,21},F'(X)\rangle &= \langle\alpha_{23,31}\,, x\rangle \\
\langle\alpha_{23,29},F'(X)\rangle &= \langle\alpha_{31}, x\rangle \xor 1 \label{eqn:feal-4-F4}
\end{align}
\begin{proof}[Beweis der Gleichungen~\ref{eqn:feal-4-F2} und~\ref{eqn:feal-4-F4}]
Wir nutzen den Fakt, dass wir das Skalarprodukt aufteilen können (es ist ja
schließlich nur eine Summe), d.\,h.\@ für alle \(\alpha_i\) und
\(Y=(y_0,y_1,\dotsc)\) können wir schreiben:
\[
\langle\alpha_i,Y\rangle = \langle\alpha_i,y_0\rangle +
\langle\alpha_{i-|y_0|},y_1\rangle + \dotsb
\]
Wir können nun jeden negativen Index ignorieren, da diese nicht auf diesen
Bitstring zutreffen. Diese Idee kann auf mehrfach indexierte \(\alpha\) analog
angewendet werden.
Zusätzlich wissen wir:
\[
\langle\alpha, a\xor b\rangle = \langle\alpha, a\rangle + \langle\alpha, b\rangle
\]
Damit können wir nun folgende Gleichheiten zeigen:
\begin{align*} \langle\alpha_{5,15},F'(X)\rangle
&= \langle\alpha_{5,15}, (y_0,y_1,y_2,y_3)\rangle \\
&= \langle\alpha_5, y_0\rangle \xor \langle\alpha_7, y_1\rangle \xor \langle 0, y_2\rangle \xor \langle 0, y_3\rangle \\
&= \langle\alpha_5, G_0(x_0, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor
\langle\alpha_7, G_1(x_0\xor x_1, x_2\xor x_3)\rangle \\
&= \langle\alpha_7, x_0 \xor G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor
\langle\alpha_7, G_1(x_0\xor x_1, x_2\xor x_3)\rangle \\
&= \langle\alpha_7, x_0\rangle \xor
\langle\alpha_7, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor
\langle\alpha_7, G_1(x_0\xor x_1, x_2\xor x_3)\rangle \\
&= \langle\alpha_7, x_0\rangle
\end{align*}
\begin{align*}
\langle\alpha_{23,29}, F'(X)\rangle
=& \langle\alpha_7, G_0(x_2\xor x_3, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor \\
& \langle\alpha_5, G_1(x_3, G_0(x_2\xor x_3, G_1(x_0\xor x_1, x_2\xor x_3)))\rangle \\
=& \langle\alpha_7, G_0(x_2\xor x_3, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor \\
& \langle\alpha_7, x_3\xor G_0(x_2\xor x_3, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor 1 \\
=& \langle\alpha_7, G_0(x_2\xor x_3, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \xor \\
& \langle\alpha_7, x_3\rangle \xor 1 \xor \\
& \langle\alpha_7, G_0(x_2\xor x_3, G_1(x_0\xor x_1, x_2\xor x_3))\rangle \\
=& \langle\alpha_7,x_3\rangle \xor 1 \\
=& \langle\alpha_{31}, x\rangle \xor 1
\end{align*}
\end{proof}
\begin{remark}
Noch zwei weitere lineare Relationen können gefunden werden:
\[
\langle\alpha_{13},F(x)\rangle = \langle\alpha_{7,15,23,31}, x\rangle \xor 1 \qquad\qquad
\langle\alpha_{15,21},F(x)\rangle = \langle\alpha_{23,31}, x\rangle
\]
\end{remark}
Wir können jetzt unser gewonnenes Wissen benutzen und versuchen Infromationen
der eigentlichen Chiffretexte vorherzusagen, bspw.\@ für die finale linke
Hälfte \(L_4'\) mit \(Y_i := F'(L_i \xor K_i)\):
\begin{align*}
L_4' :=& K_L \xor L_4 \\
=& K_L \xor (Y_3 \xor R_3) \\
=& K_L \xor Y_3 \xor L_2 \\
=& K_L \xor Y_3 \xor Y_1 \xor R_1
\end{align*}
Wir können damit folgende Abhängigkeit von Bits in \(L_4\) berechnen:
\begin{align*}
\langle\alpha_{23,29},L_4'\rangle
=& \langle\alpha_{23,29},K_L \xor Y_3 \xor Y_1 \xor R_1\rangle \\
=& \langle\alpha_{23,29},K_L\rangle \xor
\langle\alpha_{23,29},Y_3\rangle \xor
\langle\alpha_{23,29},Y_1\rangle \xor
\langle\alpha_{23,29},R_1\rangle
\end{align*}
Die einzelnen Ausdrücke können wir jetzt auch weiter auflösen:
\begin{align*}
\langle\alpha_{23,39},Y_3\rangle
=& \langle\alpha_{23,29},F(X_3\xor K_3)\rangle \\
=& \langle\alpha_{31},X_3\xor K_3\rangle \xor 1\\
=& \langle\alpha_{31},\underbrace{L_4'\xor K_4\xor R'_4\xor K_R}_{=X_3}\xor K_3\rangle \xor 1 \\
=& \langle\alpha_{31},L_4'\xor R'_4\rangle \xor
\langle\alpha_{31},K_4\xor K_R\xor K_3\rangle \xor 1 \\
\\
\langle\alpha_{23,29},Y_1\rangle
=& \langle\alpha_{23,29},F'(X_1\xor K_1)\rangle \\
=& \langle\alpha_{23,29},F'(Y_0\xor L'_0 \xor K_1)\rangle \\
=& \langle\alpha_{31},Y_0\rangle \xor
\langle\alpha_{31},L'_0\rangle \xor
\langle\alpha_{31},K_1\rangle \xor 1 \\
=& \langle\alpha_{31},F(L'_0\xor R'_0\xor K_0)\rangle \xor
\langle\alpha_{31},L'_0\rangle \xor
\langle\alpha_{31},K_1\rangle \xor 1 \\
\\ \langle\alpha_{23,29},R_1\rangle
=& \langle\alpha_{23,29},L'_0\xor R'_0\rangle
\end{align*}
Damit können wir weiter einsetzen und umsortieren
%TODO ugly. also overfull hbox
\begin{alignat*}{2}
&& \langle\alpha_{23,29},L_4'\rangle
=& \langle\alpha_{23,29},K_L\rangle \xor
\langle\alpha_{23,29},Y_3\rangle \xor
\langle\alpha_{23,29},Y_1\rangle \xor
\langle\alpha_{23,29},R_1\rangle \\
&& =& \langle\alpha_{23,29},K_L\rangle \xor
\langle\alpha_{31},L_4'\xor R'_4\rangle \xor \\
&& & \langle\alpha_{31},K_4\xor K_R\xor K_3\rangle \xor 1 \xor
\langle\alpha_{31},F(L'_0\xor R'_0\xor K_0)\rangle \xor \\
&& & \langle\alpha_{31},L'_0\rangle \xor
\langle\alpha_{31},K_1\rangle \xor 1
\langle\alpha_{23,29},L'_0\xor R'_0\xor K_L\rangle \\
\Leftrightarrow &&
0
=& \langle\alpha_{31},L_4'\xor R'_4\xor K_4\xor K_R\xor K_3\xor F(L'_0\xor R'_0\xor K_0)\xor L'_0\xor K_1\rangle \xor \\
&& & \langle\alpha_{23,29},L_4'\xor L'_0\xor R'_0\xor K_L\rangle \\
\Leftrightarrow &&
\langle\alpha_{23,29},K_L\rangle \xor\phantom{=} \\
&& \langle\alpha_{31},K_4\xor K_R\xor K_3\xor K_1\rangle
=& \langle\alpha_{31},L_4'\xor R'_4\xor F(L'_0\xor R'_0\xor K_0)\xor L'_0\rangle \xor \\
&& & \langle\alpha_{23,29},L_4'\xor L'_0\xor R'_0\rangle
\end{alignat*}
Wir definieren nun die linke Hälfte als Funktion \(A\) und die rechte als Funktion
\(f\):
\[
A(K) := \langle\alpha_{23,29},K_L\rangle \xor
\langle\alpha_{31},K_4\xor K_R\xor K_3\xor K_1\rangle
\]
\[
f(L'_0,R'_0,L_4',R'_4,K_0) :=
\langle\alpha_{31},L_4'\xor R'_4\xor F(L'_0\xor R'_0\xor K_0)\xor L'_0\rangle \xor
\langle\alpha_{23,29},L_4'\xor L'_0\xor R'_0\rangle
\]
Das bedeutet, \(f\) hängt von dem Plaintext \((L_0,R_0)\), dem Ciphertext
\((L_4',R'_4)\) und \(K_0\) ab, während der \(A\) von den Subkeys \(K_1,K_3,K_L,K_R\)
abhängt (also bei festem Schlüssel konstant).
Wir können mit dieser Erkenntnis nun folgenden Angriff durchführen, sofern
\(n\) Paare \(( ({L'_0}^i,{R'_0}^i), ({L'_4}^i, {R'_4}^i) )_{i\leq n}\) bekannt sind:
%TODO Algo doesn't make sense
\section{Differentielle Kryptoanalyse}
% TODO cite Biham, Shamir 1990
Differentielle Kryptoanalyse ist ein weiterer Angriff auf iterierte Blockchiffren
wie SPNs oder Feistelnetzwerken. Hierbei werden statistische Muster zwischen
Eingabe- (Plaintext) und Ausgabedifferenzen (Ciphertext) ausgenutzt.
Betrachten wir zuerst eine Runde eines SPNs \(c := P(S(m\xor k^0)) \xor k^1\),
wobei die Rundenfunktion als \(R := P\circ S\) definiert ist und die Substitution
aus \num{16} S-Boxen \(S := S_1\times\dotsb S_{16}\) besteht. Wir betrachten
jetzt Paare von Plaintext-Ciphertextpaaren \((m_1,c_1),(m_2,c_2)\) und berechnen
jeweils die Differenz zwischen den Plain- und Ciphertexten:
\[
\Diff(m_1,m_2) := m_1\xor m_2 \qquad \Diff(c_1,c_2) := c_1\xor c_2
\]
Wir machen uns jetzt zu Nutze, dass die Plaintextdifferenz, auch die Differenz
der Eingabe von \(S\) ist:
\[
\Diff(m_1\xor k^0,m_2\xor k^0) =
(m_1\xor k^0) \xor (m_2\xor k^0) =
\Diff(m_1,m_2)
\]Weiterhin ist die Umkehrfunktion \(P^{-1}\) der Permutation linear, somit können
wir auch die Ausgabedifferenz von \(S\) aus der Differenz der Ciphertexte
ableiten:
\begin{align*}
\Diff(S(m_1\xor k^0),S(m_2\xor k^0)) &=
\Diff(P^{-1}(c_1\xor k^1),P^{-1}(c_2\xor k^1)) \\ &=
P^{-1}(c_1\xor k^1) \xor P^{-1}(c_2\xor k^1) \\ &=
P^{-1}(c_1\xor k^1 c_2\xor k^1) \\ &=
P^{-1}(\Diff(c_1, c_2)
\end{align*}
Wir kennen also für jede parallele S-Box \(S_i\) in dieser Runde die Ein- und
Ausgabedifferenz für ein Paar an Plaintexten \(m_1,m_2\).
Es sollte klar sein, dass die Eingabedifferenz unabhängig von den Schlüsseln ist,
praktisch jedoch ist, dass die Ausgabedifferenz ebenfalls nicht von \(k^1\)
abhängig ist -- sondern nur von \(k^0\).
Wir notieren jetzt \((X)_i\) als den \(i\)-ten Teil von \(X\) mit
\(X =: ((X)_1,\dotsc,(X)_{16})\), sprich die Ein- und Ausgaben der \(i\)-ten
S-Box ist:
\[
(\Diff(m_1,m_2))_i \stackrel{S_i}{\mapsto} (P^{-1}(\Diff(c_1,c_2)))_i
\]
Weiterhin notieren wir die einzelnen \num{8} Bits für den Rundenschlüssel \(k^0\):
\[
k^0 =: ((k^0)_1,\dotsc,(k^0)_{16}) =: ((k^0_1,\dotsc,k^0_8),\dotsc)
\]
Nun können wir die einzelnen Bits des Rundenschlüssels \(k^0\) raten, indem wir
nur die S-Boxen \(S_i\) betrachten. Hierzu berechnen wir die sogenannten
Differenztabelle \(D^i\) einer jeden S-Box, indem wir für paare von Ein- und
Ausgabedifferenzen \((\diff,\diff')\) die Eingaben für diese S-Box sammeln,
die bei Änderungen um \(\diff\) eine Änderung um \(\diff'\) in der Ausgabe
der S-Box verursachen:
\begin{align*}
D^i(\diff,\diff') :=&
\{ x\in\GF_2^8 \mid \Diff(S_i(x),S_i(x\xor\diff)) = \diff' \} \\ =&
\{ x\in\GF_2^8 \mid S_i(x)\xor S_i(x\xor\diff) = \diff' \}
\end{align*}
Diese Tabellen sind unabhängig von den Schlüsseln und lassen sich pro Tabelle
mit einem Aufwand von \(2^8\cdot 2^8\) berechnen, indem man alle Paare
\((\diff,\diff')\) durchgeht.
Nun wissen wir, dass der Teilschlüssel \((k^0)_i\) folgende Bedindung
erfüllen muss:
\[
(m_1)_i \xor (k^0)_i \in D^i(\, (\Diff(m_1,m_2))_i, (P^{-1}(\Diff(c_1,c_2))_i\,)
\]
Wobei \(x:=(m_1)_i \xor (k^0)_i\) die Eingabe der \(i\)-ten S-Box ist, und
\(\diff_i := (\Diff(m_1,m_2))_i\) die Eingabedifferenz der Plaintextteile, sowie
\(\diff'_i := (P^{-1}(\Diff(c_1,c_2))_i\) die aus den Ciphertexten berechenbare
Ausgabedifferenz. Formal gilt also die für Tabelleinträge geforderte
Gleichheit:
\begin{align*}
\Diff(S_i(x),S_i(x\xor\diff_i)) &=
S_i(x) \xor S_i(x\xor\diff_i) \\ &=
S_i((m_1)_i \xor (k^0)_i) \xor S_i((m_1)_i \xor (k^0)_i\xor(\Diff(m_1,m_2))_i) \\ &=
S_i((m_1)_i \xor (k^0)_i) \xor S_i((m_1)_i \xor (k^0)_i\xor(m_1)_1\xor(m_2)_i) \\ &=
S_i((m_1)_i \xor (k^0)_i) \xor S_i((m_2)_i \xor (k^0)_i) \\ &=
\Diff(S_i((m_1)_i \xor (k^0)_i), S_i((m_2)_i \xor (k^0)_i)) \\ &=
(P^{-1}(\Diff(c_1,c_2)))_i \\ &=
\diff'_i
\end{align*}
Somit können wir eine Menge an Kandidaten für den Teilschlüssel aufstellen, die eben diese Bedindung
erfüllen:
\[
(k^0)_i \in \{ (m_1) \xor x \mid x\in D^i(\, (\Diff(m_1,m_2))_i, (P^{-1}(\Diff(c_1,c_2))_i\, ) \}
\]
Die Anzahl dieser Kandidaten ist berechenbar als:
\[
\prod_{i=1}^8 |\{ x\in\GF_2^8 \mid S(x) \xor S(x\xor\diff_i) = \diff'_i \} |\]
Um die Kandidatenmenge weiter einzuschränken, führt man diesen Angriff mit
weiteren Paaren durch, der Schlüssel muss im Schnitt aller Kandidatenmengen
liegen.
\paragraph{Fortsetzen auf mehrere Runden}
Für mehrere Runden können wir nicht mehr \enquote{direkt} berechnen, sondern
müssen die einzelnen Zwischendifferenzen raten. Hierzu betrachten wir vorerst
die Wahrscheinlichkeit, von bestimmten Eingabe-Ausgabedifferenzen in einer Runde.
%TODO definition should also be X.y, just like theorem
\begin{definition}[Wahrscheinlichkeit von 1-Runden Charakteristiken]
Sei die Rundenfunktion eine Abbildung \(R:\GF_2^n\to\GF_2^n\). Für die Ein-
und Ausgabedifferenzen \(\diff,\diff'\in\GF_2^n\) sei
\begin{align*}
\Pr(\diff\mapsto\diff' \mid R) :=&
\Pr( \{ x\in\GF_2^n \mid \Delta(R(x), R(x\xor\diff)) = \diff') \} ) \\ =&
\frac{|\{ x\in\GF_2^n \mid \Delta(R(x), R(x\xor\diff)) = \diff') \}|}{|\GF_2^n|}
\end{align*}
die Wahrscheinlichkeit, dass die Eingabedifferenz \(\diff\) unter der Runde \(R\)
die Ausgabedifferenz \(\diff'\) ergibt. Wir nennen hierbei das Tupel
\((\diff,\diff')\) eine 1-Runden-Charakteristik.
\end{definition}
Die Wahrscheinlichkeit für eine ganze Runde ergibt sich hierbei aus den
Wahrscheinlichkeit der einzelnen parallelen S-Boxen der Runde, deren Ein- und
Ausgabedifferenzen wir vorher betrachtet haben, also die Wahrscheinlichkeit,
für jeweiligen einen Eintrag in unserer Differenztabelle.
\begin{theorem}\label{thm:piling-up-lemma-diff}
Sei die Runde \(R=P\circ(S_1\times\dotsb S_{16})\), dann gilt für alle Ein- und
Ausgabedifferenzen \(\diff\), \(\diff'\):
\begin{align*}
\Pr(\diff\mapsto\diff' \mid R) =&
\prod_{i=1}^{16} \Pr( (\diff)_i\mapsto(\diff')_i \mid S_i ) \\ =&
\prod_{i=1}^{16} \Pr( D^i(\diff,\diff') )
\end{align*}
Der Beweis ist ähnlich zu dem des Piling-Up-Lemma~\ref{thm:piling-up-lemma}.
\end{theorem}
Wir werden nun \(r\)-Runden-Charakteristik aus mehreren
\(1\)-Runden-Charakteristiken konstruieren.
\begin{theorem}[Wahrscheinlichkeit über mehreren Runden]\label{thm:piling-up-lemma-diff'}
Seien \(\Gamma=(\delta^1,\delta'^1),\dotsc,(\delta^r,\delta'^r)\) die
\(1\)-Runden-Charakteristiken für die \(r\) Runden, wobei gilt,
dass die Ausgabedifferenz einer Runde \(\delta'^i=\delta^{i+1}\) gleich der
Eingabedifferenz der nachfolgenden ist. Sind die Rundenschlüssel
\(k^0,\dotsc,k^r\) unabhängig gewählt, so gilt für die Gesamtwahrscheinlichkeit
über die Ein- und Ausgabedifferenz der Chiffre
\(E(m) := (R_r\circ\dotsb\circ R_1)(m)\) aus den einzelnen schlüsselversehenen
Rundenfunktionen \(R_i(m) := R(m\xor k^i)\):
\[
p_\Gamma =
\Pr(\diff^1\mapsto\diff'^r \mid E) \geq
\prod_{i=1}^r \Pr(\delta^i\mapsto\delta'^i \mid R)
\]
%TODO wo sind die schlüssel hin?
Auch dieser Beweis ist analog zu dem in der linearen
Kryptoanalyse~\ref{thm:piling-up-lemma'}, und wir haben genauso eine
untere Schranke!
\end{theorem}
\subparagraph{Induktive Konstruktion}
Um nun den Angriff durchzuführen, möchten wir aus einer existierenden
Charakteristik \(\Gamma\) über \(r\) Runden und einer (möglichst hohen)
Wahrscheinlichkeit von \(p_\Gamma\) eine für \(r+1\) konstruieren. Wir wählen
hierzu ein Plaintextpaar \((m,m\xor\diff^i)\) und verschlüsseln dieses mit
unserer \(r+1\)-Runden Chiffre zu \(c,c\xor\diff'^{r+1}\). Mit einer
Wahrscheinlichkeit von \emph{mindestens} \(p_\Gamma\) gilt dann, dass unsere
Erweiterung tatsächlich eine \(r+1\)-Runden Charakteristik ergeben hat, d.\,h.\@
die Ausgabedifferenz der alten Chiffre \(\diff'^r=\diff^{r+1}\) ist gleich derEingabedifferenz der \(r+1\)-ten Runde.
Somit haben wir die Problematik auf die einer \(1\)-Runden-Charakteristik
reduziert, da die Eingabedifferenz in die letzte Runde mit mindestens
\(p_\Gamma\) bekannt ist und wir können die Kandidatenmenge für \(k^r\)
aufstellen um diesen Schlüssel zu raten.
Leider ergibt unsere Erweiterung wahrscheinlich tatsächlich eine korrekte
Charakteristik -- wir können es aber nicht überprüfen, wissen also nicht
ob bei einer Eingabedifferenz von \(\delta^1\) in der ersten Runde, die
Ausgabedifferenz der letzten Runde tatsächlich \(\delta'^r\) ist, da wir
dafür die letzte Runde partiell entschlüsseln müssten wofür wir wiederum
den Schlüssel \(k^{r+1}\) für diese Runde wissen müssten.
Wir wissen aber, ist unsere Konstruktion eine Charakteristik, dann ist
\(k^r\) in der Kandidatenmenge enthalten -- andernfalls sind die Schlüssel
in der Menge gleichverteilt, also ist auch die Wahrscheinlichkeit, dass
\(k^r\) in der Kandidatenmenge ist mindestens \(p_\Gamma\).
\paragraph{Anzahl benötigter Plaintext-Chiffretextpaare}
Sei \(M\) die Anzahl der Plaintextpaare mit Eingabedifferenz \(\delta^i\):
\[
M = \{ (m_1,m_2) \mid \Diff(m_1,m_2) = \delta^i \}
\]
Und \(d\) die durchschnittliche Anzahl der Schlüsselkandidaten für jedes
Paar in \(M\), dann ist \(k^r\) in durchschnittlich mindestens \(p_\Gamma M\)
Kandidatenmengen enthalten -- und ein falscher Schlüssel in mindestens
\((dM)/|\Keys|\).
Man kann nun analog zur linearen Analyse die Anzahl der benötigten Paare
in Abhängigkeit von \(d\) und \(p_\Gamma\) berechnen.
\subsection*{Verhinderung von linearer und differentieller Kryptoanalyse}
%TODO ref Kap. 13
Der Erfolg unserer Angriffe ist abhängig von den Linearitäten bzw.\@ den
Differenztabellen -- diese werden wir uns später in Kapitel%~\ref{}
angucken. Auch verringern mehrere aktive parallele S-Boxen die
Erfolgswahrscheinlichkeit (s.\@ Sätze~\ref{thm:piling-up-lemma}
und~\ref{thm:piling-up-lemma-diff}) -- wir möchten also die Permutation
\(P\) dementsprechend designen. Genauso verringert die Anzahl der
Runden die Erfolgswahrscheinlichkeit (s.\@ Sätze~\ref{thm:piling-up-lemma'}
und~\ref{thm:piling-up-lemma-diff'}).
\section{Algebraische Kryptoanalyse}
%TODO useful resource https://www.staff.uni-mainz.de/pommeren/Cryptology/
Ein Problem von statistischen Anaylsen wie der linearen und der differentiellen
Kryptoanalyse ist die hohe Menge an benötigten Plaintext-Ciphertextpaaren für
die Angriffe. Zudem sind die meisten neueren Blockchiffren im Hinblick auf diese
beiden Angriffsformen so entwickelt, dass die Angriffe nicht durchführbar sind.
Eine andere Methode der Kryptoanalyse ist die Algebraische Analyse.
Dafür werden wir unsere Verschlüsselung als Gleichungen von aus Polynomen mit
mehreren Unbekannten modellieren, deren Lösung uns Rückschlüsse auf den Schlüssel
ziehen lässt.
\subsection{Algebraische Modellierung}
Unsere Verschlüsselungsfunktion einer Blockchiffre ist eine Abbildung
\(E: \GF_2^n\times\GF_2^l \to \GF_2^n\), und wir kennen ein
Plaintext-Ciphertextpaar \((m,c)\). Das Ziel ist die Lösung des
Gleichungssystems \(E(m,x)=c\), mit den Unbekannten
\(x=(x_1,\dotsc,x_l)\in\GF_2^l\). Wir werden uns nun mit der genauren Gestalt
des Gleichungssystems auseinandersetzen. Hierfür wählen wir eine andere
Darstellung um die \(i\)-te Komponente der Bitvektoren zu betrachten. Wir
definieren die Projektion:
\[ E_i: \GF_2^n\times\GF_2^l\to\GF_2 \qquad E_i(m,x) = (E(m,x))_i
\]
Damit lässt sich unser Gleichungssystem schreiben als:
\begin{align*}
E_1(m,x)\xor c_1 =& 0 \\
\vdots& \\
E_n(m,x)\xor c_n =& 0
\end{align*}
Fixieren wir die Nachricht \(m\) ist unsere Funktion \(E_{i,m}(x) := E_i(m,x)\)
eine Boolesche Funktion ist, d.,i.\@ Element der Menge
\(E_{i,x}\in\Fn(\GF_2^l,\GF_2)\). Diese Menge bildet mit der
kanonischen Addition und Multiplikation einen Ring
\((\Fn(\GF_2^l,\GF_2),+,\cdot)\), d.\,i.\@
\[
(f+g)(x) = f(x) + g(x) \qquad (f\cdot g)(x) = f(x) \cdot g(x)
\]
Unser Ziel ist es, diese booleschen Funktion als Polynome mit mehreren
Unbestimmten darzustellen. Wir definieren hierfür erst den booleschen
Polynomring mit \(l\) Platzhaltern \(\GF_2[X_1,\dotsc,X_l]\) wieder mit der
kanonischen Multiplikation und Addition (wie in der Mathematik häufig üblich
notieren wir konventionell damit sowohl den Ring selber, als auch die Menge über
der dieser Ring definiert ist). Nun ist jedes Polynom dieser Menge, die Summe
von einzelnen Monomen \(f_I\) die über ihren Vektor an Potenzen der einzelnen
Unbekannten \(I=(i_1,\dotsc,i_l)\in\mathbb{N}^l\) und dem Koeffizienten \(a\)
eindeutig charakterisiert werden:
\[
f_I = a X^I = a (x_1^{i_1} \dotsb x_l^{i_l})
\]
Jedes Polynom \(f\in\GF_2[X_1,\dotsc,X_l]\) lässt sich dann über die Indexmenge
\(\Idx\subseteq\mathbb{N}^l\) aller Potenzvektoren und den Koeffizienten \(a_I\)
seiner Monome charakterisieren:
\[
f = \sum_{I\in\Idx} f_I(X_1,\dotsc,X_l) = a_I X^I
\]
Wir nennen weiterhin \(X^I\) ein einfaches Monom, wenn seine Potenzen
ausschließlich boolesch sind, also \(I\in\GF_2^l\).
\begin{remark}[Polynome und Polynomfunktionen]
An dieser Stelle unterscheiden wir zwischen Polynomen (Ringelementen mit
Freiheitsgraden)
\[
f = \sum a_i X^i
\]
und Polynomfunktionen (Funktionen, die durch das Ersetzen
der Unbestimmten durch Variablen entstehen):
\[
x \mapsto f(x)
\]
Diese Unterscheidung ist vor Allem bei endlichen Körpern wichtig, da bspw.\@
unterschiedliche Polynome die gleiche Polynomfunktion induzieren können.
\end{remark}
Wir haben nun einen Ring ab booleschen Abbildungen und einen Ring an Polynomen,
und möchten jetzt diese jeweils ineinander überführen.
\begin{theorem}[Auswertefunktion]\label{thm:eval}
Wir definieren eine Auswertefunktion die einem Polynom aus dem obigen Ring
\(f\in\GF_2[X_1,\dots,X_l]\) eine boolesche Funktion zuordnet, in dem sie
der Unbestimmten durch die Funktionsargumente als Variablen ersetzt.
\begin{align*}
\Eval:\, &\GF_2[X_1,\dotsc,X_l] \to\Fn(\GF_2^l,\GF_2) \\
&f \mapsto ((x_1,\dotsc,x_l) \mapsto f(x_1,\dotsc,x_l))
\end{align*}
Diese Funktion ist ein surjektiver Ringhomomorphismus. Zusätzlich ist die
Darstellung der booleschen Funktionen als Summe \emph{einfacher} Monome
eindeutig.
\end{theorem}
\begin{proof}[Beweisansatz]
Wir beweisen hier lediglich die Surjektivität der Abbildung, nicht jedoch, dass
diese strukturerhaltend ist.
Wir möchten zeigen, dass es für jede boolesche Funktion ein Polynom im Ring gibt,
dessen mit \(\Eval\) zugeordnete Funktion eben unsere Funktion ist. Wir
definieren hierzu die charakteristische (Indikator-)funktion:
\begin{align*}
\chi_p:\, &\GF_2^l\to\GF_2 \\
&x\mapsto \begin{cases}
1, & x = p \\
0, &\text{sonst}
\end{cases}
\end{align*}
Wir können nun jede boolesche Funktion \(F\in\Fn(\GF_2^l,\GF_2)\) über die
Auswertung selbiger für alle \(p\in\GF_2^l\) zusammen mit \(\chi_p\) darstellen:
\[
F(x) = \sum_{p\in\GF_2^l} F(p) \chi_p(x)
\]
%TODO \Ima(\Eval) Unterring, abgeschlossen bzgl. +
% f(x) := \Prod_{i=1}^l (X_i\xor p_i\xor 1); \Eval(f) = \chi_p
% \chi_p \in \Ima(\Eval)
Nun möchten wir zeigen, dass die erhaltene Darstellung einer booleschen Funktion
also Polynom in eine Darstellung mit ausschließlich einfachen Monomen überführt
werden kann. Wir nutzen, dass im \(\GF_2\) für alle \(t\geq 1\) gilt, dass
\(x^t = x\). Wir definieren hierfür für jeden jeden Potenzvektor
\(I\in\mathbb{N}^l\) ein \(I'\):
\[
i'_j := \begin{cases}
1, &i_j > 0 \\
0, &\text{sonst}
\end{cases}
\]
Damit ist \(\Eval(X^I) = \Eval(X^{I'})\), somit für alle
\(\Idx\subseteq\mathbb{N}^l\):
\[
\sum_{I\in\Idx} a_I x^I = \sum_{I\in\Idx} a_I x^{I'}
\]
Diese Darstellung ist zudem eindeutig, die Kardinalität beider Mengen gleich ist,
also die der booleschen Funktionen \(|\Fn(\GF_2^l,\GF_2)|=2^{2^l}\) und die
Anzahl der Polynome aus ausschließlich einfachen Monomen (es gibt \(2^l\)
viele unterschiedliche Monome) ist ebenfalls \(2^{2^l}\).
Die Einschränkung von \(\Eval\) auf solche Polynome ist also bijektiv.
\end{proof}
Der Grad eines Polynoms \(f\in\GF_2[X_1,\dotsc,X_l]\) mit
\(f=\sum a_I X^I\) ist definiert als das Maximum
der Summe der Potenzvektoren der einzelnen Monome (d.\,i.\@ das Maximum der
Totalgrade der Monome):
\[
\deg(f) := \max\left\{ \sum_{i\in I} i \;\middle|\; I\in\Idx, a_i \neq 0 \right\}
\]
wir möchten nun diesen Begriff auf die
assoziierten booleschen Funktionen erweitern.
\begin{definition}
Sei \(F\in\Fn(\GF_2^l,\GF_2)\) eine boolesche Funktion, dann ist der Grad
\(\deg(F)\) der Grad des nach~\ref{thm:eval} eindeutig zugeordneten Polynoms
\(f\) mit \(\Eval(f) = F\), welches nur aus einfachen Monomen besteht.
\end{definition}
%TODO ist das gemeint?
Wir nutzen nun diese Definition des Grades einer booleschen Funktion um eine
Korrelation zwischen dem Grad und der Affinität einer Abbildung herzustellen.
Wir bezeichnen hierbei eine Abbildung \(f\) als affin-linear, wenn eine lineare
Funktion \(g(x)=mx\) existiert, sodass \(f(x) = g(x) +m\).
\begin{lemma}\label{lem:affin}
Eine Funktion \(f\) ist genau dann affin, wenn \(\deg(f) \leq 1\). Zudem gilt
für alle \(f\in\Fn(\GF_2^l,\GF_2)\), dass ihr Grad abhängig von der Eingabelänge
beschränkt ist \(\deg(f) \leq l\).\end{lemma}
Kommen wir nun zurück zu unserem Gleichungssystem vom Anfang. Setzen wir
nun \(f_i(x) = E_i(m,x) \xor c_i = 0\), erhalten wir:
\begin{align*}
f_1(x_1,\dotsc,x_l)\xor c_1 =&\; 0 \\
\ \vdots&\; \\
f_n(x_1,\dotsc,x_l)\xor c_n =&\; 0
\end{align*}
Da wir nun diese booleschen Funktionen als Polynomfunktionen sehen können,
müssen wir jetzt die gemeinsamen Nullstellen eines Polynomsystems finden.
Leider ist das kein einfaches Problem.
\begin{theorem}[Garey/Johnson]
Das Problem, eine gemeinsame Nullstelle eines Polynomsystems
\(f_1,\dotsc,f_n\in\GF_2[X_1,\dotsc,X_l]\) zu finden, ist NP-schwer.
\end{theorem}
Für uns hat das einige Konsequenzen. Erstmal ist ein Algorithmus der alle
Polynomsysteme löst vermutlich sehr langsam. Jedoch nimmt die Aussage nichts
über die Polynome an, bspw.\@ ist das Problem für Polynome mit \(\deg(f)\leq 1\)
einfach. Grob kann man sagen, dass für höhere Grade das Problem schwerer wird.
Aber auch das stimmt nicht immer, bspw.\@ für \(x_1=\dotsb=x_l=0\).
\subsection{Angriff über Linearisierung}
Wir können nun den ersten Angriff auf unsere Chiffre fahren. Dieser funktioniert
jedoch nur, wenn unser Polynomsystem überbestimmt ist, d.\,h.\@ wir haben mehr
Gleichungen als Unbekannte. In diesem Fall kann man einige Monome des
Polynomsystems durch weitere voneinander unabhängige Unbekannte ersetzen.
Bspw.\@ können wir über \(\mathbb{R}\) das überbestimmte System betrachten:
\begin{align*}
x^3 + xy + y^5 &= 1 \\
2x^3 - xy &= 0 \\
xy + 3y^5 &= 3
\end{align*}
Setzen wir \(u:=x^3\), \(v:=xy\) und \(w:=y^5\) erhalten wir ein Gleichungssystem
mit gleich vielen Unbekannten wie Gleichungen:
\begin{align*}
u + v + w &= 1 \\
2u - v &= 0 \\
v + 3w &= 3
\end{align*}
Die Lösung des zweiten Systems mit \(u=v=0\) und \(w=1\) führt zur Lösung des
ersten Systems mit \(x=0\) und \(y=1\).
Formal, sei \(d\) der Maximalgrad über alle Polynome in dem Polynomsystem. Nach
\ref{lem:affin} gilt \(d\leq l\). Für die Monome in diesen Polynomen muss
somit gelten, dass ihr Totalgrad wiederum kleinergleich \(d\) ist, somit gibt
es ca.\@ \(l^d\) solcher Monome (Ziehen von \(i\) aus \(l\) Kugeln ohne
Zurücklegen mit Außenvorlassen der Reihenfolge):
\[
\binom{l}{0} + \binom{l}{1} + \dotsb + \binom{l}{d} \approx l^d
\]
Nutzen wir Linearisierung, erhalten wir also auch ungefähr \(l^d\) Variablen,
benötigen zur Lösung dementsprechend auch genausoviele unabhängige Gleichungen.
Die Laufzeit ist hierbei (bspw.\@ mit dem Gauß-Algorithmus) kubisch, sprich
\(\mathcal{O}(n^3)\) mit der Anzahl der Variablen \(n\). Es ergibt sich eine
Gesamtlaufzeit von \(\mathcal{O}(l^{3d}\).
Um gegen diesen Angriff Gegenmaßnahmen zu treffen benötigen wir eine hohe Anzahl
an Variablen die bei der Linearisierung entstehen. Dies geschieht durch einen
hohen algebraischen Grad der Polynome (potentiell viele Variablen) und dicht
besetzte Polynome (d.\,h.\@ Polynome aus vielen Monomen).
\end{document}