Abstract
Since Kocher’s first attacks in 1996, the field of side-channel analysis has widely developed, and new statistical tools have competed against new countermeasures to threaten cryptosystems. Among existing algorithms, RSA has always been a privileged target. It seems generally admitted that a combination of SPA protection such as regular exponentiation associated with blinding techniques such as randomization of the exponent and of the input message offers in practice sufficient protection against all known side-channel attacks. Indeed, known attacks either require building statistical information over several executions of the algorithm, which is countered by exponent randomization, or rely on partial SPA leakage, which implies an incorrect implementation of known countermeasures, or require specific internal knowledge of the implementation and hard-to-obtain experimental conditions, as for the recent horizontal correlation analysis of Clavier et al. [10]. In this paper, we show that it is possible to attack a state-of-the-art implementation of Straightforward Method (SFM) RSA. Our attack requires a small public exponent (no greater than 216 + 1) and a reasonable exponent blinding factor (no greater than 32 bits). It does not require additional internal knowledge of the implementation, neither does it have special experimental requirements. From a practical point of view, it thus compares with classical correlation analysis. We provide simulations of our attack demonstrating its efficiency, even in noisy scenarios. This shows that SFM implementations of RSA may be much more difficult to protect against side-channel attacks than CRT implementations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Amiel, F., Feix, B., Tunstall, M., Whelan, C., Marnane, W.P.: Distinguishing Multiplications from Squaring Operations. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 346–360. Springer, Heidelberg (2009)
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)
Bastina, L., Gierlichs, B., Prouff, E., Rivain, M., Standaert, F.-X., Veyrat-Charvillon, N.: Mutual Information Analysis: A Comprehensive Study. Journal of Cryptology 24(2), 269–291 (2011)
Bauer, A., Jaulmes, E., Prouff, E., Wild, J.: Horizontal and vertical side-channel attacks against secure RSA implementations. In: Dawson, E. (ed.) RSA 2013. LNCS, vol. 7779, pp. 1–17. Springer, Heidelberg (2013)
Boneh, D.: Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society, AMS (1999)
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 1998. LNCS, vol. 1514, pp. 25–34. Springer, Heidelberg (1998)
Brier, E., Clavier, C., Olivier, F.: Correlation Power Analysis with a Leakage Model. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 16–29. Springer, Heidelberg (2004)
Chevallier-Mames, B., Ciet, M., Joye, M.: Lowcost Solutions for Preventing Simple Side-Channel Cryptanalysis: Side-Channel Atomicity. IEEE Transactions on Computers 53(6), 760–768 (2004)
Clavier, C., Feix, B., Gagnerot, G., Giraud, C., Roussellet, M., Verneuil, V.: ROSETTA for Single Trace Analysis – Recovery of Secret Exponent by Triangular Trace Analysis. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 140–155. Springer, Heidelberg (2012)
Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal Correlation Analysis on Exponentiation. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 46–61. Springer, Heidelberg (2010)
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)
Fouque, P.-A., Kunz-Jacques, S., Martinet, G., Muller, F., Valette, F.: Power Attack on Small RSA Public Exponent. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 339–353. Springer, Heidelberg (2006)
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)
Gierlichs, B., Batina, L., Tuyls, P., Preneel, B.: Mutual Information Analysis. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 426–442. Springer, Heidelberg (2008)
Joye, M.: Highly regular m-ary powering ladders. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 350–363. Springer, Heidelberg (2009)
Joye, M., Yen, S.-M.: The Montgomery Powering Ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
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)
Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
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)
Walter, C.D.: Sliding Windows Succumbs to Big Mac Attack. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 286–299. Springer, Heidelberg (2001)
Walter, C.D.: Longer Keys May Facilitate Side Channel Attacks. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 42–57. Springer, Heidelberg (2004)
Walter, C.D.: Longer Randomely Blinded RSA Keys May Be Weaker Than Shorter Ones. In: Kim, S., Yung, M., Lee, H.-W. (eds.) WISA 2007. LNCS, vol. 4867, pp. 303–316. Springer, Heidelberg (2008)
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 International Publishing Switzerland
About this paper
Cite this paper
Bauer, A., Jaulmes, É. (2013). Correlation Analysis against Protected SFM Implementations of RSA. In: Paul, G., Vaudenay, S. (eds) Progress in Cryptology – INDOCRYPT 2013. INDOCRYPT 2013. Lecture Notes in Computer Science, vol 8250. Springer, Cham. https://doi.org/10.1007/978-3-319-03515-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-03515-4_7
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03514-7
Online ISBN: 978-3-319-03515-4
eBook Packages: Computer ScienceComputer Science (R0)