X-Git-Url: http://git.euphorik.ch/?a=blobdiff_plain;f=rapport%2Fmain.tex;h=ef230e36225c3afececa86b00cb0439d72c3e927;hb=5b2785dd710151d81e6f6af4fd6ae48521068e41;hp=19a579fee5e508c58e47d2a8233bafb67044a5fb;hpb=7975d02c6c1ee679a236087e86955c086f1a9a8e;p=crypto_lab3.git

diff --git a/rapport/main.tex b/rapport/main.tex
index 19a579f..ef230e3 100644
--- 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}
@@ -26,15 +28,203 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Introduction}
 
+Le but de ce laboratoire et de mettre en œuvre l'attaque \emph{Boneh-DeMillo-Lipton} sur notre propre implémentation de \emph{RSA-CRT}~\footnote{\emph{Chinese remainder theorem}}. Puis de décrire et d'implémenter le \flqq truc\frqq\ de \emph{Shamir} afin de prévenir ce type d'attaque.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{RSA-CRT}
+
+\subsection{Implémentation}
+
+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 le 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 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 \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 :
+
+\begin{verbatim}
+qbs run -- tests 
+\end{verbatim}
+
+
+\subsubsection*{Question 1.2 : Quel est le gain en terme de temps d'exécution lors de la création d'une signature avec \emph{RSA-CRT} par rapport à la version standard ?}
+
+Les mesures sont réalisées en générant $20'000$ signatures. Vingt paires de clefs différentes sont utilisées.
+
+Les temps sont mesurés à l'aide de la commande suivante :
+
+\begin{verbatim}
+qbs run release -- time-measures 
+\end{verbatim}
+
+\begin{itemize}
+   \item \emph{RSA} standard : $14'800\, ms$ ($740\, \mu s$ par signature).
+   \item \emph{RSA CRT} : $4'466\, ms$ ($223, \mu s$ par signature).
+\end{itemize}
+
+La génération de signatures avec \emph{RSA CRT} est en moyenne 3.25 fois plus rapide.
+
+
+\subsubsection*{Question 1.3 : Quelles sont les valeurs que l'on peut pré-calculer et 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.
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+   e &= 65537 \\
+   \mathbf{p, q} &&\text{deux nombres premiers de 512 bits choisis de manière aléatoire} \\
+   n &= p \cdot q \\
+   \varphi(n) &= (p - 1) \cdot (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.
+
+{\setlength{\abovedisplayskip}{0pt}
+\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}
+
+D'après le document \flqq On the Importance of Eliminating Errors in Cryptographic Computations\frqq~\cite{Boneh-DeMillo-Lipton-attack} $q$ peut être retrouvé comme suit :
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+   q &= gcd(m - sig'^e, n) &
+\end{flalign*}
+
+Où :
+
+\begin{itemize}
+   \item $m$ : le message signé avec $sig'$.
+   \item $sig'$ : la signature calculée avec un $p$ altéré.
+   \item $e$ : l'exposant public.
+   \item $n$ : le module public.
+\end{itemize}
+
 
+Nous pouvons alors facilement retrouver $p$:
+
+{\setlength{\abovedisplayskip}{0pt}
+\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 ?}
+
+Voici une liste de techniques issues du document \flqq Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures\frqq~\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}
+
+Il faut aussi ajouter qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies dans les calculs.
+
+
+\subsubsection*{Question 2.2 : Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?}
+
+Oui, il est possible de récupérer $p$ ou $q$ si l'on possède une signature valide mais pas le message original :
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+   q &= gcd(sig - sig'^e, n) &
+\end{flalign*}
+
+Où :
+
+\begin{itemize}
+   \item $sig$ : la signature correctement calculée. 
+   \item $sig'$ : la signature calculée avec un $p$ altéré.
+\end{itemize}
+
+
+
+\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}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Le \flqq truc\frqq\ de \emph{Shamir}}
+
+\subsection{Fonctionnement}
+
+Le principe consiste à introduire un nombre généré aléatoirement $r$ dans le calcul de $s_p$ et $s_q$ puis de vérifier que ces deux parties congrues modulo $r$.
+
+Voici ce qui a été implémenté :
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+   \mathbf{r} &&\text{un nombre premier aléatoire de 64 bits} \\
+   exp &= d ~mod ~\varphi(p \cdot \mathbf{r}) \\
+   s_{pr} &= m^{exp} ~mod ~p \cdot \mathbf{r} \\
+   s_{qr} &= m^{exp} ~mod ~q \cdot \mathbf{r}
+\end{flalign*}
+
+Il faut alors vérifier cette égalité :
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+   s_{pr} ~mod ~\mathbf{r} &= s_{qr} ~mod ~\mathbf{r} &
+\end{flalign*}
+
+Si celle ci est correcte alors on calcul $s_p$ et $s_q$ de la manière suivante, la signature est alors calculée de la même façon que montrée à la question 1.3. Si l'égalité n'est pas correct alors un message d'erreur est renvoyé.
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+   s_p &= s_{pr} ~mod ~p  \\
+   s_q &= s_{qr} ~mod ~q &
+\end{flalign*}
+
+Une explication complète est fournit par le document \flqq Improved Shamir's CRT-RSA Algorithm: A Revisit with the Modulus Chaining Method\frqq~\cite{Lee-Choi-Koren-Dooho-improved-shamirs-crt-rsa}.
+
+
+\subsection{Implémentation}
+
+Une tentative d'attaque sur un code utilisant le \flqq truc\frqq\ de \emph{Shamir} est illustrée dans la fonction \texttt{Tests::doAttackFixed()}. Pour tester cette attaque :
+
+\begin{verbatim}
+qbs run -- attack-fixed
+\end{verbatim}
 
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Conclusion}
 
+L'implémentation de RSA à l'aide des restes chinois permet de gagner du temps \emph{CPU} lors de la signature. Un facteur 3.25 a été observé. Cette implémentation étant vulnérable à l'attaque \emph{Boneh-DeMillo-Lipton}, l'implémentation du \flqq truc\frqq\ de \emph{Shamir} a permis de prévenir cette attaque tout en étant 2.46 fois plus rapide que l'implémentation standard de \emph{RSA}.
+
+Il faut bien garder à l'esprit que l'implémentation réalisée ici est de type \emph{textbook} et ne doit pas être utilisée telle quelle en pratique. Il manque notamment l'ajout de bourrage tel que \emph{OAEP}.
+
 
-%\bibliographystyle{plain}
-%\bibliography{main}
+\bibliographystyle{plain}
+\bibliography{main}
 
 \end{document}