User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

On second-order fault analysis resistance for CRT-RSA implementations

Primary tabs

Dottax, E. Giraud, C. Rivain, M. Sierra, Y.

Since their publication in 1996, fault attacks have been widely studied from both theoretical and practical points of view and most of cryptographic systems have been shown vulnerable to this kind of attacks. Until recently, most of the theoretical fault attacks and countermeasures used a fault model which assumes that the attacker is able to disturb the execution of a cryptographic algorithm only once. However, this approach seems too restrictive since the publication in 2007 of the successful experiment of an attack based on the injection of two faults, namely a second-order fault attack. Amongst the few papers dealing with second-order fault analysis, three countermeasures were published at WISTP'07 and FDTC'07 to protect the RSA cryptosystem using the CRT mode. In this paper, we analyse the security of these countermeasures with respect to the second-order fault model considered by their authors. We show that these countermeasures are not intrinsically resistant and we propose a new method allowing us to implement a CRT-RSA that resists to this kind of second-order fault attack.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès restreint
Publication date 2009
Conference "Information Security Theory and Practice. Smart Devices, Pervasive Systems, and Ubiquitous Networks. Third IFIP WG11.2 International Workshop, WISTP 2009", Brussels, Belgium (1-4 September 2009)
Peer reviewed yes
Host document Markowitch, O.; Bilas, A.; Hoepman, J.-H.; Mitchell, C.J.; Quisquater, J.-J.; ; "Information Security Theory and Practice. Smart Devices, Pervasive Systems, and Ubiquitous Networks. Third IFIP WG11.2 International Workshop, WISTP 2009"- p. 68-83 (ISBN : 978-3-642-03943-0)
Publisher Springer verlag
Affiliation UCL
Links
  1. Aumüller C., Bier P., Fischer W., Hofreiter P., Seifert J.-P., Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures, Cryptographic Hardware and Embedded Systems - CHES 2002 (2003) ISBN:9783540004097 p.260-275, 10.1007/3-540-36400-5_20
  2. Bar-El H., Choukri H., Naccache D., Tunstall M., Whelan C., The Sorcerer's Apprentice Guide to Fault Attacks, 10.1109/jproc.2005.862424
  3. Biham Eli, Shamir Adi, Differential fault analysis of secret key cryptosystems, Advances in Cryptology — CRYPTO '97 (1997) ISBN:9783540633846 p.513-525, 10.1007/bfb0052259
  4. Blömer, J., Otto, M., Seifert, J.-P.: A New RSA-CRT Algorithm Secure against Bellcore Attacks. In: Jajodia, S., Atluri, V., Jaeger, T. (eds.) ACM Conference on Computer and Communications Security – CCS 2003, pp. 311–320. ACM Press, New York (2003)
  5. Boneh Dan, DeMillo Richard A., Lipton Richard J., On the Importance of Checking Cryptographic Protocols for Faults, Advances in Cryptology — EUROCRYPT ’97 (1997) ISBN:9783540629757 p.37-51, 10.1007/3-540-69053-0_4
  6. Boscher Arnaud, Naciri Robert, Prouff Emmanuel, CRT RSA Algorithm Protected Against Fault Attacks, Information Security Theory and Practices. Smart Cards, Mobile and Ubiquitous Computing Systems (2007) ISBN:9783540723530 p.229-243, 10.1007/978-3-540-72354-7_19
  7. Ciet Mathieu, Joye Marc, Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Faults, 10.1007/s10623-003-1160-8
  8. Ciet, M., Joye, M.: Practical Fault Countermeasures for Chinese Remaindering Based RSA. In: Breveglieri, L., Koren, I. (eds.) Workshop on Fault Diagnosis and Tolerance in Cryptography – FDTC 2005, pp. 124–132 (2005)
  9. Garner Harvey L., The Residue Number System, 10.1109/tec.1959.5219515
  10. Giraud, C.: Fault Resistant RSA Implementation. In: Breveglieri, L., Koren, I. (eds.) Workshop on Fault Diagnosis and Tolerance in Cryptography – FDTC 2005, pp. 142–151 (2005)
  11. Giraud C., An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis, 10.1109/tc.2006.135
  12. Giraud, C.: Personnal communication (June 29, 2007)
  13. Giraud Christophe, Thiebeauld Hugues, A Survey on Fault Attacks, IFIP International Federation for Information Processing (2004) ISBN:9781402081460 p.159-176, 10.1007/1-4020-8147-2_11
  14. Hemme Ludger, A Differential Fault Attack Against Early Rounds of (Triple-)DES, Lecture Notes in Computer Science (2004) ISBN:9783540226666 p.254-267, 10.1007/978-3-540-28632-5_19
  15. Hoch Jonathan J., Shamir Adi, Fault Analysis of Stream Ciphers, Lecture Notes in Computer Science (2004) ISBN:9783540226666 p.240-253, 10.1007/978-3-540-28632-5_18
  16. Joye Marc, Lenstra Arjen K., Quisquater Jean-Jacques, Chinese Remaindering Based Cryptosystems in the Presence of Faults, 10.1007/s001459900055
  17. Joye Marc, Quisquater Jean-Jacques, Bao Feng, Deng Robert H., RSA-type signatures in the presence of transient faults, Crytography and Coding (1997) ISBN:9783540639275 p.155-160, 10.1007/bfb0024460
  18. Joye Marc, Yen Sung-Ming, The Montgomery Powering Ladder, Cryptographic Hardware and Embedded Systems - CHES 2002 (2003) ISBN:9783540004097 p.291-302, 10.1007/3-540-36400-5_22
  19. Kim Chong Hee, Quisquater Jean-Jacques, Fault Attacks for CRT Based RSA: New Attacks, New Results, and New Countermeasures, Information Security Theory and Practices. Smart Cards, Mobile and Ubiquitous Computing Systems (2007) ISBN:9783540723530 p.215-228, 10.1007/978-3-540-72354-7_18
  20. Kim, C.H., Quisquater, J.-J.: How Can We Overcome Both Side Channel Analysis and Fault Attack on RSA-CRT? In: Breveglieri, L., Gueron, S., Koren, I., Naccache, D., Seifert, J.-P. (eds.) Fault Diagnosis and Tolerance in Cryptography – FDTC 2007, pp. 21–29. IEEE Computer Society Press, Los Alamitos (2007)
  21. Kommerling, O., Kuhn, M.: Design Principles for Tamper Resistant Smartcard Processors. In: The USENIX Workshop on Smartcard Technology (Smartcard 1999), pp. 9–20 (1999)
  22. Naccache David, Nguyên Phong Q., Tunstall Michael, Whelan Claire, Experimenting with Faults, Lattices and the DSA, Public Key Cryptography - PKC 2005 (2005) ISBN:9783540244547 p.16-28, 10.1007/978-3-540-30580-4_3
  23. Piret Gilles, Quisquater Jean-Jacques, A Differential Fault Attack Technique against SPN Structures, with Application to the AES and Khazad, Lecture Notes in Computer Science (2003) ISBN:9783540408338 p.77-88, 10.1007/978-3-540-45238-6_7
  24. Shamir, A.: How to check modular exponentiation. In: Eurocrypt 1997 rump session (1997)
  25. Yen Sung-Ming, Kim Dongryeol, Moon SangJae, Cryptanalysis of Two Protocols for RSA with CRT Based on Fault Infection, Lecture Notes in Computer Science (2006) ISBN:9783540462507 p.53-61, 10.1007/11889700_5
  26. Sung-Ming Yen, Seungjoo Kim, Seongan Lim, Sang-Jae Moon, RSA speedup with chinese remainder theorem immune against hardware fault cryptanalysis, 10.1109/tc.2003.1190587
Bibliographic reference Dottax, E. ; Giraud, C. ; Rivain, M. ; Sierra, Y.. On second-order fault analysis resistance for CRT-RSA implementations.Information Security Theory and Practice. Smart Devices, Pervasive Systems, and Ubiquitous Networks. Third IFIP WG11.2 International Workshop, WISTP 2009 (Brussels, Belgium, 1-4 September 2009). In: Markowitch, O.; Bilas, A.; Hoepman, J.-H.; Mitchell, C.J.; Quisquater, J.-J.;, Information Security Theory and Practice. Smart Devices, Pervasive Systems, and Ubiquitous Networks. Third IFIP WG11.2 International Workshop, WISTP 2009, Springer verlag2009, p. 68-83
Permanent URL http://hdl.handle.net/2078.1/67494