From 22aac262156e81085b22bdfcd0cc38950768be9b Mon Sep 17 00:00:00 2001 From: Ummon Date: Mon, 12 Jan 2015 01:11:36 +0100 Subject: [PATCH] Implementation of Shamir's trick (working in progress). --- rapport/main.tex | 37 ++++++++++++++----- src/RsaCrt.cpp | 2 -- src/RsaCrt.h | 6 ++++ src/RsaCrtShamirsTrick.cpp | 66 ++++++++++++++++++++++++++++++++++ src/RsaCrtShamirsTrick.h | 43 ++++++++++++++++++++++ src/Tests.cpp | 73 +++++++++++++++++++++++++++++++++++--- src/Tests.h | 17 ++++++++- src/lab3.qbs | 2 +- src/main.cpp | 7 +++- 9 files changed, 235 insertions(+), 18 deletions(-) create mode 100644 src/RsaCrtShamirsTrick.cpp create mode 100644 src/RsaCrtShamirsTrick.h diff --git a/rapport/main.tex b/rapport/main.tex index f8ebe68..f02d7b6 100644 --- a/rapport/main.tex +++ b/rapport/main.tex @@ -73,6 +73,7 @@ La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus r 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} \begin{flalign*} e &= 65537 \\ \mathbf{p, q} &&\text{deux nombres premiers de 512 bits choisis de manière aléatoire} \\ @@ -81,12 +82,13 @@ Les valeurs de $p$, $q$, $d_p$, $d_q$ et $q_{inv}$ sont mémorisées en tant que 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) + \mathbf{q_{inv}} &= q^{-1} ~(mod ~p) \end{flalign*} La signature $sig$ du message $m$ peut être ensuite calculée comme suit. +{\setlength{\abovedisplayskip}{-4pt} \begin{flalign*} s_p &= m^{d_p} ~(mod ~p) &\\ s_q &= m^{d_q} ~(mod ~q) \\ @@ -101,6 +103,7 @@ La signature $sig$ du message $m$ peut être ensuite calculée comme suit. D'après le document \cite{Boneh-DeMillo-Lipton-attack} : +{\setlength{\abovedisplayskip}{-4pt} \begin{flalign*} q &= gcd(m - sign'^e, n) & \end{flalign*} @@ -109,12 +112,13 @@ Où : \begin{itemize} \item $m$ : le message signé avec $sign'$ - \item $sign'$ : la signature calculé avec un $p$ altéré. + \item $sign'$ : la signature calculée avec un $p$ altéré. \end{itemize} Nous pouvons alors facilement retrouver $p$: +{\setlength{\abovedisplayskip}{-4pt} \begin{flalign*} p &= n / q & \end{flalign*} @@ -134,9 +138,24 @@ 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. -\subsubsection*{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?} +\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 : + +{\setlength{\abovedisplayskip}{-4pt} +\begin{flalign*} + q &= gcd(sign - sign'^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é. +\end{itemize} @@ -154,14 +173,16 @@ qbs run -- attack \subsection{Fonctionnement} -(maths) -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\section{Conclusion} -% -% Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\section{Conclusion} \bibliographystyle{plain} diff --git a/src/RsaCrt.cpp b/src/RsaCrt.cpp index b078013..0a9273e 100644 --- a/src/RsaCrt.cpp +++ b/src/RsaCrt.cpp @@ -53,5 +53,3 @@ mpz_class RsaCrt::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv) return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q; } - - diff --git a/src/RsaCrt.h b/src/RsaCrt.h index b680e31..adf6c72 100644 --- a/src/RsaCrt.h +++ b/src/RsaCrt.h @@ -2,6 +2,7 @@ #define RSACRT_H #include +#include #include @@ -25,9 +26,14 @@ public: /** * m must not be greater or equal than kPriv.n. + * @param m the message to sign. No padding is used. */ static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv); + /** + * Sp is altered by flipping its 42nd bit. + * @param m the message to sign. No padding is used. + */ static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv); }; diff --git a/src/RsaCrtShamirsTrick.cpp b/src/RsaCrtShamirsTrick.cpp new file mode 100644 index 0000000..0e01e4b --- /dev/null +++ b/src/RsaCrtShamirsTrick.cpp @@ -0,0 +1,66 @@ +#include "RsaCrtShamirsTrick.h" + +using namespace std; + +#include "Rand.h" +#include "Utils.h" + +pair RsaCrtShamirsTrick::generateRSAKeys(uint exponent, uint keySizeBits) +{ + mpz_class phi; + Rsa::KeyPub kPub; + KeyPriv kPriv; + + do + { + kPub.e = exponent; + kPriv.p = Rand::randPrime(keySizeBits / 2); + kPriv.q = Rand::randPrime(keySizeBits / 2); + + kPub.n = kPriv.p * kPriv.q; + phi = (kPriv.p - 1) * (kPriv.q - 1); + + // d = e^-1 (mode phi). + } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0); + + // qInv = q^-1 (mod p) + mpz_invert(kPriv.qInv.get_mpz_t(), kPriv.q.get_mpz_t(), kPriv.p.get_mpz_t()); + + return make_pair(kPub, kPriv); +} + +mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv) +{ + const mpz_class r = Rand::randPrime(64); + + const mpz_class pr = kPriv.p * r; + const mpz_class qr = kPriv.q * r; + + const mpz_class spExponent = kPriv.d % ((kPriv.p - 1) * (r - 1)); // d mod phi(p * r). + 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()); + + if (spr % r != sqr % r) + throw UnableToSignWithShamirsTrick(); + + mpz_class sp = spr % kPriv.p; + mpz_class sq = sqr % kPriv.q; + + 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 new file mode 100644 index 0000000..07299e8 --- /dev/null +++ b/src/RsaCrtShamirsTrick.h @@ -0,0 +1,43 @@ +#ifndef RSACRT_SHAMIRS_TRICK_H +#define RSACRT_SHAMIRS_TRICK_H + +#include +#include + +#include + +#include "Rsa.h" + +class RsaCrtShamirsTrick +{ +public: + class UnableToSignWithShamirsTrick : public std::exception {}; + + struct KeyPriv { + mpz_class p; + mpz_class q; + mpz_class d; + 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. + * Use the Shamir's trick to test if a fault has been created during the computation of Sp and Sq. + * If so it throws 'UnableToSignWithShamirsTrick'. + * @param m the message to sign. No padding is used. + */ + static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv); + + /** + * Sp is altered by flipping its 42nd bit. + * @param m the message to sign. No padding is used. + */ + static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv); +}; + +#endif diff --git a/src/Tests.cpp b/src/Tests.cpp index 2adcd32..c9a2839 100644 --- a/src/Tests.cpp +++ b/src/Tests.cpp @@ -8,6 +8,7 @@ using namespace std; #include "Rand.h" #include "RsaStd.h" #include "RsaCrt.h" +#include "RsaCrtShamirsTrick.h" Tests::Tests(uint keySizeBits, uint rsaPublicExponent) : KEY_SIZE_BITS(keySizeBits), @@ -28,6 +29,14 @@ void Tests::runTests() cout << "RSA CRT 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; +} + void Tests::runTimeMeasures() { const int N = 1000; @@ -35,16 +44,20 @@ void Tests::runTimeMeasures() int timeRsaStd = 0; int timeRsaCRT = 0; + int timeRsaCRTShamirsTrick = 0; for (int k = 0; k < nbKeys; ++k) { timeRsaStd += timeSignRsaStd(N); timeRsaCRT += timeSignRsaCRT(N); + timeRsaCRTShamirsTrick += timeSignRsaCRTShamirsTrick(N); } cout << N * nbKeys << " x RSA standard: " << timeRsaStd << " ms" << endl; cout << N * nbKeys << " x RSA CRT: " << timeRsaCRT << " ms" << endl; - cout << "Speedup: " << (double(timeRsaStd) / double(timeRsaCRT)) << 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; } void Tests::doAttack() @@ -52,11 +65,12 @@ 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; + bool attackSuccessful = true; cout << "Original:" << endl; cout << " p = " << kPriv.p << endl; @@ -75,7 +89,7 @@ void Tests::doAttack() 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. + 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. @@ -91,15 +105,22 @@ void Tests::doAttack() cout << " p = " << p << endl; // Equal to 1. cout << " q = " << q << endl; // Equal to n. - attackOK = attackOK && kPriv.p != p && kPriv.q != q; + attackSuccessful = attackSuccessful && kPriv.p != p && kPriv.q != q; } - if (attackOK) + if (attackSuccessful) cout << "Attack successful" << endl; else cout << "Attack failed" << endl; } +void Tests::doAttackFixed() +{ + const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); + const auto& kPub = keys.first; + const auto& kPriv = keys.second; +} + bool Tests::rsaStandard() { const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); @@ -160,6 +181,36 @@ bool Tests::rsaCrt() return true; } +bool Tests::rsaCrtWithShamirsTrick() +{ + const auto& keys = RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); + const auto& kPub = keys.first; + const auto& kPriv = keys.second; + + { + mpz_class message = kPub.n; + mpz_class signature = RsaCrtShamirsTrick::sign(message, kPriv); + if (Rsa::verifySignature(message, signature, kPub)) // Must not be able to signe message greater than kPub.n. + return false; + } + + { + mpz_class message = kPub.n - 1; + mpz_class signature = RsaCrtShamirsTrick::sign(message, kPriv); + if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub)) + return false; + } + + { + mpz_class message = kPub.n / 2; + mpz_class signature = RsaCrtShamirsTrick::sign(message, kPriv); + if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub)) + return false; + } + + return true; +} + int Tests::timeSignRsaStd(int N) { Timer timer; @@ -183,3 +234,15 @@ int Tests::timeSignRsaCRT(int N) return timer.ms(); } + +int Tests::timeSignRsaCRTShamirsTrick(int N) +{ + Timer timer; + const auto& keys = RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); + + mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2); + for (int i = 0; i < N; i++) + RsaCrtShamirsTrick::sign(message, keys.second); + + return timer.ms(); +} diff --git a/src/Tests.h b/src/Tests.h index fe75c6d..75f0bdb 100644 --- a/src/Tests.h +++ b/src/Tests.h @@ -8,17 +8,32 @@ class Tests public: Tests(uint keySizeBits, uint rsaPublicExponent); - void runTests(); + void runTests(); + void runTestsWithShamirsTrick(); void runTimeMeasures(); + void doAttack(); + void doAttackFixed(); private: bool rsaStandard(); bool rsaCrt(); + bool rsaCrtWithShamirsTrick(); + /** + * Return the time in [ms] required to sign N times with RSA standard. + * One key pair and a message is generated. + */ int timeSignRsaStd(int N); + + /** + * Return the time in [ms] required to sign N times with RSA CRT. + * One key pair and a message is generated. + */ int timeSignRsaCRT(int N); + int timeSignRsaCRTShamirsTrick(int N); + const uint KEY_SIZE_BITS; const uint RSA_PUBLIC_EXPONENT; }; diff --git a/src/lab3.qbs b/src/lab3.qbs index 148f7b4..cbe3dcd 100644 --- a/src/lab3.qbs +++ b/src/lab3.qbs @@ -4,7 +4,7 @@ Product { name: "lab3" type: "application" - files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaStd.h", "RsaStd.cpp", "RsaCrt.h", "RsaCrt.cpp", "Utils.h", "Utils.cpp", "Tests.h", "Tests.cpp"] + files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaStd.h", "RsaStd.cpp", "RsaCrt.h", "RsaCrt.cpp", "RsaCrtShamirsTrick.h", "RsaCrtShamirsTrick.cpp", "Utils.h", "Utils.cpp", "Tests.h", "Tests.cpp"] cpp.commonCompilerFlags: ["-std=c++11"] cpp.staticLibraries: ["gmp", "gmpxx"] diff --git a/src/main.cpp b/src/main.cpp index 3dcf71e..8c4ec7e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -22,9 +22,10 @@ void printUsage(const string& progName) cout << "Usage: " << progName << " " << endl; cout << " can be one of the following:" << endl; cout << " * tests: Do some tests for RSA and RSA-CRT" << endl; + cout << " * tests-with-shamirs-trick: Do some tests for RSA-CRT with Shamir's trick" << 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; + cout << " * attack-fixed: Try the attack with the Shamir's trick version" << endl; } int main(int argc, char** argv) @@ -35,10 +36,14 @@ int main(int argc, char** argv) if (args.size() >= 2 && args[1] == "tests") Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTests(); + else if (args.size() >= 2 && args[1] == "tests-with-shamirs-trick") + Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTestsWithShamirsTrick(); 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 if (args.size() >= 2 && args[1] == "attack-fixed") + Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).doAttackFixed(); else printUsage(args[0]); -- 2.45.2