Abstract
Elliptic curve cryptosystem (ECC) is well-suited for the implementation on memory constraint environments due to its small key size. However, side channel attacks (SCA) can break the secret key of ECC on such devices, if the implementation method is not carefully considered. The scalar multiplication of ECC is particularly vulnerable to the SCA. In this paper we propose an SCA-resistant scalar multiplication method that is allowed to take any number of pre-computed points. The proposed scheme essentially intends to resist the simple power analysis (SPA), not the differential power analysis (DPA). Therefore it is different from the other schemes designed for resisting the DPA. The previous SPA-countermeasures based on window methods utilize the fixed pattern windows, so that they only take discrete table size. The optimal size is 2w − 1 for w=2,3,..., which was proposed by Okeya and Takagi. We play a different approach from them. The key idea is randomly (but with fixed probability) to generate two different patterns based on pre-computed points. The two distributions are indistinguishable from the view point of the SPA. The proposed probabilistic scheme provides us more flexibility for generating the pre-computed points — the designer of smart cards can freely choose the table size without restraint.
Chapter PDF
Similar content being viewed by others
Keywords
References
ANSI X9.62, Public Key Cryptography for the Financial Services Industry. The Elliptic Curve Digital Signature Algorithm, ECDSA (1998)
Brier, É., Joye, M.: Weierstrass Elliptic Curves and Side-Channel Attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002)
Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)
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)
Fischer, W., Giraud, C., Knudsen, E.W., Seifert, J.P.: Parallel scalar multiplication on general elliptic curves over Fp hedged against Non-Differential Side-Channel Attacks. International Association for Cryptologic Research (IACR), Cryptology ePrint Archive 2002/007 (2002), http://eprint.iacr.org/2002/007/
Goubin, L.: A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 199–211. Springer, Heidelberg (2002)
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 (2003)
Han, D.-G., Chang, N.S., Jung, S.W., Park, Y.-H., Kim, C.H., Ryu, H.: Cryptanalysis of the Full version Randomized Addition-Subtraction Chains. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, Springer, Heidelberg (2003) (to appear)
Itoh, K., Izu, T., Takenaka, M.: Address-bit Differential Power Analysis on 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., Yajima, J., Takenaka, M., Torii, N.: DPA Countermeasures by improving the Window Method. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 318–332. Springer, Heidelberg (2003)
IEEE P1363, Standard Specifications for Public-Key Cryptography, http://groupe.ieee.org/groups/1363/
Izu, T., Takagi, T.: A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 280–296. Springer, Heidelberg (2002)
Joye, M., Quisquater, J.J.: Hessian elliptic curves and side-channel attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 402–410. Springer, Heidelberg (2001)
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. LNCS, vol. 2162, pp. 377–390. Springer, Heidelberg (2001)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48, 203–209 (1987)
Kocher, C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Koyama, K., Tsuruoka, Y.: Speeding Up Elliptic Curve Cryptosystems using a Signed Binary Windows Method. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 345–357. Springer, Heidelberg (1993)
Liardet, P.Y., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 391–401. Springer, Heidelberg (2001)
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)
Miyaji, A., Ono, T., Cohen, H.: Efficient elliptic curve exponentiation. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 282–291. Springer, Heidelberg (1997)
Möller, B.: Securing Elliptic Curve Point Multiplication against Side- Channel Attacks. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, pp. 324–334. Springer, Heidelberg (2001)
Möller, B.: Securing elliptic curve point multiplication against side-channel attacks, addendum: Efficiency improvement (2001), http://www.informatik.tudarmstadt.de/TI/Mitarbeiter/moeller/ecc-scaisc01.pdf
Möller, B.: Parallelizable Elliptic Curve Point Multiplication Method with Resistance against Side-Channel Attacks. In: Chan, A.H., Gligor, V.D. (eds.) ISC 2002. LNCS, vol. 2433, pp. 402–413. Springer, Heidelberg (2002)
Möller, B.: Improved Techniques for Fast Exponentiation. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 298–312. Springer, Heidelberg (2003)
National Institute of Standards and Technology, FIPS 186-2, http://csrc.nist.gov/publication/fips/fips186-2/fips186-2.pdf
Oswald, E., Aigner, M.: Randomized Addition-Subtraction Chains as a Countermeasure against Power Attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 39–50. Springer, Heidelberg (2001)
Okeya, K., Sakurai, K.: Power Analysis Breaks Elliptic Curve Cryptosystems even Secure against the Timing Attack. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 178–190. Springer, Heidelberg (2000)
Okeya, K., Sakurai, K.: On Insecurity of the Side Channel Attack Countermeasure using Addition-Subtraction Chains under Distinguishability between Addition and Doubling. In: Batten, L.M., Seberry, J. (eds.) ACISP 2002. LNCS, vol. 2384, pp. 420–435. Springer, Heidelberg (2002)
Okeya, K., Sakurai, K.: A Second-Order DPA Attack Breaks a Window-method based Countermeasure against Side Channel Attacks. In: Chan, A.H., Gligor, V.D. (eds.) ISC 2002. LNCS, vol. 2433, pp. 389–401. Springer, Heidelberg (2002)
Okeya, K., Sakurai, K.: A Multiple Power Analysis Breaks the Advanced Version of the Randomized Addition-Subtraction Chains Countermeasure against Side Channel Attacks. In: 2003 IEEE Information TheoryWorkshop (ITW 2003) (these proceedings) (2003)
Oswald, E.: Enhancing Simple Power-Analysis Attacks on Elliptic Curve Cryptosystems. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 82–97. Springer, Heidelberg (2003)
Okeya, K., Takagi, T.: The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 328–342. Springer, Heidelberg (2003)
Standards for Efficient Cryptography Group (SECG), http://www.secg.org
Solinas, J.A.: Efficient Arithmetic on Koblitz Curves. Design, Codes and Cryptography 19, 195–249 (2000)
Walter, C.D.: Some Security Aspects of the Mist Randomized Exponentiation Algorithm. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 564–578. Springer, Heidelberg (2003)
Walter, C.D.: Breaking the Liardet-Smart Randomized Exponentiation Algorithm. In: Proceedings of CARDIS 2002, USENIX Assoc., pp. 59–68 (2002)
Walter, C.D.: Security Constraints on the Oswald-Aigner Exponentiation Algorithm. In: International Association for Cryptologic Research (IACR), Cryptology ePrint Archive 2003/013 (2003), http://eprint.iacr.org/2003/013/
Walter, C.D.: Seeing through Mist Given a Small Fraction of an RSA Private Key, Topics in Cryptology. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 391–402. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okeya, K., Takagi, T. (2003). A More Flexible Countermeasure against Side Channel Attacks Using Window Method. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems - CHES 2003. CHES 2003. Lecture Notes in Computer Science, vol 2779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45238-6_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-45238-6_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40833-8
Online ISBN: 978-3-540-45238-6
eBook Packages: Springer Book Archive