Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptographic Engineering
Published in: Journal of Cryptographic Engineering 3/2014

01-09-2014 | Special Section on Proofs 2013

A formal proof of countermeasures against fault injection attacks on CRT-RSA

Authors: Pablo Rauzy, Sylvain Guilley

Published in: Journal of Cryptographic Engineering | Issue 3/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this article, we describe a methodology that aims at either breaking or proving the security of CRT-RSA implementations against fault injection attacks. In the specific case-study of the BellCoRe attack, our work bridges a gap between formal proofs and implementation-level attacks. We apply our results to three implementations of CRT-RSA, namely the unprotected one, that of Shamir, and that of Aumüller et al. Our findings are that many attacks are possible on both the unprotected and the Shamir implementations, while the implementation of Aumüller et al.  is resistant to all single-fault attacks. It is also resistant to double-fault attacks if we consider the less powerful threat model of its authors.
previous article Towards fresh re-keying with leakage-resilient PRFs: cipher design principles and analysis
next article Understanding the limitations and improving the relevance of SPICE simulations in side-channel security evaluations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
2
In other papers related to faults, the faulted variables (such as \(X\)) are noted either with a star (\(X^*\)) or a tilde (\(\tilde{X}\)); in this paper, we use a hat, as it can stretch, hence cover the adequate portion of the variable. For instance, it allows to make an unambiguous difference between a faulted data raised at some power and a fault on a data raised at a given power (contrast \(\widehat{X}^e\) with \(\widehat{X^e}\)).
 
3
If it nonetheless happens that \(\gcd (N, S-\widehat{S})=N\), then the attacker can simply retry another fault injection, for which the probability that \(\gcd (N, S-\widehat{S}) \in \{p,q\}\) increases.
 
4
The authors notice that in Shamir’s countermeasure, \(r\) is a priori not a secret, hence can be static and safely divulged.
 
5
For example, a fault in the implementation of the multiplication is either inoffensive, and we do not need to care about it, or it affects the result of the multiplication, and our model take it into account without going into the details of how the multiplication’s is computed.
 
6
This result is worthwhile some emphasis: the genuine algorithm of Aumüller is thus proved resistant against single-fault attacks. At the opposite, the CRT-RSA algorithm of Vigilant is not immune to single-fault attacks (refer to [9]), and the corrections suggested in the same paper by Coron et al.  have not been proved yet.
 
7
Some results will appear in the proceedings of the 3rd ACM SIGPLAN Program Protection and Reverse Engineering Workshop (PPREW 2014) [20], collocated with POPL 2014.
 
Literature
1.
Aumüller, C., Bier, P., Fischer, W., Hofreiter, P., Seifert, J.-P.: Fault attacks on RSA with CRT: concrete results and practical countermeasures. In: Kaliski, B.S., Jr., Koç, C.K., Paar, C. (eds.) CHES. Lecture Notes in Computer Science, vol. 2523, pp. 260–275. Springer, Berlin (2002)
2.
Berzati, A., Canovas-Dumas, C., Goubin, L.: A survey of differential fault analysis against classical RSA implementations. In: Joye, M., Tunstall, M. (eds.) Fault Analysis in Cryptography, Information Security and Cryptography, pp. 111–124. Springer, Berlin (2012)
3.
Biham, E., Carmeli, Y., Shamir, A.: Bug attacks. In: CRYPTO. LNCS, vol. 5157, pp. 221–240. Springer, Santa Barbara (2008)
4.
Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Proceedings of Eurocrypt’97. LNCS, vol. 1233, pp. 37–51. Springer, Konstanz (1997). doi:10.​1007/​3-540-69053-0_​4
5.
6.
Blömer, J., Otto, M., Seifert, J.P.: A new CRT-RSA algorithm secure against Bellcore attacks. In: Jajodia, S., Atluri, V., Jaeger, T. (eds.) ACM Conference on Computer and Communications Security, pp. 311–320. ACM (2003)
7.
Biham, E., Shamir, A.: Analysis, differential fault, of secret key cryptosystems. In: CRYPTO. LNCS, vol. 1294, pp. 513–525. Springer, Santa Barbara (1997). doi:10.​1007/​BFb0052259
8.
Christofi, M., Chetali, B., Goubin, L., Vigilant, D.: Formal verification of an implementation of CRT-RSA Vigilant’s algorithm. J. Cryptogr. Eng. 3(3), (2013). doi:10.​1007/​s13389-013-0049-3
9.
Coron, J.-S., Giraud, C., Morin, N., Piret, G., Vigilant, D.: Fault attacks and countermeasures on vigilant’s RSA-CRT Algorithm. In: Breveglieri, L., Joye, M., Koren, I., Naccache, D., Verbauwhede, I. (eds.) FDTC, pp. 89–96. IEEE Computer Society (2010)
10.
Debande, N., Souissi, Y., Elaabid, M.A., Guilley, S., Danger, J.-L.: Wavelet transform based pre-processing for side channel analysis. In: HASP, pp. 32–38. IEEE, Vancouver (2012). doi:10.​1109/​MICROW.​2012.​15
11.
12.
13.
14.
Joye, M., Lenstra, A.K., Quisquater, J.-J.: Chinese remaindering based cryptosystems in the presence of faults. J. Cryptol. 12(4), 241–245 (1999)
15.
Joye, M.: Protecting RSA against fault attacks: the embedding method. In: Breveglieri, L., Koren, I., Naccache, D., Oswald, E., Seifert, J.-P. (eds.) FDTC, pp. 41–45. IEEE Computer Society (2009)
16.
Joye, M., Paillier, P.: GCD-free algorithms for computing modular inverses. In: Walter, C.D., Koç, C.K., Paar, C. (eds.) CHES. Lecture Notes in Computer Science, vol. 2779, pp. 243–253. Springer, Berlin (2003)
17.
Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Proceedings of CRYPTO’99. LNCS, vol. 1666, pp. 388–397. Springer, Berlin (1999)
18.
Kim, S.-K., Kim, T.H., Han, D.-G., Hong, S.: An efficient CRT-RSA algorithm secure against power and fault attacks. J. Syst. Softw. 84, 1660–1669 (October 2011)
19.
20.
Rauzy, P., Guilley, S.: Formal analysis of CRT-RSA vigilant’s countermeasure against the BellCoRe attack—a pledge for formal methods in the field of implementation security. In: 3rd ACM SIGPLAN Program Protection and Reverse Engineering Workshop (PPREW 2014) (2014). ISBN: 978-1-4503-2649-0
21.
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)CrossRefMATHMathSciNet
22.
23.
Shamir, A.: Method and apparatus for protecting public key schemes from timing and fault attacks, November 1999. Patent Number 5,991,415; also presented at the rump session of EUROCRYPT ’97.
24.
Tehranipoor, M., Wang, C. (eds.) Introduction to Hardware Security and Trust. Springer, Berlin (2012). ISBN: 978-1-4419-8079-3
25.
Vigilant, D.: RSA with CRT: a new cost-effective solution to thwart fault attacks. In Oswald, E., Rohatgi, P. (eds.) CHES. Lecture Notes in Computer Science, vol. 5154, pp. 130–145. Springer, Berlin (2008)
Metadata
Title
A formal proof of countermeasures against fault injection attacks on CRT-RSA
Authors
Pablo Rauzy
Sylvain Guilley
Publication date
01-09-2014
Publisher
Springer Berlin Heidelberg
Published in
Journal of Cryptographic Engineering / Issue 3/2014
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-013-0065-3

Other articles of this Issue 3/2014

Journal of Cryptographic Engineering 3/2014 Go to the issue

Regular Paper

A model of the leakage in the frequency domain and its application to CPA and DPA

Special Section on Proofs 2013

Towards fresh re-keying with leakage-resilient PRFs: cipher design principles and analysis

Special Section on Proofs 2013

Formal verification of a software countermeasure against instruction skip attacks

Special Section on Proofs 2013

Understanding the limitations and improving the relevance of SPICE simulations in side-channel security evaluations

Premium Partner

    Image Credits