Attack implementation.

[crypto_lab3.git] / rapport / main.tex

diff --git a/rapport/main.tex b/rapport/main.tex
index eeeafa4..f8ebe68 100644 (file)
--- a/rapport/main.tex
+++ b/rapport/main.tex
@@ -5,6 +5,8 @@
 \usepackage[T1]{fontenc}
 \usepackage{lmodern}
 
+\usepackage{amssymb,amsmath,amsthm}
+
 \usepackage{graphicx}
 \usepackage{listings}
 \usepackage{url}
@@ -35,12 +37,12 @@
 
 L'implémentation utilise le langage \emph{C++11}, le compilateur \emph{GCC} 4.9.1, la \emph{library} \emph{GMP} 6.0.0 ainsi que la système de \emph{build} \emph{QBS}~\footnote{\url{http://qt-project.org/wiki/qbs}}.
 
-Le fichier \emph{*.qbs} peut-être ouvert à l'aide de \emph{Qt Creator}~\footnote{\url{http://qt-project.org/wiki/Category:Tools::QtCreator}}
+Le fichier \emph{*.qbs} peut-être ouvert à l'aide de l'environnement de développement \emph{Qt Creator}~\footnote{\url{http://qt-project.org/wiki/Category:Tools::QtCreator}}.
 
 
 \subsubsection*{Question 1.1 : Comment s'assure-t-on que les routines implémentées fonctionnent correctement ?}
 
-Pour chaque version, standard et restes chinois, une paire de clefs est générée puis trois messages sont testés avec des valeurs différentes correspondantes à $n$, $n-1$ et $n / 2$. Pour le premier cas la vérification de la signature ne doit pas fonctionner car le message est trop grand, dans les deux autres cas, on vérifie la signature ainsi qu'une signature altérée (incrémentée de 1).
+Pour chaque version, standard et restes chinois, une paire de clefs est générée puis trois messages sont testés avec des valeurs différentes correspondantes à $n$, $n-1$ et $n / 2$. Pour le premier cas la vérification de la signature ne doit pas fonctionner car le \emph{plaintext} est trop grand, dans les deux autres cas, on vérifie la signature ainsi qu'une signature altérée (incrémentée de 1).
 
 Les tests peuvent être lancés avec la commande suivante :
 
@@ -69,17 +71,82 @@ La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus r
 
 \subsubsection*{Question 1.3 : Quels sont les valeurs que l'on peut pré-calculer est stocker hormis $n$ et $d$ afin d'améliorer la vitesse de calcul d'une signature avec \emph{RSA-CRT} ?}
 
+Les valeurs de $p$, $q$, $d_p$, $d_q$ et $q_{inv}$ sont mémorisées en tant que clef privée. Celles ci sont calculées comme suit.
+
+\begin{flalign*}
+   e &= 65537 \\
+   \mathbf{p, q} &&\text{deux nombres premiers de 512 bits choisis de manière aléatoire} \\
+   n &= p * q \\
+   \varphi(n) &= (p - 1) * (q - 1) \\
+   d &= e^{-1} ~(mod ~\varphi(n)) \\
+   \mathbf{d_p} &= d ~(mod ~p - 1) \\
+   \mathbf{d_q} &= d ~(mod ~q - 1) \\
+   \mathbf{q_{inv}} &= q^{-1} ~(mod p)
+\end{flalign*}
+
+
+La signature $sig$ du message $m$ peut être ensuite calculée comme suit.
+
+\begin{flalign*}
+   s_p &= m^{d_p} ~(mod ~p) &\\
+   s_q &= m^{d_q} ~(mod ~q) \\
+   \mathbf{sig} &= s_q + ((q_{inv} \cdot (s_p - s_q)) ~mod ~p) \cdot q
+\end{flalign*}
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{L'attaque de \emph{Boneh-DeMillo-Lipton}}
 
 \subsection{Fonctionnement}
 
-(maths)
+D'après le document \cite{Boneh-DeMillo-Lipton-attack} :
+
+\begin{flalign*}
+   q &= gcd(m - sign'^e, n) &
+\end{flalign*}
+
+Où :
+
+\begin{itemize}
+   \item $m$ : le message signé avec $sign'$
+   \item $sign'$ : la signature calculé avec un $p$ altéré.
+\end{itemize}
+
+
+Nous pouvons alors facilement retrouver $p$:
+
+\begin{flalign*}
+   p &= n / q &
+\end{flalign*}
+
+Il est alors trivial de reconstituer la clef privée à partir de $p$ et $q$.
 
 \subsubsection*{Question 2.1 : En pratique, comment est-il possible d'introduire des fautes dans l'implémentation d'un algorithme cryptographique ?}
 
-\subsubsection*{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non détérministe ?}
+Voici une liste de techniques issues du document \cite{Barenghi-Breveglieri-Koren-Naccache-fault-injection} :
+
+\begin{itemize}
+   \item Variation du niveau de voltage de l'alimentation électrique ;
+   \item Injection d’irrégularités dans le \emph{clock} de l'horloge ;
+   \item Champs magnétique ;
+   \item Émission de radiations ;
+   \item Surchauffe de l'appareil ;
+   \item Exposition à une lumière intense.
+\end{itemize}
+
+
+\subsubsection*{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?}
+
+
+
+
+\subsection{Implémentation}
+
+Cette attaque est illustrée dans la fonction \texttt{Tests::doAttack()}. Pour tester cette attaque :
+
+\begin{verbatim}
+qbs run -- attack 
+\end{verbatim}
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -93,9 +160,11 @@ La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus r
 \section{Conclusion}
 
 
-% http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
+%                       
+% Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures
+
 
-%\bibliographystyle{plain}
-%\bibliography{main}
+\bibliographystyle{plain}
+\bibliography{main}
 
 \end{document}