1 \documentclass[a4paper,
10pt
]{article
}
3 \usepackage[francais
]{babel
}
4 \usepackage[utf8
]{inputenc}
5 \usepackage[T1]{fontenc}
8 \usepackage{amssymb,amsmath,amsthm
}
15 \usepackage[usenames,dvipsnames
]{xcolor
}
17 \title{ICR - Labo \
#3 :
\textit{Attaque par faute contre RSA-CRT
}}
28 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
29 \section{Introduction
}
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.
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
37 \subsection{Implémentation
}
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
}}.
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
}}.
44 \subsubsection*
{Question
1.1 : Comment s'assure-t-on que les routines implémentées fonctionnent correctement ?
}
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).
48 Les tests peuvent être lancés avec la commande suivante :
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 ?
}
57 Les mesures sont réalisées en générant $
20'
000$ signatures. Vingt paires de clefs différentes sont utilisées.
59 Les temps sont mesurés à l'aide de la commande suivante :
62 qbs run release -- time-measures
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).
70 La génération de signatures avec
\emph{RSA CRT
} est en moyenne
3.25 fois plus rapide.
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
} ?
}
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.
77 {\setlength{\abovedisplayskip}{0pt
}
80 \mathbf{p, q
} &&
\text{deux nombres premiers de
512 bits choisis de manière aléatoire
} \\
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)
90 La signature $sig$ du message $m$ peut être ensuite calculée comme suit.
92 {\setlength{\abovedisplayskip}{0pt
}
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
100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
101 \section{L'attaque de
\emph{Boneh-DeMillo-Lipton
}}
103 \subsection{Fonctionnement
}
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 :
107 {\setlength{\abovedisplayskip}{0pt
}
109 q &= gcd(m - sig'^e, n) &
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.
122 Nous pouvons alors facilement retrouver $p$:
124 {\setlength{\abovedisplayskip}{0pt
}
129 Il est alors trivial de reconstituer la clef privée à partir de $p$ et $q$.
131 \subsubsection*
{Question
2.1 : En pratique, comment est-il possible d'introduire des fautes dans l'implémentation d'un algorithme cryptographique ?
}
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
} :
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.
144 Il faut aussi ajouter qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies dans les calculs.
147 \subsubsection*
{Question
2.2 : Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?
}
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 :
151 {\setlength{\abovedisplayskip}{0pt
}
153 q &= gcd(sig - sig'^e, n) &
159 \item $sig$ : la signature correctement calculée.
160 \item $sig'$ : la signature calculée avec un $p$ altéré.
165 \subsection{Implémentation
}
167 Cette attaque est illustrée dans la fonction
\texttt{Tests::doAttack()
}. Pour tester cette attaque :
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
175 \section{Le
\flqq truc
\frqq\ de
\emph{Shamir
}}
177 \subsection{Fonctionnement
}
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$.
181 Voici ce qui a été implémenté :
183 {\setlength{\abovedisplayskip}{0pt
}
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
}
191 Il faut alors vérifier cette égalité :
193 {\setlength{\abovedisplayskip}{0pt
}
195 s_
{pr
} ~mod ~
\mathbf{r
} &= s_
{qr
} ~mod ~
\mathbf{r
} &
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é.
200 {\setlength{\abovedisplayskip}{0pt
}
202 s_p &= s_
{pr
} ~mod ~p \\
203 s_q &= s_
{qr
} ~mod ~q &
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
}.
209 \subsection{Implémentation
}
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 :
214 qbs run -- attack-fixed
219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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
}.
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
}.
227 \bibliographystyle{plain
}