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
  32
  33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  34 \section{RSA-CRT}
  35
  36 \subsection{Implémentation}
  37
  38 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}}.
  39
  40 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}}.
  41
  42
  43 \subsubsection*{Question 1.1 : Comment s'assure-t-on que les routines implémentées fonctionnent correctement ?}
  44
  45 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).
  46
  47 Les tests peuvent être lancés avec la commande suivante :
  48
  49 \begin{verbatim}
  50 qbs run -- tests
  51 \end{verbatim}
  52
  53
  54 \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 ?}
  55
  56 Les mesures sont réalisées en générant $20'000$ signatures. Vingt paires de clefs différentes sont utilisées.
  57
  58 Les temps sont mesurés à l'aide de la commande suivante :
  59
  60 \begin{verbatim}
  61 qbs run release -- time-measures
  62 \end{verbatim}
  63
  64 \begin{itemize}
  65    \item \emph{RSA} standard : $14'800\, ms$ ($740\, \mu s$ par signature).
  66    \item \emph{RSA CRT} : $4'466\, ms$ ($223, \mu s$ par signature).
  67 \end{itemize}
  68
  69 La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus rapide.
  70
  71
  72 \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} ?}
  73
  74 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.
  75
  76 {\setlength{\abovedisplayskip}{-4pt}
  77 \begin{flalign*}
  78    e &= 65537 \\
  79    \mathbf{p, q} &&\text{deux nombres premiers de 512 bits choisis de manière aléatoire} \\
  80    n &= p * q \\
  81    \varphi(n) &= (p - 1) * (q - 1) \\
  82    d &= e^{-1} ~(mod ~\varphi(n)) \\
  83    \mathbf{d_p} &= d ~(mod ~p - 1) \\
  84    \mathbf{d_q} &= d ~(mod ~q - 1) \\
  85    \mathbf{q_{inv}} &= q^{-1} ~(mod ~p)
  86 \end{flalign*}
  87
  88
  89 La signature $sig$ du message $m$ peut être ensuite calculée comme suit.
  90
  91 {\setlength{\abovedisplayskip}{-4pt}
  92 \begin{flalign*}
  93    s_p &= m^{d_p} ~(mod ~p) &\\
  94    s_q &= m^{d_q} ~(mod ~q) \\
  95    \mathbf{sig} &= s_q + ((q_{inv} \cdot (s_p - s_q)) ~mod ~p) \cdot q
  96 \end{flalign*}
  97
  98
  99 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 100 \section{L'attaque de \emph{Boneh-DeMillo-Lipton}}
 101
 102 \subsection{Fonctionnement}
 103
 104 D'après le document \cite{Boneh-DeMillo-Lipton-attack} :
 105
 106 {\setlength{\abovedisplayskip}{-4pt}
 107 \begin{flalign*}
 108    q &= gcd(m - sign'^e, n) &
 109 \end{flalign*}
 110
 111 Où :
 112
 113 \begin{itemize}
 114    \item $m$ : le message signé avec $sign'$
 115    \item $sign'$ : la signature calculée avec un $p$ altéré.
 116 \end{itemize}
 117
 118
 119 Nous pouvons alors facilement retrouver $p$:
 120
 121 {\setlength{\abovedisplayskip}{-4pt}
 122 \begin{flalign*}
 123    p &= n / q &
 124 \end{flalign*}
 125
 126 Il est alors trivial de reconstituer la clef privée à partir de $p$ et $q$.
 127
 128 \subsubsection*{Question 2.1 : En pratique, comment est-il possible d'introduire des fautes dans l'implémentation d'un algorithme cryptographique ?}
 129
 130 Voici une liste de techniques issues du document \cite{Barenghi-Breveglieri-Koren-Naccache-fault-injection} :
 131
 132 \begin{itemize}
 133    \item Variation du niveau de voltage de l'alimentation électrique ;
 134    \item Injection d’irrégularités dans le \emph{clock} de l'horloge ;
 135    \item Champs magnétique ;
 136    \item Émission de radiations ;
 137    \item Surchauffe de l'appareil ;
 138    \item Exposition à une lumière intense.
 139 \end{itemize}
 140
 141 Il faut aussi ajouté qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies.
 142
 143
 144 \subsubsection*{Question 2.2 : Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?}
 145
 146 Oui, il est possible de récupérer $p$ ou $q$ s'il l'on possède une signature valide mais pas le message original :
 147
 148 {\setlength{\abovedisplayskip}{-4pt}
 149 \begin{flalign*}
 150    q &= gcd(sign - sign'^e, n) &
 151 \end{flalign*}
 152
 153 Où :
 154
 155 \begin{itemize}
 156    \item $sign$ : la signature correctement calculée.
 157    \item $sign'$ : la signature calculée avec un $p$ altéré.
 158 \end{itemize}
 159
 160
 161
 162 \subsection{Implémentation}
 163
 164 Cette attaque est illustrée dans la fonction \texttt{Tests::doAttack()}. Pour tester cette attaque :
 165
 166 \begin{verbatim}
 167 qbs run -- attack
 168 \end{verbatim}
 169
 170
 171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 172 \section{Le \flqq truc \frqq de \emph{Shamir}}
 173
 174 \subsection{Fonctionnement}
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 185 \section{Conclusion}
 186
 187
 188 \bibliographystyle{plain}
 189 \bibliography{main}
 190
 191 \end{document}