Abstract
Fault Analysis is a powerful cryptanalytic technique that enables to break cryptographic implementations embedded in portable devices more efficiently than any other technique. For an RSA implemented with the Chinese Remainder Theorem method, one faulty execution suffices to factorize the public modulus and fully recover the private key. It is therefore mandatory to protect embedded implementations of RSA against fault analysis.
This paper provides a new countermeasure against fault analysis for exponentiation and RSA. It consists in a self-secure exponentiation algorithm, namely an exponentiation algorithm that provides a direct way to check the result coherence. An RSA implemented with our solution hence avoids the use of an extended modulus (which slows down the computation) as in several other countermeasures. Moreover, our exponentiation algorithm involves 1.65 multiplications per bit of the exponent which is significantly less than the 2 required by other self-secure exponentiations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Amiel, F., Feix, B., Villegas, K.: Power analysis for secret recovering and reverse engineering of public key algorithms. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 110–125. Springer, Heidelberg (2007)
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 Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 260–275. Springer, Heidelberg (2003)
Bao, F., Deng, R., Han, Y., Jeng, A., Narasimhalu, A.D., Ngair, T.-H.: Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault. In: Christianson, B., Lomas, M. (eds.) Security Protocols 1997. LNCS, vol. 1361, pp. 115–124. Springer, Heidelberg (1998)
Berzati, A., Canovas, C., Goubin, L.: (In)security Against Fault Injection Attacks for CRT-RSA Implementations. In: Breveglieri, L., Gueron, S., Koren, I., Naccache, D., Seifert, J.-P. (eds.) FDTC 2008, pp. 101–107. IEEE Computer Society, Los Alamitos (2008)
Berzati, A., Canovas, C., Goubin, L.: Perturbating RSA public keys: An improved attack. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 380–395. Springer, Heidelberg (2008)
Biham, E., Shamir, A.: Differential fault analysis of secret key cryptosystems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 513–525. Springer, Heidelberg (1997)
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.) CCS 2003, pp. 311–320. ACM Press, New York (2003)
Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)
Boreale, M.: Attacking right-to-left modular exponentiation with timely random faults. In: Breveglieri, L., Koren, I., Naccache, D., Seifert, J.-P. (eds.) FDTC 2006. LNCS, vol. 4236, pp. 24–35. Springer, Heidelberg (2006)
Boscher, A., Naciri, R., Prouff, E.: CRT RSA algorithm protected against fault attacks. In: Sauveron, D., Markantonakis, K., Bilas, A., Quisquater, J.-J. (eds.) WISTP 2007. LNCS, vol. 4462, pp. 229–243. Springer, Heidelberg (2007)
Bos, J., Coster, M.: Addition chain heuristics. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 400–407. Springer, Heidelberg (1990)
Brier, É., Chevallier-Mames, B., Ciet, M., Clavier, C.: Why one should also secure RSA public key elements. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 324–338. Springer, Heidelberg (2006)
Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity. IEEE Transactions on Computers 53(6), 760–768 (2004)
Ciet, M., Joye, M.: Practical Fault Countermeasures for Chinese Remaindering Based RSA. In: Breveglieri, L., Koren, I. (eds.) FDTC 2005, pp. 124–132 (2005)
Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
Dottax, E., Giraud, C., Rivain, M., Sierra, Y.: On Second-Order Fault Analysis Resistance for CRT-RSA Implementations. Cryptology ePrint Archive, Report 2009/24 (2009), http://eprint.iacr.org/2009/024
Fouque, P.-A., Valette, F.: The Doubling Attack: Why Upwards is Better than Downwards. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 269–280. Springer, Heidelberg (2003)
Giraud, C.: An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis. IEEE Transactions on Computers 55(9), 1116–1120 (2006)
Gordon, D.M.: A Survey of Fast Exponentiation Methods. J. Algorithms 27(1), 129–146 (1998)
Itoh, K., Izu, T., Takenak, M.: Address-bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 129–143. Springer, Heidelberg (2003)
Itoh, K., Izu, T., Takenaka, M.: A Practical Countermeasure against Address-Bit Differential Power Analysis. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 382–396. Springer, Heidelberg (2003)
Joye, M., Lenstra, A., Quisquater, J.-J.: Chinese Remaindering Based Cryptosystems in the Presence of Faults. Journal of Cryptology 12(4), 241–245 (1999)
Kim, C.H., Quisquater, J.-J.: Fault Attacks for CRT Based RSA: New Attacks, New Results, and New Countermeasures. In: Sauveron, D., Markantonakis, K., Bilas, A., Quisquater, J.-J. (eds.) WISTP 2007. LNCS, vol. 4462, pp. 215–228. Springer, Heidelberg (2007)
Kim, C.H., Shin, J.H., Quisquater, J.-J., Lee, P.J.: Safe-error attack on SPA-FA resistant exponentiations using a HW modular multiplier. In: Nam, K.-H., Rhee, G. (eds.) ICISC 2007. LNCS, vol. 4817, pp. 273–281. Springer, Heidelberg (2007)
Knuth, D.: The Art of Computer Programming, 3rd edn. Addison-Wesley, Reading (1988)
Kocher, P., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Kocher, P.: Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Koç, Ç.: Analysis of the Sliding Window Techniques for Exponentiation. Computer & Mathematics with applications 30(10), 17–24 (1995)
Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
Messerges, T., Dabbish, E., Sloan, R.: Power Analysis Attacks of Modular Exponentiation in Smartcard. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 144–157. Springer, Heidelberg (1999)
Mitrinovic, D.S., Sándor, J., Crstici, B.: Handbook of Number Theory. Springer, Heidelberg (1995)
Möller, B.: Algorithms for multi-exponentiation. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 165–180. Springer, Heidelberg (2001)
Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Schmidt, J., Herbst, C.: A Practical Fault Attack on Square and Multiply. In: Breveglieri, L., Gueron, S., Koren, I., Naccache, D., Seifert, J.-P. (eds.) FDTC 2008, pp. 53–58. IEEE Computer Society, Los Alamitos (2008)
Seifert, J.-P.: On Authenticated Computing and RSA-based Authentication. In: Atluri, V., Meadows, C., Juels, A. (eds.) ACM CCS 2005, pp. 122–127. ACM Press, New York (2005)
Shamir, A.: Improved Method and Apparatus for Protecting Public Key Schemes from Timing and Fault Attacks. Publication number: WO9852319 (November 1998)
Sun Microsystems. Application Programming Interface – Java CardTM Plateform, Version 2.2.2 (March 2006), http://java.sun.com/products/javacard/specs.html
Vigilant, D.: RSA with CRT: A new cost-effective solution to thwart fault attacks. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 130–145. Springer, Heidelberg (2008)
Wagner, D.: Cryptanalysis of a Provable Secure CRT-RSA Algorithm. In: Pfitzmann, B., Liu, P. (eds.) CCS 2004, pp. 82–91. ACM Press, New York (2004)
Yen, S.-M., Joye, M.: Checking Before Output Not Be Enough Against Fault-Based Cryptanalysis. IEEE Transactions on Computers 49(9), 967–970 (2000)
Yen, S.-M., Kim, S.-J., Lim, S.-G., Moon, S.-J.: A countermeasure against one physical cryptanalysis may benefit another attack. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 414–427. Springer, Heidelberg (2002)
Yen, S.-M., Kim, S.-J., Lim, S.-G., Moon, S.-J.: RSA Speedup with Residue Number System Immune against Hardware Fault Cryptanalysis. IEEE Transactions on Computers 52(4), 461–472 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rivain, M. (2009). Securing RSA against Fault Analysis by Double Addition Chain Exponentiation. In: Fischlin, M. (eds) Topics in Cryptology – CT-RSA 2009. CT-RSA 2009. Lecture Notes in Computer Science, vol 5473. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00862-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-00862-7_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00861-0
Online ISBN: 978-3-642-00862-7
eBook Packages: Computer ScienceComputer Science (R0)