From 5b2785dd710151d81e6f6af4fd6ae48521068e41 Mon Sep 17 00:00:00 2001 From: Ummon Date: Mon, 12 Jan 2015 15:09:25 +0100 Subject: [PATCH] Shamir's trick implementation. --- rapport/main.bib | 10 ++++- rapport/main.tex | 87 +++++++++++++++++++++++++++----------- src/RsaCrt.cpp | 15 ++++--- src/RsaCrt.h | 3 ++ src/RsaCrtShamirsTrick.cpp | 30 ++++++------- src/RsaCrtShamirsTrick.h | 3 ++ src/Tests.cpp | 43 ++++++++++++------- 7 files changed, 127 insertions(+), 64 deletions(-) diff --git a/rapport/main.bib b/rapport/main.bib index 49b2ca5..ca29ad1 100644 --- a/rapport/main.bib +++ b/rapport/main.bib @@ -12,10 +12,16 @@ howpublished = "\url{http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6178001}" } +@misc {Lee-Choi-Koren-Dooho-improved-shamirs-crt-rsa, + author = "Lee, Seungkwang and Choi, Dooho and Choi, Yongjae", + title = "Improved Shamir's CRT-RSA Algorithm: A Revisit with the Modulus Chaining Method", + year = "2013", + howpublished = "\url{http://dx.doi.org/10.4218/etrij.14.0113.0317}" +} + @misc {wiki-rsa, author = "Wikipedia", title = "RSA (cryptosystem) --- {W}ikipedia{,} The Free Encyclopedia", year = "2014", howpublished = "\url{http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29}" - } - \ No newline at end of file + } \ No newline at end of file diff --git a/rapport/main.tex b/rapport/main.tex index f02d7b6..ef230e3 100644 --- a/rapport/main.tex +++ b/rapport/main.tex @@ -28,6 +28,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -35,14 +36,14 @@ \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 l'environnement de développement \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 \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). +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 : @@ -66,19 +67,19 @@ qbs run release -- time-measures \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 : 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} ?} +\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. +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}{-4pt} +{\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 * q \\ - \varphi(n) &= (p - 1) * (q - 1) \\ + 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) \\ @@ -88,7 +89,7 @@ Les valeurs de $p$, $q$, $d_p$, $d_q$ et $q_{inv}$ sont mémorisées en tant que La signature $sig$ du message $m$ peut être ensuite calculée comme suit. -{\setlength{\abovedisplayskip}{-4pt} +{\setlength{\abovedisplayskip}{0pt} \begin{flalign*} s_p &= m^{d_p} ~(mod ~p) &\\ s_q &= m^{d_q} ~(mod ~q) \\ @@ -101,24 +102,26 @@ La signature $sig$ du message $m$ peut être ensuite calculée comme suit. \subsection{Fonctionnement} -D'après le document \cite{Boneh-DeMillo-Lipton-attack} : +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}{-4pt} +{\setlength{\abovedisplayskip}{0pt} \begin{flalign*} - q &= gcd(m - sign'^e, n) & + q &= gcd(m - sig'^e, n) & \end{flalign*} Où : \begin{itemize} - \item $m$ : le message signé avec $sign'$ - \item $sign'$ : la signature calculée avec un $p$ altéré. + \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}{-4pt} +{\setlength{\abovedisplayskip}{0pt} \begin{flalign*} p &= n / q & \end{flalign*} @@ -127,7 +130,7 @@ 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 \cite{Barenghi-Breveglieri-Koren-Naccache-fault-injection} : +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 ; @@ -138,23 +141,23 @@ Voici une liste de techniques issues du document \cite{Barenghi-Breveglieri-Kore \item Exposition à une lumière intense. \end{itemize} -Il faut aussi ajouté qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies. +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$ s'il l'on possède une signature valide mais pas le message original : +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}{-4pt} +{\setlength{\abovedisplayskip}{0pt} \begin{flalign*} - q &= gcd(sign - sign'^e, n) & + q &= gcd(sig - sig'^e, n) & \end{flalign*} Où : \begin{itemize} - \item $sign$ : la signature correctement calculée. - \item $sign'$ : la signature calculée avec un $p$ altéré. + \item $sig$ : la signature correctement calculée. + \item $sig'$ : la signature calculée avec un $p$ altéré. \end{itemize} @@ -169,21 +172,57 @@ qbs run -- attack %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\section{Le \flqq truc \frqq de \emph{Shamir}} +\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} diff --git a/src/RsaCrt.cpp b/src/RsaCrt.cpp index 0a9273e..869fce5 100644 --- a/src/RsaCrt.cpp +++ b/src/RsaCrt.cpp @@ -34,22 +34,23 @@ pair RsaCrt::generateRSAKeys(uint exponent, uint k mpz_class RsaCrt::sign(const mpz_class& m, const KeyPriv& kPriv) { - mpz_class sp, sq; - - mpz_powm_sec(sp.get_mpz_t(), m.get_mpz_t(), kPriv.dp.get_mpz_t(), kPriv.p.get_mpz_t()); - mpz_powm_sec(sq.get_mpz_t(), m.get_mpz_t(), kPriv.dq.get_mpz_t(), kPriv.q.get_mpz_t()); - - return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q; + return sign(m, kPriv, false); } mpz_class RsaCrt::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv) +{ + return sign(m, kPriv, true); +} + +mpz_class RsaCrt::sign(const mpz_class& m, const KeyPriv& kPriv, bool withError) { mpz_class sp, sq; mpz_powm_sec(sp.get_mpz_t(), m.get_mpz_t(), kPriv.dp.get_mpz_t(), kPriv.p.get_mpz_t()); mpz_powm_sec(sq.get_mpz_t(), m.get_mpz_t(), kPriv.dq.get_mpz_t(), kPriv.q.get_mpz_t()); - mpz_combit(sp.get_mpz_t(), 42); // Flip the fourty second bit. + if (withError) + mpz_combit(sp.get_mpz_t(), 42); // Flip the fourty second bit. return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q; } diff --git a/src/RsaCrt.h b/src/RsaCrt.h index adf6c72..6e93e6b 100644 --- a/src/RsaCrt.h +++ b/src/RsaCrt.h @@ -35,6 +35,9 @@ public: * @param m the message to sign. No padding is used. */ static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv); + +private: + static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv, bool withError); }; #endif diff --git a/src/RsaCrtShamirsTrick.cpp b/src/RsaCrtShamirsTrick.cpp index 0e01e4b..dffb20f 100644 --- a/src/RsaCrtShamirsTrick.cpp +++ b/src/RsaCrtShamirsTrick.cpp @@ -30,6 +30,16 @@ pair RsaCrtShamirsTrick::generateRSAKe } mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv) +{ + return sign(m, kPriv, false); +} + +mpz_class RsaCrtShamirsTrick::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv) +{ + return sign(m, kPriv, true); +} + +mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv, bool withError) { const mpz_class r = Rand::randPrime(64); @@ -40,8 +50,11 @@ mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv) const mpz_class sqExponent = kPriv.d % ((kPriv.q - 1) * (r - 1)); // d mod phi(q * r). mpz_class spr, sqr; - mpz_powm(spr.get_mpz_t(), m.get_mpz_t(), spExponent.get_mpz_t(), pr.get_mpz_t()); - mpz_powm(sqr.get_mpz_t(), m.get_mpz_t(), sqExponent.get_mpz_t(), qr.get_mpz_t()); + mpz_powm(spr.get_mpz_t(), m.get_mpz_t(), spExponent.get_mpz_t(), pr.get_mpz_t()); // spr = m^exp mod p*r. + mpz_powm(sqr.get_mpz_t(), m.get_mpz_t(), sqExponent.get_mpz_t(), qr.get_mpz_t()); // sqr = m^exp mod q*r. + + if (withError) + mpz_combit(spr.get_mpz_t(), 42); // Flip the fourty second bit. if (spr % r != sqr % r) throw UnableToSignWithShamirsTrick(); @@ -51,16 +64,3 @@ mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv) return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q; } - -mpz_class RsaCrtShamirsTrick::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv) -{ - mpz_class sp, sq;/* - - mpz_powm_sec(sp.get_mpz_t(), m.get_mpz_t(), kPriv.dp.get_mpz_t(), kPriv.p.get_mpz_t()); - mpz_powm_sec(sq.get_mpz_t(), m.get_mpz_t(), kPriv.dq.get_mpz_t(), kPriv.q.get_mpz_t()); - - mpz_combit(sp.get_mpz_t(), 42); // Flip the fourty second bit. - - return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;*/ - return sp; -} diff --git a/src/RsaCrtShamirsTrick.h b/src/RsaCrtShamirsTrick.h index 07299e8..dbfa0e6 100644 --- a/src/RsaCrtShamirsTrick.h +++ b/src/RsaCrtShamirsTrick.h @@ -38,6 +38,9 @@ public: * @param m the message to sign. No padding is used. */ static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv); + +private: + static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv, bool withError); }; #endif diff --git a/src/Tests.cpp b/src/Tests.cpp index c9a2839..73ee552 100644 --- a/src/Tests.cpp +++ b/src/Tests.cpp @@ -18,27 +18,23 @@ Tests::Tests(uint keySizeBits, uint rsaPublicExponent) : void Tests::runTests() { - if (this->rsaStandard()) - cout << "RSA standard OK" << endl; - else - cout << "RSA standard failed!" << endl; + cout << "Tests::runTests() ..." << endl; - if (this->rsaCrt()) - cout << "RSA CRT OK" << endl; - else - cout << "RSA CRT failed!" << endl; + cout << "RSA standard: " << (this->rsaStandard() ? "OK" : "failed!") << endl; + cout << "RSA CRT: " << (this->rsaCrt() ? "OK" : "failed!") << endl; } void Tests::runTestsWithShamirsTrick() { - if (this->rsaCrtWithShamirsTrick()) - cout << "RSA CRT with shamir's trick OK" << endl; - else - cout << "RSA CRT with shamir's trick failed!" << endl; + cout << "Tests::runTestsWithShamirsTrick() ..." << endl; + + cout << "RSA CRT with Shamir's trick: " << (this->rsaCrtWithShamirsTrick() ? "OK" : "failed!") << endl; } void Tests::runTimeMeasures() { + cout << "Tests::runTimeMeasures() ..." << endl; + const int N = 1000; const int nbKeys = 20; // Number of different generated key. @@ -57,11 +53,13 @@ void Tests::runTimeMeasures() cout << N * nbKeys << " x RSA CRT: " << timeRsaCRT << " ms" << endl; cout << N * nbKeys << " x RSA CRT Shamir's trick: " << timeRsaCRTShamirsTrick << " ms" << endl; cout << "Speedup for CRT: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl; - cout << "Speedup for CRT with Shamir's trick: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl; + cout << "Speedup for CRT with Shamir's trick: " << (double(timeRsaStd) / double(timeRsaCRTShamirsTrick)) << endl; } void Tests::doAttack() { + cout << "Tests::doAttack() ..." << endl; + const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); const auto& kPub = keys.first; const auto& kPriv = keys.second; @@ -92,7 +90,7 @@ void Tests::doAttack() attackSuccessful = attackSuccessful && kPriv.p == p && kPriv.q == q; // With p and q we can recreate the original private key. } - // Try the attack with a correct signature. + // Try the attack with a correct signature (p and q shouldn't be found). { mpz_class correctSignaturePowerE; mpz_pow_ui(correctSignaturePowerE.get_mpz_t(), correctSignature.get_mpz_t(), RSA_PUBLIC_EXPONENT); @@ -116,9 +114,22 @@ void Tests::doAttack() void Tests::doAttackFixed() { - const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); - const auto& kPub = keys.first; + cout << "Tests::doAttackFixed() ..." << endl; + + const auto& keys = RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); const auto& kPriv = keys.second; + + mpz_class message = Rand::randSize(128); + + try + { + RsaCrtShamirsTrick::signWithFaultySp(message, kPriv); + cout << "Attack successful -> incorrect" << endl; + } + catch (const RsaCrtShamirsTrick::UnableToSignWithShamirsTrick& e) + { + cout << "Attack failed -> correct" << endl; + } } bool Tests::rsaStandard() -- 2.43.0