Abstract
Since side channel analysis was introduced as a method to recover secret information from an otherwise secure cryptosystem, many countermeasures have been proposed to prevent leakage from secure devices. Among these countermeasures is side channel atomicity that makes operations indistinguishable using side channel analysis. In this paper, we present practical results of an attack on RSA signature generation, protected in this manner, based on the expected difference in Hamming weight between the result of a multiplication and a squaring operation. This work presents the first attack that we are aware of where template analysis can be used without requiring an open device to characterize an implementation of a given cryptographic algorithm. Moreover, an attacker does not need to know the plaintexts being operated on and, therefore, blinding and padding countermeasures applied to the plaintext do not hinder the attack in anyway.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akishita T., Takagi T.: Power analysis to ECC using differential power between multiplication and squaring. In: Domingo-Ferrer, J., Posegga, J., Schreckling, D. (eds) CARDIS 2006, vol. 3928 of LNCS, pp. 151–164. Springer, Berlin (2006)
Amiel F., Feix B., Tunstall M., Whelan C., Marnane W.P.: Distinguishing multiplications from squaring operations. In: Youm, H.Y., Yung, M. (eds) SAC 2008, vol. 5932 of LNCS, pp. 148–162. Springer, Berlin (2009)
ARM Limited: ARM7TDMI technical reference manual (revision r4p1), http://infocenter.arm.com/ (2004)
Bernstein D.J., Lange T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (eds) ASIACRYPT 2007, vol. 4833 of LNCS, pp. 29–50. Springer, Berlin (2007)
Blömer J., May A.: New partial key exposure attacks on RSA. In: Boneh, D. (eds) CRYPTO 2003, vol. 2729 of LNCS, pp. 27–43. Springer, Berlin (2003)
Boneh D., Durfee G., Frankel Y.: An attack on RSA given a small fraction of the private key bits. In: Ohta, K., Pei, D. (eds) ASIACRYPT 98, vol. 1514 of LNCS, pp. 25–34. Springer, Berlin (1998)
Brier E., Clavier C., Olivier F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.-J. (eds) CHES 2004, vol. 3156 of LNCS, pp. 16–29. Springer, Berlin (2004)
Brier E., Joye M.: Weierstraß elliptic curve and side-channel attacks. In: Naccache, D., Paillier, P. (eds) PKC 2002, vol. 2274 of LNCS, pp. 335–345. Springer, Berlin (2002)
Chari S., Rao J.R., Rohatgi P.: Template attacks. In: Kaliski, B.S., Koç, Ç.K., Paar, C. (eds) CHES 2002, vol. 2523 of LNCS, pp. 13–28. Springer, Berlin (2003)
Chevallier-Mames B., Ciet M., Joye M.: Low-cost solutions for preventing simple side-channel analysis: Side-channel atomicity. IEEE Trans. Comput. 53(6), 760–768 (2004)
Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. Cryptology ePrint Archive, Report 2010/394, http://eprint.iacr.org/ (2010)
Coron J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, C.K., Paar, C. (eds) CHES 99, vol. 1717 of LNCS, pp. 292–302. Springer, Berlin (1999)
Fahn P.N., Pearson P.K.: IPA: a new class of power attacks. In: Koç, Ç.K., Paar, C. (eds) CHES 1999, vol. 1717 of LNCS, pp. 173–186. Springer, Berlin (1999)
Gandolfi K., Mourtel C., Olivier F.: Electromagnetic analysis: concrete results. In: Koç, C.K., Naccache, D., Paar, C. (eds) CHES 2001, vol. 2162 of LNCS, pp. 251–261. Springer, Berlin (2001)
Green P.J., Noad R., Smart N.P.: Further hidden Markov model cryptanalysis. In: Rao, J.R., Sunar, B. (eds) CHES 2005, vol. 3659 of LNCS, pp. 61–74. Springer, Berlin (2005)
Großschädl J., Oswald E., Page D., Tunstall M.: Side channel analysis of cryptographic software via early-terminating multiplications. In: Lee, D., Hong, S. (eds) ICISC 2009, vol. 5984 of LNCS, pp. 176–192. Springer, Berlin (2010)
Hachez G., Quisquater J.-J.: Montgomery exponentiation with no final subtractions: Improved results. In: Koç, C.K., Paar, C. (eds) CHES 2000, vol. 1965 of LNCS, pp. 293–301. Springer, Berlin (2000)
Herbst C., Medwed M.: Using templates to attack masked Montgomery ladder implementations of modular exponentiation. In: Chung, K.-I., Sohn, K., Yung, M. (eds) WISA 2008, vol. 5379 of LNCS, pp. 1–13. Springer, Berlin (2009)
Joye M., Tunstall M.: Exponent recoding and regular exponentiation algorithms. In: Preneel, B. (eds) AFRICACRYPT 2009, vol. 5580 of LNCS, pp. 334–349. Springer, Berlin (2009)
Joye M., Tymen C.: Protections against differential analysis for elliptic curve cryptography: An algebraic approach. In: Koç, Ç.K., Naccache, D., Paar, C. (eds) CHES 2001, vol. 2162 of LNCS, pp. 377–390. Springer, Berlin (2001)
Kocher, P.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO ’96, vol. 1109 of LNCS, pp. 104–113. Springer, Berlin (1996)
Kocher P., Jaffe J., Jun B.: Differential power analysis. In: Wiener, M.J. (eds) CRYPTO ’99, vol. 1666 of LNCS, pp. 388–397. Springer, Berlin (1999)
Mangard S., Oswald E., Popp T.: Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer, Berlin (2007)
Medwed M., Oswald E.: Template attacks on ECDSA. In: Chung, K.-I., Sohn, K., Yung, M. (eds) WISA 2008, vol. 5379 of LNCS, pp. 14–27. Springer, Berlin (2009)
Menezes A.J., van Oorschot P.C., Vanstone S.A.: Handbook of Applied Cryptography. CRC Press, USA (1997)
Montgomery P.: Modular multiplication without trial division. Math. Comput. 44, 519–521 (1985)
Nguyen P.Q., Shparlinski I.E.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)
Nguyen P.Q., Shparlinski I.E.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptogr. 30, 201–217 (2003)
Oswald E., Mangard S.: Template attacks on masking— resistance is futile. In: Abe, M. (eds) CT-RSA 2007, vol. 4377 of LNCS, pp. 243–256. Springer, Berlin (2007)
Quisquater, J.-J., Samyde, D.: Electromagnetic analysis (EMA): measures and counter-measures for smart cards. In: Attali, I., Jensen, T.P. (eds.) Smart card programming and security, International conference on research in smart cards—E-smart 2001, vol. 2140 of LNCS, pp. 200–210. Springer, Berlin (2001)
Rechberger C., Oswald E.: Practical template attacks. In: Lim, C.H., Yung, M. (eds) WISA 2004, vol. 3325 of LNCS, pp. 440–456. Springer, Berlin (2004)
Rivest R., Shamir A., Adleman L.M.: Method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Smart N., Oswald E., Page D.: Randomised representations. IET Proc. Inf. Sec. 2(2), 19–27 (2008)
Walter C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35(21), 1831–1832 (1999)
Walter, C.D.: Longer keys may facilitate side channel attacks. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2004, vol. 3006 of LNCS, pp. 42–57. Springer, Berlin (2004)
Walter C.D.: Simple power analysis of unified code for ECC double and add. In: Joye, M., Quisquater, J.-J. (eds) CHES 2004, vol. 3156 of LNCS, pp. 191–204. Springer, Berlin (2004)
Walter C.D., Thompson S.: Distinguishing exponent digits by observing modular subtractions. In: Naccache, D. (eds) CT-RSA 2001, vol. 2020 of LNCS, pp. 192–207. Springer, Berlin (2001)
ANSI X9.62.: Public key cryptography for the financial services industry, the elliptic curve digital signature algorithm (ECDSA) (1999)
Yen S.-M., Joye M.: Checking before output may not be enough against fault based cryptanalysis. IEEE Trans. Comput. 49(9), 967–970 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hanley, N., Tunstall, M. & Marnane, W.P. Using templates to distinguish multiplications from squaring operations. Int. J. Inf. Secur. 10, 255–266 (2011). https://doi.org/10.1007/s10207-011-0135-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10207-011-0135-4