rapport/main.tex

   1 \documentclass[a4paper,10pt]{article}
   2
   3 \usepackage[francais]{babel}
   4 \usepackage[utf8]{inputenc}
   5 \usepackage[T1]{fontenc}
   6 \usepackage{lmodern}
   7
   8 \usepackage{amssymb,amsmath,amsthm}
   9
  10 \usepackage{graphicx}
  11 \usepackage{listings}
  12 \usepackage{url}
  13 \usepackage{upquote}
  14 \usepackage{color}
  15 \usepackage[usenames,dvipsnames]{xcolor}
  16
  17 \title{ICR - Labo \#3 : \textit{Attaque par faute contre RSA-CRT}}
  18 \author{G.Burri}
  19
  20
  21 \begin{document}
  22
  23 \nocite{*}
  24
  25 \maketitle
  26
  27
  28 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  29 \section{Introduction}
  30
  31 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.
  32
  33
  34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  35 \section{RSA-CRT}
  36
  37 \subsection{Implémentation}
  38
  39 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}}.
  40
  41 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}}.
  42
  43
  44 \subsubsection*{Question 1.1 : Comment s'assure-t-on que les routines implémentées fonctionnent correctement ?}
  45
  46 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).
  47
  48 Les tests peuvent être lancés avec la commande suivante :
  49
  50 \begin{verbatim}
  51 qbs run -- tests
  52 \end{verbatim}
  53
  54
  55 \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 ?}
  56
  57 Les mesures sont réalisées en générant $20'000$ signatures. Vingt paires de clefs différentes sont utilisées.
  58
  59 Les temps sont mesurés à l'aide de la commande suivante :
  60
  61 \begin{verbatim}
  62 qbs run release -- time-measures
  63 \end{verbatim}
  64
  65 \begin{itemize}
  66    \item \emph{RSA} standard : $14'800\, ms$ ($740\, \mu s$ par signature).
  67    \item \emph{RSA CRT} : $4'466\, ms$ ($223, \mu s$ par signature).
  68 \end{itemize}
  69
  70 La génération de signatures avec \emph{RSA CRT} est en moyenne 3.25 fois plus rapide.
  71
  72
  73 \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} ?}
  74
  75 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.
  76
  77 {\setlength{\abovedisplayskip}{0pt}
  78 \begin{flalign*}
  79    e &= 65537 \\
  80    \mathbf{p, q} &&\text{deux nombres premiers de 512 bits choisis de manière aléatoire} \\
  81    n &= p \cdot q \\
  82    \varphi(n) &= (p - 1) \cdot (q - 1) \\
  83    d &= e^{-1} ~(mod ~\varphi(n)) \\
  84    \mathbf{d_p} &= d ~(mod ~p - 1) \\
  85    \mathbf{d_q} &= d ~(mod ~q - 1) \\
  86    \mathbf{q_{inv}} &= q^{-1} ~(mod ~p)
  87 \end{flalign*}
  88
  89
  90 La signature $sig$ du message $m$ peut être ensuite calculée comme suit.
  91
  92 {\setlength{\abovedisplayskip}{0pt}
  93 \begin{flalign*}
  94    s_p &= m^{d_p} ~(mod ~p) &\\
  95    s_q &= m^{d_q} ~(mod ~q) \\
  96    \mathbf{sig} &= s_q + ((q_{inv} \cdot (s_p - s_q)) ~mod ~p) \cdot q
  97 \end{flalign*}
  98
  99
 100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 101 \section{L'attaque de \emph{Boneh-DeMillo-Lipton}}
 102
 103 \subsection{Fonctionnement}
 104
 105 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 :
 106
 107 {\setlength{\abovedisplayskip}{0pt}
 108 \begin{flalign*}
 109    q &= gcd(m - sig'^e, n) &
 110 \end{flalign*}
 111
 112 Où :
 113
 114 \begin{itemize}
 115    \item $m$ : le message signé avec $sig'$.
 116    \item $sig'$ : la signature calculée avec un $p$ altéré.
 117    \item $e$ : l'exposant public.
 118    \item $n$ : le module public.
 119 \end{itemize}
 120
 121
 122 Nous pouvons alors facilement retrouver $p$:
 123
 124 {\setlength{\abovedisplayskip}{0pt}
 125 \begin{flalign*}
 126    p &= n / q &
 127 \end{flalign*}
 128
 129 Il est alors trivial de reconstituer la clef privée à partir de $p$ et $q$.
 130
 131 \subsubsection*{Question 2.1 : En pratique, comment est-il possible d'introduire des fautes dans l'implémentation d'un algorithme cryptographique ?}
 132
 133 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} :
 134
 135 \begin{itemize}
 136    \item Variation du niveau de voltage de l'alimentation électrique ;
 137    \item Injection d’irrégularités dans le \emph{clock} de l'horloge ;
 138    \item Champs magnétique ;
 139    \item Émission de radiations ;
 140    \item Surchauffe de l'appareil ;
 141    \item Exposition à une lumière intense.
 142 \end{itemize}
 143
 144 Il faut aussi ajouter qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies dans les calculs.
 145
 146
 147 \subsubsection*{Question 2.2 : Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?}
 148
 149 Oui, il est possible de récupérer $p$ ou $q$ si l'on possède une signature valide mais pas le message original :
 150
 151 {\setlength{\abovedisplayskip}{0pt}
 152 \begin{flalign*}
 153    q &= gcd(sig - sig'^e, n) &
 154 \end{flalign*}
 155
 156 Où :
 157
 158 \begin{itemize}
 159    \item $sig$ : la signature correctement calculée.
 160    \item $sig'$ : la signature calculée avec un $p$ altéré.
 161 \end{itemize}
 162
 163
 164
 165 \subsection{Implémentation}
 166
 167 Cette attaque est illustrée dans la fonction \texttt{Tests::doAttack()}. Pour tester cette attaque :
 168
 169 \begin{verbatim}
 170 qbs run -- attack
 171 \end{verbatim}
 172
 173
 174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 175 \section{Le \flqq truc\frqq\ de \emph{Shamir}}
 176
 177 \subsection{Fonctionnement}
 178
 179 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$.
 180
 181 Voici ce qui a été implémenté :
 182
 183 {\setlength{\abovedisplayskip}{0pt}
 184 \begin{flalign*}
 185    \mathbf{r} &&\text{un nombre premier aléatoire de 64 bits} \\
 186    exp &= d ~mod ~\varphi(p \cdot \mathbf{r}) \\
 187    s_{pr} &= m^{exp} ~mod ~p \cdot \mathbf{r} \\
 188    s_{qr} &= m^{exp} ~mod ~q \cdot \mathbf{r}
 189 \end{flalign*}
 190
 191 Il faut alors vérifier cette égalité :
 192
 193 {\setlength{\abovedisplayskip}{0pt}
 194 \begin{flalign*}
 195    s_{pr} ~mod ~\mathbf{r} &= s_{qr} ~mod ~\mathbf{r} &
 196 \end{flalign*}
 197
 198 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é.
 199
 200 {\setlength{\abovedisplayskip}{0pt}
 201 \begin{flalign*}
 202    s_p &= s_{pr} ~mod ~p  \\
 203    s_q &= s_{qr} ~mod ~q &
 204 \end{flalign*}
 205
 206 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}.
 207
 208
 209 \subsection{Implémentation}
 210
 211 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 :
 212
 213 \begin{verbatim}
 214 qbs run -- attack-fixed
 215 \end{verbatim}
 216
 217
 218
 219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 220 \section{Conclusion}
 221
 222 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}.
 223
 224 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}.
 225
 226
 227 \bibliographystyle{plain}
 228 \bibliography{main}
 229
 230 \end{document}