\usepackage[T1]{fontenc}
\usepackage{lmodern}
+\usepackage{amssymb,amsmath,amsthm}
+
\usepackage{graphicx}
\usepackage{listings}
\usepackage{url}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 la système de \emph{build} \emph{QBS}~\footnote{\url{http://qt-project.org/wiki/qbs}}.
+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 \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 :
\item \emph{RSA CRT} : $4'466\, ms$ ($223, \mu s$ par signature).
\end{itemize}
-La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus rapide.
+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*}
-\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} ?}
+
+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*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fonctionnement}
-(maths)
+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 ?}
-\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 \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}}
+\section{Le \flqq truc\frqq\ de \emph{Shamir}}
\subsection{Fonctionnement}
-(maths)
+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}.
-% http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
-%\bibliographystyle{plain}
-%\bibliography{main}
+\bibliographystyle{plain}
+\bibliography{main}
\end{document}
projects / crypto_lab3.git / blobdiff