Abstract
Since the introduction of the side-channel and fault injection analysis late in the 90’s, implementing cryptographic standards on embedded devices has become a difficult challenge. Developers were obliged to add new appropriate countermeasures into their code. To prevent those separate threats, they often implemented countermeasures separately. The side-channel dedicated countermeasures were added to the algorithm when on the other hand specific protections against fault injections, like computation verifications, were implemented. However in 2007 Amiel et al.demonstrated that a single fault injection combined with simple side-channel analysis can defeat such a classical implementation. Then it became obvious that side-channel and fault countermeasures had to be designed together. In that vein Schmidt et al.published at Latincrypt 2010 an efficient exponentiation algorithm supposedly resistant against this combined attack category. Despite the clever design of these algorithms, we present here two new attacks that can defeat its security. Our first attack is a single fault injection scheme requiring only few faulted ciphertexts. The second one requires the combination of a single fault injection with a differential treatment. We also propose a more secure version of this algorithm that thwarts our attacks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Amiel, F., Feix, B., Tunstall, M., Whelan, C., Marnane, W.P.: Distinguishing multiplications from squaring operations. In: Avanzi, R., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 346–360. Springer, Heidelberg (2009)
Amiel, F., Villegas, K., Feix, B., Marcel, L.: Passive and active combined attacks: combining fault attacks and side channel analysis. In: Breveglieri, I., Gueron, S., Koren, I., Naccache, D., Seifert, J. (eds.) FDTC, pp. 92–102. IEEE Computer Society, Washington, DC (2007)
Berzati, A., Canovas-Dumas, C., Goubin, L.: Public key perturbation of randomized RSA implementations. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 306–319. Springer, Heidelberg (2010)
Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost solutions for preventing simple side-channel analysis: Side-channel atomicity. IEEE Transactions on Computers 53, 760–768 (2004)
Courrège, J.-C., Feix, B., Roussellet, M.: Simple power analysis on exponentiation revisited. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) CARDIS 2010. LNCS, vol. 6035, pp. 65–79. Springer, Heidelberg (2010)
Dehbaoui, A., Dutertre, J., Robisson, B., Orsatelli, P., Maurine, P., Tria, A.: Injection of transient faults using electromagnetic pulses-practical results on a cryptographic system. Cryptology ePrint Archive, Report 2012/123 (2012)
Fan, J., Gierlichs, B., Vercauteren, F.: To infinity and beyond: Combined attack on ECC using points of low order. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 143–159. Springer, Heidelberg (2011)
Gandolfi, K., Mourtel, C., Olivier, F.: Electromagnetic analysis: Concrete results. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 251–261. Springer, Heidelberg (2001)
Giraud, C.: An RSA implementation resistant to fault attacks and to simple power analysis. IEEE Transactions on Computers 55(9), 1116–1120 (2006)
Hanley, N., Tunstall, M., Marnane, W.: Using templates to distinguish multiplications from squaring operations. International Journal of Information Security 10, 255–266 (2011)
Joye, M.: Protecting RSA against fault attacks: The embedding method. In: Breveglieri, L., Koren, I., Naccache, D., Oswald, E., Seifert, J.P. (eds.) Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2009, pp. 41–45. IEEE Computer Society Press (2009)
Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48, 203–209 (1987)
Kocher, P.C.: 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)
Medwed, M., Herbst, C.: Randomizing the Montgomery multiplication to repel template attacks on multiplicative masking. In: COSADE 2010 (2010)
Messerges, T., Dabbish, E., Sloan, R.: Investigations of power analysis attacks on smartcards. In: USENIX Workshop on Smartcard Technology, pp. 151–161 (1999)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Poucheret, F., Tobich, K., Lisart, M., Chusseau, L., Robisson, B., Maurine, P.: Local and direct EM injection of power into CMOS integrated circuits. In: FDTC, pp. 100–104 (2011)
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21, 120–126 (1978)
Schindler, W., Itoh, K.: Exponent blinding does not always lift (Partial) SPA resistance to higher-level security. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 73–90. Springer, Heidelberg (2011)
Schmidt, J.-M., Tunstall, M., Avanzi, R., Kizhvatov, I., Kasper, T., Oswald, D.: Combined implementation attack resistant exponentiation. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 305–322. Springer, Heidelberg (2010)
Verneuil, V.: Elliptic Curve Cryptography and Security of Embedded Devices. Ph.D. thesis, Université de Bordeaux (2012)
Witteman, M.F., van Woudenberg, J.G.J., Menarini, F.: Defeating RSA multiply-always and message blinding countermeasures. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 77–88. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feix, B., Venelli, A. (2013). Defeating with Fault Injection a Combined Attack Resistant Exponentiation. In: Prouff, E. (eds) Constructive Side-Channel Analysis and Secure Design. COSADE 2013. Lecture Notes in Computer Science, vol 7864. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40026-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-40026-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40025-4
Online ISBN: 978-3-642-40026-1
eBook Packages: Computer ScienceComputer Science (R0)