A comparison of simple side-channel analysis countermeasures for variable-base elliptic curve scalar multiplication
Resumo
Side-channel attacks are a growing threat to implementations of cryptographic systems. This article examines the state of the art of algorithmic countermeasures against simple side-channel attacks on elliptic curve cryptosystems defined over prime fields. We evaluate the security versus computation cost trade-offs of SSCA countermeasures for variable-base scalar multiplication algorithms without precomputation. The expected performance impact of each countermeasure is analyzed regarding their computational cost in terms of finite field operations.Referências
Abarzúa, R. and Thériault, N. (2012). Complete Atomic Blocks for Elliptic Curves in Jacobian Coordinates over Prime Fields. In Hevia, A. and Neven, G., editors, Progress in Cryptology – LATINCRYPT 2012, volume 7533 of LNCS, pages 37–55. Springer Berlin / Heidelberg.
Aciiçmez, O. and Koç, c. K. (2009). Microarchitectural Attacks and Countermeasures. In Cryptographic Engineering, chapter 18. Springer.
Amiel, F., Feix, B., Tunstall, M., Whelan, C., and Marnane, W. P. (2009). Distinguishing multiplications from squaring operations. In Selected Areas in Cryptography, pages 346–360. Springer.
Amiel, F., Villegas, K., Feix, B., and Marcel, L. (2007). Passive and active combined attacks: Combining fault attacks and side channel analysis. In Fault Diagnosis and Tolerance in Cryptography, 2007. FDTC 2007. Workshop on, pages 92–102.
Bernstein, D. and Lange, T. (2007). Inverted edwards coordinates. In Boztas¸, S. and Lu, H.-F., editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 4851 of LNCS, pages 20–27. Springer.
Bernstein, D. J., Birkner, P., Joye, M., Lange, T., and Peters, C. (2008). Twisted edwards curves. In Progress in Cryptology–AFRICACRYPT 2008, pages 389–405. Springer.
Brier, E., Dechene, I., and Joye, M. (2004). Unified Point Addition Formulae for Elliptic Curve Cryptosystems. In Embedded Cryptographic Hardware: Methodologies and Architectures, pages 247–256. Nova Science Publishers.
Brier, E. and Joye, M. (2002). Weierstrass Elliptic Curves and Side-Channel Attacks. In Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems, vol 2274, pages 335–345. Springer.
Certicom (2010). SEC 2: Recommended Elliptic Curve Domain Parameters, version 2.0. Technical report, Certicom Corp.
Chen, T., Li, H., Wu, K., and Yu, F. (2009). Countermeasure of ECC against Sidechannel Attacks: Balanced Point Addition and Point Doubling Operation Procedure. Asia-Pacific Conference on Information Processing.
Chevallier-Mames, B., Ciet, M., and Joye, M. (2004). Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. Computers, IEEE Transactions on, 53(6):760–768.
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., and Vercauteren, F. (2010). Handbook of elliptic and hyperelliptic curve cryptography. Chapman and Hall/CRC.
Coron, J.-S. (1999). Resistance against differential power analysis for elliptic curve cryptosystems. In Cryptographic Hardware and Embedded Systems, pages 292–302. Springer.
Edwards, H. (2007). A normal form for elliptic curves. Bulletin of the American Mathematical Society, 44(3):393–422.
Fischer, W. and Giraud, C. (2002). Parallel scalar multiplication on general elliptic curves IACR Cryptology over Fp hedged against Non-Differential Side-Channel Attacks. ePrint Archive.
Fouque, P.-A. and Valette, F. (2003). The doubling attack – why upwards is better than downwards. In Walter, C., Koç, e., and Paar, C., editors, Cryptographic Hardware and Embedded Systems CHES 2003, volume 2779 of LNCS, pages 269–280. Springer.
Gandolfi, K., Mourtel, C., and Olivier, F. (2001). Electromagnetic analysis: Concrete results. In Cryptographic Hardware and Embedded Systems CHES 2001, pages 251– 261. Springer.
Giraud, C. and Verneuil, V. (2010). Atomicity improvement for elliptic curve scalar multiplication. In Gollmann, D., Lanet, J.-L., and Iguchi-Cartigny, J., editors, Smart Card Research and Advanced Application, volume 6035 of LNCS, pages 80–101. Springer.
Goundar, R., Joye, M., Miyaji, A., Rivain, M., and Venelli, A. (2011). Scalar multiplication on Weierstraßelliptic curves from Co-Z arithmetic. Journal of Cryptographic Engineering, 1(2):161–176.
Hanley, N., Tunstall, M., and Marnane, W. (2011). Using templates to distinguish multiplications from squaring operations. International Journal of Information Security, 10(4):255–266.
Hisil, H., Wong, K. K.-H., Carter, G., and Dawson, E. (2008). Twisted Edwards curves revisited. In Advances in Cryptology-ASIACRYPT 2008, pages 326–343. Springer.
Izu, T. and Takagi, T. (2002a). A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. In Public Key Cryptography – PKC 2002, pages 280– 296.
Izu, T. and Takagi, T. (2002b). Exceptional procedure attack on elliptic curve cryptosystems. In Public Key Cryptography—PKC 2003, pages 224–239. Springer.
Joye, M. (2007). Highly regular right-to-left algorithms for scalar multiplication. In Cryptographic Hardware and Embedded Systems CHES 2007, pages 135–147. Springer.
Joye, M., Tibouchi, M., and Vergnaud, D. (2010). Huff’s model for elliptic curves. In Algorithmic Number Theory, pages 234–250. Springer.
Joye, M. and Yen, S.-M. (2003). The Montgomery powering ladder. In Cryptographic Hardware and Embedded Systems-CHES 2002, pages 291–302. Springer.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177):203–209.
Kocher, P. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Koblitz, N., editor, Advances in Cryptology CRYPTO ’96, volume 1109 of LNCS, pages 104–113. Springer Berlin / Heidelberg.
Kocher, P., Jaffe, J., and Jun, B. (1999). Differential Power Analysis. In Wiener, M., editor, Advances in Cryptology CRYPTO ’99, volume 1666 of LNCS, page 789. Springer Berlin / Heidelberg.
Longa, P. and Miri, A. (2008). Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields. In Computers, IEEE Transactions on, volume 57, pages 289–302.
Mangard, S., Oswald, E., and Popp, T. (2007). Power analysis attacks: Revealing the secrets of smart cards, volume 31. Springer.
Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Advances in Cryptology -CRYPTO Proceedings, pages 417–426. Springer.
Montgomery, P. L. (1987). Speeding the Pollard and elliptic curve methods of factorization. Mathematics of computation, 48(177):243–264.
NIST (2000). FIPS 186-2: Digital Signature Standard. Technical report, NIST.
Quisquater, J.-J. and Samyde, D. (2001). Electromagnetic analysis (ema): Measures and counter-measures for smart cards. In Smart Card Programming and Security, pages 200–210. Springer.
Schindler, W. (2002). A Combined Timing and Power Attack. In Naccache, D. and Paillier, P., editors, Public Key Cryptography SE 19, volume 2274 of LNCS, pages 263–279. Springer.
Schmidt, J.-M., Tunstall, M., Avanzi, R., Kizhvatov, I., Kasper, T., and Oswald, D. (2010).
Combined implementation attack resistant exponentiation. In Progress in Cryptology– LATINCRYPT 2010, pages 305–322. Springer.
Stebila, D. and Thériault, N. (2006). Unified point addition formulæ and side-channel attacks. In Goubin, L. and Matsui, M., editors, Cryptographic Hardware and Embedded Systems CHES 2006, volume 4249 of LNCS, pages 354–368. Springer.
Sung-Ming, Y., Kim, S., Lim, S., and Moon, S. (2002). A countermeasure against one physical cryptanalysis may benefit another attack. In Kim, K., editor, Information Security and Cryptology—ICISC 2001, volume 2288 of LNCS, pages 414–427. Springer. Tanja, L. and Bernstein, D. J. (2014). Explicit-Formulas Database. https://www.hyperelliptic.org/EFD/bib.html.
Thériault, N. (2006). Spa resistant left-to-right integer recodings. In Preneel, B. and Tavares, S., editors, Selected Areas in Cryptography, volume 3897 of LNCS, pages 345–358. Springer.
Walter, C. (2004). Simple power analysis of unified code for ecc double and add. In Joye, M. and Quisquater, J.-J., editors, Cryptographic Hardware and Embedded Systems - CHES 2004, volume 3156 of LNCS, pages 191–204. Springer.
Yen, S.-M., Ko, L.-C., Moon, S., and Ha, J. (2006). Relative doubling attack against montgomery ladder. In Won, D. and Kim, S., editors, Information Security and Cryptology - ICISC 2005, volume 3935 of LNCS, pages 117–128. Springer.
Aciiçmez, O. and Koç, c. K. (2009). Microarchitectural Attacks and Countermeasures. In Cryptographic Engineering, chapter 18. Springer.
Amiel, F., Feix, B., Tunstall, M., Whelan, C., and Marnane, W. P. (2009). Distinguishing multiplications from squaring operations. In Selected Areas in Cryptography, pages 346–360. Springer.
Amiel, F., Villegas, K., Feix, B., and Marcel, L. (2007). Passive and active combined attacks: Combining fault attacks and side channel analysis. In Fault Diagnosis and Tolerance in Cryptography, 2007. FDTC 2007. Workshop on, pages 92–102.
Bernstein, D. and Lange, T. (2007). Inverted edwards coordinates. In Boztas¸, S. and Lu, H.-F., editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 4851 of LNCS, pages 20–27. Springer.
Bernstein, D. J., Birkner, P., Joye, M., Lange, T., and Peters, C. (2008). Twisted edwards curves. In Progress in Cryptology–AFRICACRYPT 2008, pages 389–405. Springer.
Brier, E., Dechene, I., and Joye, M. (2004). Unified Point Addition Formulae for Elliptic Curve Cryptosystems. In Embedded Cryptographic Hardware: Methodologies and Architectures, pages 247–256. Nova Science Publishers.
Brier, E. and Joye, M. (2002). Weierstrass Elliptic Curves and Side-Channel Attacks. In Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems, vol 2274, pages 335–345. Springer.
Certicom (2010). SEC 2: Recommended Elliptic Curve Domain Parameters, version 2.0. Technical report, Certicom Corp.
Chen, T., Li, H., Wu, K., and Yu, F. (2009). Countermeasure of ECC against Sidechannel Attacks: Balanced Point Addition and Point Doubling Operation Procedure. Asia-Pacific Conference on Information Processing.
Chevallier-Mames, B., Ciet, M., and Joye, M. (2004). Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. Computers, IEEE Transactions on, 53(6):760–768.
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., and Vercauteren, F. (2010). Handbook of elliptic and hyperelliptic curve cryptography. Chapman and Hall/CRC.
Coron, J.-S. (1999). Resistance against differential power analysis for elliptic curve cryptosystems. In Cryptographic Hardware and Embedded Systems, pages 292–302. Springer.
Edwards, H. (2007). A normal form for elliptic curves. Bulletin of the American Mathematical Society, 44(3):393–422.
Fischer, W. and Giraud, C. (2002). Parallel scalar multiplication on general elliptic curves IACR Cryptology over Fp hedged against Non-Differential Side-Channel Attacks. ePrint Archive.
Fouque, P.-A. and Valette, F. (2003). The doubling attack – why upwards is better than downwards. In Walter, C., Koç, e., and Paar, C., editors, Cryptographic Hardware and Embedded Systems CHES 2003, volume 2779 of LNCS, pages 269–280. Springer.
Gandolfi, K., Mourtel, C., and Olivier, F. (2001). Electromagnetic analysis: Concrete results. In Cryptographic Hardware and Embedded Systems CHES 2001, pages 251– 261. Springer.
Giraud, C. and Verneuil, V. (2010). Atomicity improvement for elliptic curve scalar multiplication. In Gollmann, D., Lanet, J.-L., and Iguchi-Cartigny, J., editors, Smart Card Research and Advanced Application, volume 6035 of LNCS, pages 80–101. Springer.
Goundar, R., Joye, M., Miyaji, A., Rivain, M., and Venelli, A. (2011). Scalar multiplication on Weierstraßelliptic curves from Co-Z arithmetic. Journal of Cryptographic Engineering, 1(2):161–176.
Hanley, N., Tunstall, M., and Marnane, W. (2011). Using templates to distinguish multiplications from squaring operations. International Journal of Information Security, 10(4):255–266.
Hisil, H., Wong, K. K.-H., Carter, G., and Dawson, E. (2008). Twisted Edwards curves revisited. In Advances in Cryptology-ASIACRYPT 2008, pages 326–343. Springer.
Izu, T. and Takagi, T. (2002a). A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. In Public Key Cryptography – PKC 2002, pages 280– 296.
Izu, T. and Takagi, T. (2002b). Exceptional procedure attack on elliptic curve cryptosystems. In Public Key Cryptography—PKC 2003, pages 224–239. Springer.
Joye, M. (2007). Highly regular right-to-left algorithms for scalar multiplication. In Cryptographic Hardware and Embedded Systems CHES 2007, pages 135–147. Springer.
Joye, M., Tibouchi, M., and Vergnaud, D. (2010). Huff’s model for elliptic curves. In Algorithmic Number Theory, pages 234–250. Springer.
Joye, M. and Yen, S.-M. (2003). The Montgomery powering ladder. In Cryptographic Hardware and Embedded Systems-CHES 2002, pages 291–302. Springer.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177):203–209.
Kocher, P. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Koblitz, N., editor, Advances in Cryptology CRYPTO ’96, volume 1109 of LNCS, pages 104–113. Springer Berlin / Heidelberg.
Kocher, P., Jaffe, J., and Jun, B. (1999). Differential Power Analysis. In Wiener, M., editor, Advances in Cryptology CRYPTO ’99, volume 1666 of LNCS, page 789. Springer Berlin / Heidelberg.
Longa, P. and Miri, A. (2008). Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields. In Computers, IEEE Transactions on, volume 57, pages 289–302.
Mangard, S., Oswald, E., and Popp, T. (2007). Power analysis attacks: Revealing the secrets of smart cards, volume 31. Springer.
Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Advances in Cryptology -CRYPTO Proceedings, pages 417–426. Springer.
Montgomery, P. L. (1987). Speeding the Pollard and elliptic curve methods of factorization. Mathematics of computation, 48(177):243–264.
NIST (2000). FIPS 186-2: Digital Signature Standard. Technical report, NIST.
Quisquater, J.-J. and Samyde, D. (2001). Electromagnetic analysis (ema): Measures and counter-measures for smart cards. In Smart Card Programming and Security, pages 200–210. Springer.
Schindler, W. (2002). A Combined Timing and Power Attack. In Naccache, D. and Paillier, P., editors, Public Key Cryptography SE 19, volume 2274 of LNCS, pages 263–279. Springer.
Schmidt, J.-M., Tunstall, M., Avanzi, R., Kizhvatov, I., Kasper, T., and Oswald, D. (2010).
Combined implementation attack resistant exponentiation. In Progress in Cryptology– LATINCRYPT 2010, pages 305–322. Springer.
Stebila, D. and Thériault, N. (2006). Unified point addition formulæ and side-channel attacks. In Goubin, L. and Matsui, M., editors, Cryptographic Hardware and Embedded Systems CHES 2006, volume 4249 of LNCS, pages 354–368. Springer.
Sung-Ming, Y., Kim, S., Lim, S., and Moon, S. (2002). A countermeasure against one physical cryptanalysis may benefit another attack. In Kim, K., editor, Information Security and Cryptology—ICISC 2001, volume 2288 of LNCS, pages 414–427. Springer. Tanja, L. and Bernstein, D. J. (2014). Explicit-Formulas Database. https://www.hyperelliptic.org/EFD/bib.html.
Thériault, N. (2006). Spa resistant left-to-right integer recodings. In Preneel, B. and Tavares, S., editors, Selected Areas in Cryptography, volume 3897 of LNCS, pages 345–358. Springer.
Walter, C. (2004). Simple power analysis of unified code for ecc double and add. In Joye, M. and Quisquater, J.-J., editors, Cryptographic Hardware and Embedded Systems - CHES 2004, volume 3156 of LNCS, pages 191–204. Springer.
Yen, S.-M., Ko, L.-C., Moon, S., and Ha, J. (2006). Relative doubling attack against montgomery ladder. In Won, D. and Kim, S., editors, Information Security and Cryptology - ICISC 2005, volume 3935 of LNCS, pages 117–128. Springer.
Publicado
03/11/2014
Como Citar
NASCIMENTO, Erick; ABARZÚA, Rodrigo; LÓPEZ, Julio; DAHAB, Ricardo.
A comparison of simple side-channel analysis countermeasures for variable-base elliptic curve scalar multiplication. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 14. , 2014, Belo Horizonte.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 125-138.
DOI: https://doi.org/10.5753/sbseg.2014.20126.
