From 2745bc6570ac32789650336b8c84a52d1883c62a Mon Sep 17 00:00:00 2001 From: Ummon Date: Fri, 26 Dec 2014 13:39:31 +0100 Subject: [PATCH] Attack implementation. --- rapport/main.bib | 21 +++++++++++++ rapport/main.tex | 77 +++++++++++++++++++++++++++++++++++++++++++----- src/RsaCrt.cpp | 14 +++++++++ src/RsaCrt.h | 5 ++++ src/Tests.cpp | 53 +++++++++++++++++++++++++++++++++ src/Tests.h | 1 + src/main.cpp | 17 +++++------ 7 files changed, 172 insertions(+), 16 deletions(-) create mode 100644 rapport/main.bib diff --git a/rapport/main.bib b/rapport/main.bib new file mode 100644 index 0000000..49b2ca5 --- /dev/null +++ b/rapport/main.bib @@ -0,0 +1,21 @@ +@misc {Boneh-DeMillo-Lipton-attack, + author = "Boneh, Dan and DeMillo, Richard A. and Lipton, Richard J.", + title = "On the Importance of Eliminating Errors in Cryptographic Computations", + year = "1999", + howpublished = "\url{http://crypto.stanford.edu/~dabo/abstracts/faults.html}" +} + +@misc {Barenghi-Breveglieri-Koren-Naccache-fault-injection, + author = "Barenghi, Alessandro and Breveglieri, Luca and Koren, Israel and Naccache, David", + title = "Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures", + year = "2012", + howpublished = "\url{http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6178001}" +} + +@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 diff --git a/rapport/main.tex b/rapport/main.tex index f2e5ba5..f8ebe68 100644 --- a/rapport/main.tex +++ b/rapport/main.tex @@ -5,6 +5,8 @@ \usepackage[T1]{fontenc} \usepackage{lmodern} +\usepackage{amssymb,amsmath,amsthm} + \usepackage{graphicx} \usepackage{listings} \usepackage{url} @@ -69,7 +71,27 @@ La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus r \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} ?} -[TODO] +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. + +\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) \\ + 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*} + + +La signature $sig$ du message $m$ peut être ensuite calculée comme suit. + +\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*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -77,15 +99,54 @@ La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus r \subsection{Fonctionnement} -http://crypto.stanford.edu/~dabo/abstracts/faults.html +D'après le document \cite{Boneh-DeMillo-Lipton-attack} : -(maths) +\begin{flalign*} + q &= gcd(m - sign'^e, n) & +\end{flalign*} + +Où : + +\begin{itemize} + \item $m$ : le message signé avec $sign'$ + \item $sign'$ : la signature calculé avec un $p$ altéré. +\end{itemize} + + +Nous pouvons alors facilement retrouver $p$: + +\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 ?} +Voici une liste de techniques issues du document \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} + + +\subsubsection*{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?} -\subsubsection*{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non détérministe ?} + + + +\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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -99,9 +160,11 @@ http://crypto.stanford.edu/~dabo/abstracts/faults.html \section{Conclusion} -% http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29 +% +% Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures + -%\bibliographystyle{plain} -%\bibliography{main} +\bibliographystyle{plain} +\bibliography{main} \end{document} diff --git a/src/RsaCrt.cpp b/src/RsaCrt.cpp index ff3f21e..b078013 100644 --- a/src/RsaCrt.cpp +++ b/src/RsaCrt.cpp @@ -41,3 +41,17 @@ mpz_class RsaCrt::sign(const mpz_class& m, const KeyPriv& kPriv) return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q; } + +mpz_class RsaCrt::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; +} + + diff --git a/src/RsaCrt.h b/src/RsaCrt.h index 373d583..b680e31 100644 --- a/src/RsaCrt.h +++ b/src/RsaCrt.h @@ -18,12 +18,17 @@ public: mpz_class qInv; }; + /** + * Generate a pair of keys (public, private). + */ static std::pair generateRSAKeys(uint exponent, uint keySizeBits); /** * m must not be greater or equal than kPriv.n. */ static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv); + + static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv); }; #endif diff --git a/src/Tests.cpp b/src/Tests.cpp index 92bccd0..2adcd32 100644 --- a/src/Tests.cpp +++ b/src/Tests.cpp @@ -47,6 +47,59 @@ void Tests::runTimeMeasures() cout << "Speedup: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl; } +void Tests::doAttack() +{ + const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); + const auto& kPub = keys.first; + const auto& kPriv = keys.second; + mpz_class message = Rand::randSize(128); + mpz_class faultySignature = RsaCrt::signWithFaultySp(message, kPriv); + mpz_class correctSignature = RsaCrt::sign(message, kPriv); + + bool attackOK = true; + + cout << "Original:" << endl; + cout << " p = " << kPriv.p << endl; + cout << " q = " << kPriv.q << endl; + + // At this point the attacker doesn't know the private key but he has intercepted the message and the faulty signature. + { + mpz_class faultySignaturePowerE; + mpz_pow_ui(faultySignaturePowerE.get_mpz_t(), faultySignature.get_mpz_t(), RSA_PUBLIC_EXPONENT); + mpz_class messageMinuxFaultySignaturePowerE = message - faultySignaturePowerE; + mpz_class q; + mpz_gcd(q.get_mpz_t(), messageMinuxFaultySignaturePowerE.get_mpz_t(), kPub.n.get_mpz_t()); + mpz_class p = kPub.n / q; + + cout << "Found with a faulty signature:" << endl; + cout << " p = " << p << endl; + cout << " q = " << q << endl; + + attackOK = attackOK && kPriv.p == p && kPriv.q == q; // With p and q we can recreate the original private key. + } + + // Try the attack with a correct signature. + { + mpz_class correctSignaturePowerE; + mpz_pow_ui(correctSignaturePowerE.get_mpz_t(), correctSignature.get_mpz_t(), RSA_PUBLIC_EXPONENT); + mpz_class messageMinuxCorrectSignaturePowerE = message - correctSignaturePowerE; + mpz_class q; + mpz_gcd(q.get_mpz_t(), messageMinuxCorrectSignaturePowerE.get_mpz_t(), kPub.n.get_mpz_t()); + mpz_class p = kPub.n / q; + + cout << "Found with a correct signature:" << endl; + cout << " p = " << p << endl; // Equal to 1. + cout << " q = " << q << endl; // Equal to n. + + attackOK = attackOK && kPriv.p != p && kPriv.q != q; + } + + if (attackOK) + cout << "Attack successful" << endl; + else + cout << "Attack failed" << endl; +} + bool Tests::rsaStandard() { const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); diff --git a/src/Tests.h b/src/Tests.h index 4f01ac0..fe75c6d 100644 --- a/src/Tests.h +++ b/src/Tests.h @@ -10,6 +10,7 @@ public: void runTests(); void runTimeMeasures(); + void doAttack(); private: bool rsaStandard(); diff --git a/src/main.cpp b/src/main.cpp index 4cfdb9c..3dcf71e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -19,15 +19,12 @@ const uint RSA_PUBLIC_EXPONENT = 65537; void printUsage(const string& progName) { - cout << "Usage: " << progName << " [tests|time-measures]" << endl; - -// mpz_class n = 10; -// mpz_class d = 3; -// mpz_class q; -// mpz_fdiv_q(q.get_mpz_t(), n.get_mpz_t(), d.get_mpz_t()); - -// cout << "q: " << q << endl; -// cout << "q: " << (n / d) << endl; + cout << "Usage: " << progName << " " << endl; + cout << " can be one of the following:" << endl; + cout << " * tests: Do some tests for RSA and RSA-CRT" << endl; + cout << " * time-measures: Compute the ratio between RSA and RSA-CRT" << endl; + cout << " * attack: Simulate the Boneh-DeMillo-Lipton attack against RSA-CRT" << endl; + cout << " * attack-fixed: [TODO]" << endl; } int main(int argc, char** argv) @@ -40,6 +37,8 @@ int main(int argc, char** argv) Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTests(); else if (args.size() >= 2 && args[1] == "time-measures") Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTimeMeasures(); + else if (args.size() >= 2 && args[1] == "attack") + Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).doAttack(); else printUsage(args[0]); -- 2.45.2