\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{algpseudocode}

%\usepackage[dvips]{graphicx}

\newtheorem{theoreme}{Théorème}

\def\mod{~\mathrm{mod}~}
\def\Z{\mathbb{Z}}

\title{TD 4 de Cryptologie}
\date{Lundi 7 novembre 2005}

\begin{document}
\maketitle

\section*{Cryptanalyse linéaire}

On considère un algorithme de chiffrement par bloc du type réseau de
substitution et permutation (\emph{Substitution-Permutation Network}
ou SPN) qui travaille sur une taille de bloc de $16$ bits.
On numérote les bits d'un bloc de droite à gauche de $0$ à $15$, le
bit $15$ étant donc le bit de poids fort..

La substitution $S$ manipule des blocs de $4$ bits, représentés par un
chiffre hexadécimal, et sa table de valeurs est la suivante :

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Entrée & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F\\
\hline
Sortie & E & 4 & D & 1 & 2 & F & B & 8 & 3 & A & 6 & C & 5 & 9 & 0 & 7\\
\hline
\end{tabular}
\end{center}
La permutation $P$ échange les $16$ bits du bloc en envoyant un bit
sur la position miroir des bits de sa position. Par exemple le bit en
position $2 = 0010_2$ est envoyé sur la position $0100_2 = 4$.

Le chiffrement complet d'un bloc se fait en 4 tours :
\begin{algorithm}
\caption{Procédure de chiffrement}
\begin{algorithmic}[1]
\Statex \textsc{Entrée}: $M = M_3M_2M_1M_0$, $(K_i)_{i=1, 4}$.
\For{$i \gets 1 \mathrm{~to~} 4$}
    \State $C \gets M \oplus K_i$ \Comment{\emph{Subkey mixing}, bloc
    de $16$ bits}
    \For{$j \gets 0 \mathrm{~to~} 4$} \Comment{substitution, par blocs
    de $4$ bits}
	\State $Z_j \gets S(C_j)$
    \EndFor
    \State $M \gets P(M)$ \Comment{permutation, bloc de $16$ bits}
\EndFor
\State \Return $M$
\end{algorithmic}
\end{algorithm}
Les $K_i$ sont les sous-clefs de chiffrements de chaque tour et
constituent donc la cible de la cryptanalyse.
\begin{enumerate}
\item Donner l'image par la permutation $P$ des blocs \texttt{2},
\texttt{A}, \texttt{7}.
\item Calculer le chiffré après 2 tours du message $M
=$~\texttt{BEEF} en prenant $K_1 = $~\texttt{DEAF}, $K_2 =
$~\texttt{CAFE}.
\item Quel est l'intérêt de la permutation du dernier tour ?
\item Comment s'effectue le déchiffrement ?
\item Montrer que le chiffrement \emph{AES} est aussi du type SPN en
identifiant les étapes de permutation, de substitution et de
\emph{subkey mixing}.
\end{enumerate}
Le principe de la cryptanalyse linéaire est d'utiliser des
approximations linéaires de la substitution $S$ et de déterminer des
bits de la clef à partir de couples de clair/chiffrés connus.

Si $X = X_{15}X_{14}\ldots X_1X_0$ et $Y = Y_{15}Y_{14}\ldots
Y_{1}Y_0$ avec $Y= S(X)$, on calcule les
probabilités de relations du type
\[ X_0 \oplus X_1 \oplus X_{12} \oplus Y_2 \oplus Y_4 = 0 \]
Plus précisément on s'intéresse au biais de la probabilité et on écrit 
$\mathrm{Pr}(X_0 \oplus X_1 \oplus X_{12} \oplus Y_2 \oplus Y_4 = 0) =
1/2 + \varepsilon$.
\begin{enumerate}
\setcounter{enumi}{5}
\item Montrer que si $X_1$ et $X_2$ sont deux variables aléatoires
booléennes indépendantes de biais $\varepsilon_1$ et $\varepsilon_2$, i.e.
$\mathrm{Pr}(X_i = 0) = 1/2 + \varepsilon_i$, alors le biais de la
variable aléatoire $X_1 \oplus X_2$ est $2\varepsilon_1
\varepsilon_2$.
\item Montrer que si $X_1, X_2, \ldots X_n$ sont $n$ variables
aléatoires booléennes indépendantes de biais $\varepsilon_1,
\varepsilon_2, \ldots, \varepsilon_n$ alors le biais de $X_1 \oplus
X_2 \oplus \ldots \oplus X_n$ est $2^{n-1}\prod_{i=1}^n
\varepsilon_i$.
\item Pour la substitution $S$ donnée calculer le biais des
expressions suivantes~:
    \begin{itemize}
    \item $X_3 \oplus X_0 \oplus Y_2$,
    \item $X_3 \oplus X_1 \oplus X_0 \oplus Y_2$,
    \item $X_2 \oplus Y_2 \oplus Y_0$,
    \item une somme de $X_i$ sans occurence d'un seul $Y_i$,
    \item une somme de $Y_i$ sans occurence d'un seul $X_i$.
    \end{itemize}
\item Combien y a-t-il d'expressions possibles dont on peut calculer
les biais pour $S$~?
\item Quelle est la complexité du calcul de tous ces biais~?
\end{enumerate}
On considère les bits $11$, $9$ et $8$ du bloc clair notés $P_{11}$,
$P_{9}$
et $P_8$. On note $K_{i,j}$ le $j$-ième bit de la clef de l'étape de
chiffrement $i$, et on appelle $U_{10}$ et $U_8$ les bits $10$ et $8$
après deux tours de chiffrement.
\begin{enumerate}
\setcounter{enumi}{10}
\item Calculer le biais de l'expression
\[ U_{10} \oplus U_{8} \oplus P_{11} \oplus P_{9} \oplus P_8 
    \oplus K_{1,11} \oplus K_{1,9} \oplus K_{1,8} \oplus K_{2,10}
    \oplus K_{2,8} \]
\item On connait un grand nombre de couples (clair, chiffré après deux
tours). Comment s'en servir et quelle information obtient-on~?
\end{enumerate}
\end{document}