Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Journal of Cryptographic Engineering
Erschienen 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

verfasst von: Pablo Rauzy, Sylvain Guilley

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 3/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Towards fresh re-keying with leakage-resilient PRFs: cipher design principles and analysis
Nächster Artikel Understanding the limitations and improving the relevance of SPICE simulations in side-channel security evaluations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
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.
 
Literatur
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)
Metadaten
Titel
A formal proof of countermeasures against fault injection attacks on CRT-RSA
verfasst von
Pablo Rauzy
Sylvain Guilley
Publikationsdatum
01.09.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
Journal of Cryptographic Engineering / Ausgabe 3/2014
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-013-0065-3

Weitere Artikel der Ausgabe 3/2014

Journal of Cryptographic Engineering 3/2014 Zur Ausgabe

Special Section on Proofs 2013

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

Special Section on Proofs 2013

Formal verification of a software countermeasure against instruction skip attacks

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

Premium Partner

    Bildnachweise