Abstract
Exponent splitting is a classical technique to protect modular exponentiation against side-channel attacks. Although it is rarely implemented due to efficiency reasons, it is widely considered as a highly-secure solution. Therefore it is often used as a reference to benchmark new countermeasure proposals.
In this paper, we make new observations about the statistical behavior of the splitting of the exponent. We look at the correlations between the two shares, and show an important imbalance. Later, we show how to use this imbalance in higher-order attacks (mostly based on address-bit, safe-error and fault analysis). We also present experimental results to estimate their feasibility.
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
Bleichenbacher, D.: On the Generation of DSA One-time Keys. Presented at the Workshop on Elliptic Curve Cryptography – ECC 2002 (2002)
Blömer, J., May, A.: New Partial Key Exposure Attacks on RSA. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 27–43. Springer, Heidelberg (2003)
Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract). In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)
Chari, S., Jutla, C., Rao, J., Rohatgi, P.: Towards Sound Approaches to Counteract Power-Analysis Attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999)
Chevallier-Mames, B.: Self-Randomized Exponentiation Algorithms. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 236–249. Springer, Heidelberg (2004)
Clavier, C., Joye, M.: Universal Exponentiation Algorithm. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 300–308. Springer, Heidelberg (2001)
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., Muller, F., Poupard, G., Valette, F.: Defeating Countermeasures Based on Randomized BSD Representations. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 312–327. Springer, Heidelberg (2004)
Gandolfi, K., Mourtel, C., Olivier, F.: Electromagnetic Analysis: Concret Results. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 251–261. Springer, Heidelberg (2001)
Goubin, L., Patarin, J.: DES and Differential Power Analysis, The ”Duplication” Method. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 158–172. Springer, Heidelberg (1999)
Ha, J., Moon, S.: Randomized signed-scalar Multiplication of ECC to resist Power Attacks. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 551–563. Springer, Heidelberg (2002)
Itoh, K., Izu, T., Takenaka, 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 (2002)
Karlof, C., Wagner, D.: Hidden Markov Model Cryptanalysis. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 17–34. Springer, Heidelberg (2003)
Kocher, P.C.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Others Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Kocher, P., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS) FIPS Publication 186-2 (February 2000), Available at http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf
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)
Shamir, A.: How to Share a Secret. Communications of the ACM (CACM) 22(11), 612–613 (1979)
Trichina, E., Bellezza, A.: Implementation of Elliptic Curve Cryptography with Built-In Counter Measures against Side Channel Attacks. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 98–113. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Muller, F., Valette, F. (2006). High-Order Attacks Against the Exponent Splitting Protection. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11745853_21
Download citation
DOI: https://doi.org/10.1007/11745853_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33851-2
Online ISBN: 978-3-540-33852-9
eBook Packages: Computer ScienceComputer Science (R0)