Attack implementation.

diff --git a/rapport/main.bib b/rapport/main.bib
new file mode 100644 (file)
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 (file)
--- a/rapport/main.tex
+++ b/rapport/main.tex
@@ -5,6 +5,8 @@
 \usepackage[T1]{fontenc}
 \usepackage{lmodern}
 
 \usepackage[T1]{fontenc}
 \usepackage{lmodern}
 

+\usepackage{amssymb,amsmath,amsthm}
+

 \usepackage{graphicx}
 \usepackage{listings}
 \usepackage{url}
 \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} ?}
 
 
 \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}
 
 
 \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 ?}
 
 
 \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}
 
 
 \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}
 
 \end{document}

diff --git a/src/RsaCrt.cpp b/src/RsaCrt.cpp
index ff3f21e..b078013 100644 (file)
--- 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;
 }
 
    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 (file)
--- a/src/RsaCrt.h
+++ b/src/RsaCrt.h
@@ -18,12 +18,17 @@ public:
       mpz_class qInv;
    };
 
       mpz_class qInv;
    };
 

+   /**
+    * Generate a pair of keys (public, private).
+    */

    static std::pair<Rsa::KeyPub, KeyPriv> 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 std::pair<Rsa::KeyPub, KeyPriv> 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
 };
 
 #endif

diff --git a/src/Tests.cpp b/src/Tests.cpp
index 92bccd0..2adcd32 100644 (file)
--- a/src/Tests.cpp
+++ b/src/Tests.cpp
@@ -47,6 +47,59 @@ void Tests::runTimeMeasures()
    cout << "Speedup: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl;
 }
 
    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);
 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 (file)
--- a/src/Tests.h
+++ b/src/Tests.h
@@ -10,6 +10,7 @@ public:
 
    void runTests();
    void runTimeMeasures();
 
    void runTests();
    void runTimeMeasures();

+   void doAttack();

 
 private:
    bool rsaStandard();
 
 private:
    bool rsaStandard();

diff --git a/src/main.cpp b/src/main.cpp
index 4cfdb9c..3dcf71e 100644 (file)
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -19,15 +19,12 @@ const uint RSA_PUBLIC_EXPONENT = 65537;
 
 void printUsage(const string& progName)
 {
 
 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 << " <command>" << endl;
+   cout << " <command> 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)
 }
 
 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();
       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]);
 
    else
       printUsage(args[0]);