Skip to main content

Advertisement

Springer Nature Link
Log in

Survey on performance and security problems of countermeasures for passive side-channel attacks on ECC

  • Regular Paper
  • Published:
Journal of Cryptographic Engineering Aims and scope Submit manuscript

Abstract

This paper presents an analysis on the state of the art of several proposals for algorithmic countermeasures to prevent passive side-channel attacks (SCA) on elliptic curve cryptography (ECC) defined over prime fields. One of the main applications of ECC is in the field of Internet of Things, where the interconnection of devices requires public-key technology with small key sizes and high security levels. Since the secure implementation of ECC on embedded devices involves many challenges for security and efficiency, this work evaluates the trade-offs between security and performance of side-channel attack countermeasures for scalar multiplication algorithms without precomputation. The main contribution is to present a panorama of explicit solutions that may be used for the implementation of ECC mechanisms suitable for embedded devices. In addition to the security problems, some countermeasures are also analyzed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. When \(m=2\) and the attacker knows whether \(y([2]P)+y(P)=0\), then, \(k_{n-2}=1\); otherwise, \(k_{n-2}=0\).

  2. We consider these ratios for our computing cost and \(S/M=0.8\).

  3. This experimental attack is applied because the implementation does not prevent irregular breaks between Atomic Blocks within the same group operation and distinct group operations.

  4. \(\mathcal {J}\), \(\mathcal {J}^c\) and \(\mathcal {J}^m\), respectively, refer to the Jacobian coordinates, Chudnovsky Jacobian coordinates and the modified Jacobian coordinates

References

  1. Abarzúa, R., Thériault, N.: Complete atomic blocks for elliptic curves in Jacobian coordinates over prime fields. In: Latincrypt 2012, LNCS, vol. 7533, Springer, pp. 7–55 (2012)

  2. Abarzúa, R., Martínez, S., Mendoza, V., Valera, J.: Avoiding side-channel attacks by computing isogenous and isomorphic elliptic curves. Math. Comput. Sci. 12, 295–307 (2008)

    Article  MathSciNet  Google Scholar 

  3. Akishita, T., Takagi, T.: Zero-value point attacks on elliptic curve cryptosystem. In: Information Security—ISC 2003, LNCS, vol. 2851, Springer, pp. 218–233 (2003)

  4. Akishita, T., Takagi, T.: On the optimal parameter choice for elliptic curve cryptosystems using isogeny. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 1, 140–146 (2005)

    Article  Google Scholar 

  5. Amiel, F., Feix, B., Tunstall, M., Whelan, C., Marnane, W.P.: Distinguishing multiplications from squaring operations. In: SAC 2008, LNCS, vol. 5381, Springer, pp. 346–360 (2008)

  6. Amiel, F., Villegas, K., Feix, B., Marcel, L.: Passive and active combined attacks. In: FDTC 2007, IEEE, pp. 92–99 (2007)

  7. Aranha, D.F., Fouque, P.A., Gérard, B.G., Kammerer, J.G., Tibouchi, M., Zapalowicz, J.C.: GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. In: ASIACRYPT 2014. LNCS, vol. 8873, Springer, Heidelberg, pp. 262–281 (2014)

  8. Avanzi, R.: Side channel attacks on implementations of curve-based cryptographic primitives. In: IACR Cryptology ePrint Archive. https://eprint.iacr.org/2005/017.pdf, pp. 1–27 (2005)

  9. Bajard, J.C., Imbert, L., Liardet, P.Y., Teglia, Y.: Leak resistant arithmetic. In: CHES 2004, LNCS vol. 3156, Springer, pp. 62–75 (2004)

  10. Batina, L., Chmielewski, L., Papachristodoulou, L., Schwabe, P., Tunstall, M.: Online template attacks. J. Cryptogr. Eng. 9, 21–36 (2019)

  11. Bauer, A., Jaulmes, E., Prouff, E., Reinhard, J.R., Wild, J.: Horizontal collision correlation attack on elliptic curves: extended version. Cryptogr. Commun. 7(1), 91–119 (2014)

    Article  MathSciNet  Google Scholar 

  12. Bauer, A., Jaulmes, E., Prouff, E., Wild, J.: Horizontal and vertical side-channel attacks against secure RSA implementations. In: CT-RSA 2013, LNCS, vol. 7779, Springer, pp. 1–17 (2013)

  13. Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: ASIACRYPT 2007, LNCS, vol. 4833, Springer, pp. 29–50 (2007)

  14. Bernstein, D.J., Birkner, P., Joye, M., Lange, L., Peters, C.: Twisted Edwards curves. In: AFRICACRYPT 2008, LNCS, vol. 5023, Springer, pp. 389–405 (2008)

  15. Bernstein, D.J., Lange, T.: Inverted Edwards coordinates. In: AAECC 2007, LNCS, vol. 4851, Springer, pp. 20–27 (2007)

  16. Bernstein, D.J., Lange, T.: Explicit-formulas database. http://www.hyperelliptic.org/EFD/ (2017)

  17. Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis. In: AAECC 2003, LNCS, vol. 2643, Springer, pp. 34–42 (2003)

  18. Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Selecting elliptic curves for cryptography: an efficiency and security analysis. J. Cryptogr. Eng. 6(4), 259–286 (2016)

    Article  Google Scholar 

  19. Brier, É., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: PKC 2002, LNCS, vol. 2274, Springer, pp. 335–345 (2002)

  20. Brier, É., Clavier, Ch., Olivier, F.: Correlation power analysis with a leakage model. In: CHES 2004, LNCS, vol. 3156, Springer, pp. 16–29 (2004)

  21. Brier, É., Dèchéne, I., Joye, M.: Unified point addition formulae for elliptic curve cryptosystems. In: Nova Science Publishers, chapter XIV, pp. 247–256 (2004)

  22. Brown, M., Hankerson, D., López, J., Menezes, A:. Software Implementation of the NIST elliptic curves over prime fields. In: CT-RSA 2001.LNCS, vol. 2020, Springer, Heidelberg, pp. 250–265 (2001)

  23. Brown, D.: Standards for efficient cryptography, sec 2: recommended elliptic curve domain parameters. http://www.secg.org/sec2-v2.pdf, Certicom Corp. Version 2.0, January (2010)

  24. Brumley, B.B., Tuveri, N.: Remote timing attacks are still practical. In: ESORICS 2011. LNCS, vol. 6879, Springer, Heidelberg, pp. 355–371 (2011)

  25. Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: CHES 2002, LNCS, vol. 2523, Springer, pp. 13–28 (2003)

  26. 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)

    Article  Google Scholar 

  27. Chevallier-Mames, B.: Self-randomized exponentiation algorithms. In: CT-RSA 2004, LNCS, vol. 2964, Springer-Verlag, pp. 236–249 (2004)

  28. Chen, T., Li, H., Wu, K., Yu, F.: Countermeasure of ECC against side-channel attacks: Balanced point addition and point doubling operation procedure. In: APCIP 2009, IEEE, pp. 465–469 (2009)

  29. Chmielewski, Ł., Massolino, P., Vliegen, J., Batina, L., Mentens, N.: Completing the complete ECC formulae with countermeasures. J. Low Power Electron. Appl. 7, 1 (2017)

    Article  Google Scholar 

  30. Ciet, M., Joye, M.: (Virtually) Free randomization techniques for elliptic curve cryptography. In: ICICS 2003, LNCS, vol. 2836, Springer-Verlag, pp. 348–359 (2003)

  31. Clavier, C., Joye, M.: Universal exponentation algorithm. In: CHES 2001, LNCS, vol. 2162, Springer, pp. 300–308 (2001)

  32. Clavier, Ch., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: ICICS 2010, LNCS, vol. 6476, Springer, pp. 46–61 (2010)

  33. Clavier, Ch., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Improved collision-correlation power analysis on first order protected AES. In: CHES 2011, LNCS, vol. 6917, Springer, pp. 49–62 (2011)

  34. Ch. Clavier, B. Feix, G. Gagnerot, Ch. Giraud, M. Roussellet and V. Verneuil, ROSETTA for single trace analysis. INDOCRYPT 2012, LNCS 7668, Springer-Verlag, pp. 140–155, (2012)

  35. Coron, J.S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: CHES 1999, LNCS, vol. 1717, Springer, pp. 292–302 (1999)

  36. Cohen, H., Frey, G., Avanzi, R., Doche, Ch., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, Boca Raton (2005)

    Book  Google Scholar 

  37. Cormen, T.H., Leiserson, ChE, Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, New York (2009)

    MATH  Google Scholar 

  38. Danger, J.L., Guilley, S., Hoogvorst, Ph., Murdica, C., Naccache, D.: Improving the big mac attack on elliptic curve cryptography. In: The New Codebreakers, LNCS, vol. 9100, Springer, pp. 374–386 (2016)

  39. Danger, J.-L., Guilley, S., Hoogvorst, Ph, Murdica, C., Naccache, D.: A synthesis of side-channel attacks on elliptic curve cryptography in smart-cards. J. Cryptogr. Eng. 3(4), 241–265 (2013)

    Article  Google Scholar 

  40. Das, P., Roy, D., Boyapally, H., Mukhopadhyay, D.: Inner collisions in ECC: Vulnerabilities of complete addition formulas for NIST curves. In: AsianHOST 2016, IEEE, pp. 1–6 (2017)

  41. Dubeuf, J., Hely, D., Beroulle, V.: ECDSA passive attacks, leakage sources, and common design mistakes. ACM Trans. Des. Autom. Electron. Syst. 21(2), 3101–3124 (2016)

    Article  Google Scholar 

  42. Dubeuf, J., Hely, D., Beroulle, V.,: Enhanced elliptic curve scalar multiplication against side channel and safe error. In: COSADE 2017, LNCS 10348, pp. 65–82, Springer (2017)

  43. Dugardin, M., Guilley, S., Danger, J.L., Najm, Z., Rioul, O.: Correlated extra-reductions defeat blinded regular exponentiation—extended version. Cryptology ePrint Archive, Report 2016/597 (2016)

  44. Dugardin, M., Papachristodoulou, L., Najm, Z., Batina, L., Danger, J.L., Guilley, S.:. Dismantling real-world ECC with horizontal and vertical template attacks. In: COSADE 2016, LNCS 9689, Springer, pp. 88–108 (2016)

  45. Duquesne, S.: Improving the arithmetic of elliptic curves in the Jacobi model. In: Information Processing Letters, vol. 104, no. 3, Elsevier, pp. 101–105 (2007)

  46. Ebeid, N.M.: Key randomization countermeasures to power analysis attacks on elliptic curve cryptosystems. University of Waterloo, Ph.D. Electrical and Computer Engineering (2007)

  47. Edwards-Curve Digital Signature Algorithm (EdDSA). Internet Research Task Force (IRTF), ISSN:2070-1721, https://tools.ietf.org/html/rfc8032, 2017

  48. Edwards, H.M.: A normal form for elliptic curves. Bull. Am. Math. Soc. 44(3), 393–422 (2007)

    Article  MathSciNet  Google Scholar 

  49. Elliptic Curves for Security. Internet Research Task Force (IRTF), ISSN: 20-70-1721, https://tools.ietf.org/html/rfc7748, 2016

  50. Fan, J., Verbauwhede, I.: An updated survey on secure ECC implementations: attacks, countermeasures and cost. In: Cryptography and Security: From Theory to Applications, LNCS, vol. 6805, Springer, 265–282 (2012)

  51. Fan, J., Guo, X., Mulder, E.D., Schaumont, P., Preneel, B., Verbauwhede, I.: State of the art of secure ECC implementations: a survey on known side-channel attacks and countermeasures. In: HOST 2010, IEEE, pp. 76–87 (2010)

  52. Farashahi, R., Joye, M.: Efficient arithmetic on Hessian curves. In: PKC 2010, LNCS, vol. 6056, Springer pp. 243–260 (2010)

  53. Feix, B., Roussellet, M., Venelli, A.: Side-channel analysis on blinded regular scalar multiplications. In: INDOCRYPT 2014, LNCS, vol. 8885, Springer, pp. 3–20 (2014)

  54. Fischer, W., Giraud, C., Knudsen, E.W., Seifert, J.P.: Parallel scalar multiplication on general elliptic curves over \(F_p\) hedged against non-differential side-channel attacks. https://eprint.iacr.org/2002/007.ps, Cryptology ePrint Archive, Report 2002/007 (2002)

  55. Fouque, P.A., Lercier, R., Réal, D., Valette, F.: Fault attack on elliptic curve with Montgomery ladder implementation. In: FDTC 2008, IEEE, pp. 92–98 (2008)

  56. Fouque, P.A., Valette, F.: The doubling attack why upwards is better than downwards. In: CHES 2003, LNCS, vol. 2779, Springer, pp. 269–280 (2003)

  57. Fouque, P.A., Réal, D., Valette, F., Drissi, M.: The carry leakage on the randomized exponent countermeasure. In: CHES 2009, LNCS, vol. 5154, Springer, pp. 198–213 (2008)

  58. Francq, J.: Conception et sécurisation d’unités arithmétiques hautes performances pour courbes elliptiques. Université Montpellier II, Ph.D thesis, Informatique (2010)

  59. Galbraith, S.: Constructing isogenies between elliptic curves over finite fields. J. Comput. Math. 2, 118–138 (1999)

    MathSciNet  MATH  Google Scholar 

  60. Gandolfi, K., Mourtel, Ch., Olivier, F.: Electronic analysis: concrete results. In: CHES 2001, LNCS, vol. 2162, Springer, pp. 251–261 (2001)

  61. Giraud, Ch., Verneuil, V.: Atomicity improvement for elliptic curve scalar multiplication. In: CARDIS 2010, LNCS, vol. 6035, Springer-Verlag, pp. 80–101 (2010)

  62. Giry, D., Quinsquater, J.J.: Bluekrypt cryptographic key length recommendation. http://www.keylength.com/. Accessed on 2017 (2011)

  63. Giry, D.: Bluekrypt, cryptographic key length recommendation. https://www.keylength.com/. Accessed 28 June 2018 (2017)

  64. Goubin, L.: A refined power-analysis attack on elliptic curve cryptosystems. In: PKC 2003, LNCS, vol. 2567, Springer, pp. 199–211 (2002)

  65. Goundar, R.R., Joye, M., Miyaji, A., Rivain, M., Venelli, A.: Scalar multiplication on Weierstraß elliptic curves from Co-Z arithmetic. J. Cryptogr. Eng. 1(2), 161–176 (2011)

    Article  Google Scholar 

  66. Ha, J., Park, J., Moon, S., Yen, S.: Provably secure countermeasure resistant to several types if power attack for ECC. In: WISA 2007, LNCS, vol. 4867, Springer, pp. 333–344 (2007)

  67. Hamburg, M.: Faster Montgomery and double-add ladders for short Weierstrass curves. In: IACR Transactions on Cryptographic Hardware and Embedded Systems, ISSN 2569-2925, vol. 2020, no. 4, pp. 189–208 (2020)

  68. Hanley, N., Tunstall, M., Marnane, W.P.: Using templates to distinguish multiplications from squaring operations. Int. J. Inf. Secur. 10(4), 255–266 (2011)

    Article  Google Scholar 

  69. Hanley, N., Kim, H.S., Tunstall, M.: Exploiting collisions in addition chain-based exponentiation algorithms using a single trace. In: CT-RSA 2015, LNCS, vol. 9048, pp. 431–448, Springer (2015)

  70. Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004)

    MATH  Google Scholar 

  71. Heyszl, J., Mangard, S., Heinz, B., Stumpf, F., Sigl, G.: Localized electromagnetic analysis of cryptographic implementations. In: CT-RSA 2012, LNCS, vol. 7178, Springer, pp. 231–244 (2012)

  72. Heyszl, J., Merli, D., Heinz, B., De Santis, F., Sigl, G.: Strengths and limitations of high-resolution electromagnetic field measurements for side-channel analysis. In: CARDIS 2012, LNCS, vol. 7771, Springer, pp. 248–262 (2013)

  73. Hisil, H., Carter, G., Dawson, E.: New formulae for efficient elliptic curve arithmetic. In: INDOCRYPT 2007, LNCS, vol. 4859, Springer, pp. 138–151 (2007)

  74. Hisil, H., Wong, K.K.H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: ASIACRYPT 2008, LNCS, vol. 5350, Springer, pp. 326–343 (2008)

  75. Hisil, H., Wong, K.K-H., Carter, G., Dawson, E.: Jacobi quartic curves revisited. In: ACISP 2009, LNCS, vol. 5594, Springer, pp. 452–468 (2009)

  76. Itoh, K., Izu, T., Takenaka, M.: A practical countermeasure against address-bit differential power analysis. In: CHES 2003, LNCS, vol. 2779, Springer, pp. 382–396 (2003)

  77. Itoh, K., Izu, T., Takenaka, M.: Address-bit differential power analysis of cryptographic schemes OK-ECDH and OK-ECDSA. In: CHES 2002, LNCS, vol. 2523, Springer, pp. 129–143 (2003)

  78. Itoh, K., Izu, T., Takenaka, M.: Efficient countermeasures against power analysis for elliptic curve cryptosystems. In: CARDIS 2004, IFIPAICT 153, Springer, pp. 99–113 (2004)

  79. Izu, T., Takagi, T.: Exceptional procedure attack on elliptic curve cryptosystems. In: PKC 2003, LNCS, vol. 2567, Springer, pp. 224–239 (2003)

  80. Izumi, M., Ikegami, J., Sakiyama, K., Ohta, K.: Improved countermeasure against Address-bit DPA for ECC scalar multiplication. In: DATE 2010, IEEE, pp. 981–984 (2010)

  81. Izu, T., Takagi, T.: A fast parallel elliptic curve multiplication resistant against side channel attacks. In: PKC 2002, LNCS, vol. 2274, Springer, pp. 280–296 (2002)

  82. Jing, Q., Vasilakos, A.V., Wan, J., Lu, J., Qiu, D.: Security of the internet of things: perspectives and challenges. Wirel. Netw. 20(8), 2481–2501 (2014)

    Article  Google Scholar 

  83. Joye,M., Tymen, Ch.: Protections against differential analysis for elliptic curve cryptography. In: CHES 2001, LNCS, vol. 2162, Springer pp. 377–390 (2001)

  84. Joye, M., Tibouchi, M., Vergnaud, D.: Huff’s model for elliptic curves. In: ANTS 2010, LNCS, vol. 6197, Springer, pp. 234–250 (2010)

  85. Joye, M.: Highly regular right-to-left algorithms for scalar multiplication. In: CHES 2007, LNCS, 4727, Springer, pp. 135–147 (2007)

  86. Joye, M., Quisquater, J.J.: Hessian elliptic curves and side-channel attacks. In: CHES 2001, LNCS, vol. 2162, Springer, pp. 402–410 (2001)

  87. Joye, M., Yen, S.M.: The montgomery powering ladder. In: CHES 2002, LNCS, vol. 2523, Springer, pp. 291–302 (2003)

  88. Kim, C.K., Ha, J.C., Moon, S.J., Yen, S.M., Lien, W.Ch., Kim, S.H.: An improved and efficient countermeasure against power analysis attacks. https://eprint.iacr.org/2005/022.pdf, IACR Cryptology ePrint Archive (2005)

  89. Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)

  90. Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)

    Article  MathSciNet  Google Scholar 

  91. Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: CRYPTO 1999, LNCS, vol. 1666, Springer, pp. 388–397 (1999)

  92. Kocher, P.: Timing attacks on implementation of Diffie-Hellman RSA, DSS and other systems. In: CRYPTO 1996, LNCS, vol. 1109, Springer, pp. 104–113 (1996)

  93. Koç, Ç.K.: Cryptographic Engineering. Springer, Berlin (2009)

    Book  Google Scholar 

  94. Le, D.P., Tan, C.H., Tunstall, M.: Randomizing the montgomery powering ladder. In: IFIP 2015, LNCS, vol. 9311, Springer, pp. 169–184 (2015)

  95. Liardet, P.Y., Smart, N.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: CHES 2001, LNCS, vol. 2162, Springer, pp. 391–401 (2001)

  96. Liu, Z., Liu, D., Sun, X., Zou, X., Lin, X.: Implementation of a resource-constrained ECC processor with power analysis countermeasure. In: APCCAS 2016, Springer, pp. 206–209 (2017)

  97. Longa, P., Miri, A.: Fast and flexible elliptic curve point arithmetic over prime fields. IEEE Trans. Comput. 57(3), 289–302 (2008)

    Article  MathSciNet  Google Scholar 

  98. López, J., Dahab, R.: Fast multiplication on elliptic curves over GF(2m) without precomputation. In: CHES 1999, LNCS, vol. 1717, Springer, pp. 316–327 (1999)

  99. Mamiya, H., Miyaji, A., Morimoto, H.: Secure elliptic curve exponentiation against RPA, ZRA, DPA, and SPA. In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E89-A, 8, pp. 2207–2215 (2006)

  100. Mamiya, H., Miyaji, A., Morimoto, H.: Efficient countermeasures against RPA, DPA, and SPA. In: CHES 2004, LNCS, vol. 3156, Springer, pp. 343–356 (2004)

  101. Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer, Berlin (2007)

    MATH  Google Scholar 

  102. Miller, V.: Use of elliptic curves in cryptography. In: CRYPTO 1985, LNCS, vol. 218, Springer, pp. 417–426 (1985)

  103. Miret, J., Sadornil, D., Tena, J., Tomàs, R., Valls, M.: On avoiding ZVP-attacks using isogeny volcanoes. In: WISA 2008, LNCS, vol. 5379, Springer, pp. 266–277 (2009)

  104. Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)

    Article  MathSciNet  Google Scholar 

  105. Möller, B.: Securing elliptic curve point multiplication against side-channel attacks. In: ISC 2001, LNCS, vol. 2200, Springer, pp. 324–334 (2001)

  106. Muller, F., Valette, F.: High-order attacks against the exponent splitting protection. In: PKC 2006, LNCS, vol. 3958, Springer, pp. 315–329 (2006)

  107. Murdica, C., Guilley, S., Danger, J.L., Hoogvorst, Ph., Naccache, D.: Same values power analysis using special points on elliptic curves. In: COSADE 2012, LNCS, vol. 7275, Springer, pp. 183–198 (2012)

  108. Murdica, C.: Physical security of elliptic curve cryptography. Telecom ParisTech. https://pastel.archives-ouvertes.fr/tel-01179584/document (2014)

  109. Naccache, D., Smart, N., Stern, J.: Projective coordinates leak. In: EUROCRYPT 2004, LNCS, vol. 3027, Springer, pp. 257–267 (2004)

  110. Nascimento, E., Abarzúa, R., López, J., Dahab, R.: A comparison of simple side-channel analysis countermeasures for variable-base elliptic curve scalar multiplication. XIV Simposio Brasilerio em Seguranca da Informacao de Sistemas Computacionais, SBseg 2014, 125–138 (2014)

  111. Nascimento, E., Chmielewski, L., Oswald, D., Schwabe, P.: Attacking embedded ECC implementations through cmov side channels. In: SAC 2016, LNCS, vol. 10532, Springer, pp. 99–119 (2017)

  112. Nguyen, P.Q., Shparlinski, I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)

    Article  MathSciNet  Google Scholar 

  113. NIST, FIPS 186-3: Digital signature standard (DSS), National institute of standards and Technology NIST. https://csrc.nist.gov/publications/detail/fips/186/3/archive/2009-06-25. Accessed 28 June 2018 (2009)

  114. Okeya, K., Sakurai, K.: Power analysis breaks elliptic curve cryptosystems even secure against the timing attack. In: INDOCRYPT 2000, LNCS, vol. 1977, Springer, pp. 178–190 (2000)

  115. Özgen, E., Papachristodoulou, L., Batina, L.: Template attacks using classification algorithms. HOST 2016, 242–247 (2016)

    Google Scholar 

  116. Perin, G., Imbert, L., Torres, L., Maurine, Ph.: Attacking randomized exponentiations using unsupervised learning. In: COSADE 2014, LNCS, vol. 8622, Springer, pp. 144–160 (2014)

  117. Popp, T., Mangard, S., Oswald, E.: Power analysis attacks and countermeasures. IEEE Des. Test Comput. 24(6), 535–543 (2007)

  118. Prouff, E., Rivain, M.: Theoretical and practical aspects of mutual information based side channel analysis. In: ACNS 2009, LNCS, vol. 5536, Springer, pp. 499–518 (2009)

  119. Quisquater, J.J., Samyde, D.: Electromagnetic analysis (EMA): Measures and countermeasures for smart cards. In: Smart Card Programming and Security—E-SMART 2001, LNCS, vol. 2140, Springer, pp. 200–210 (2001)

  120. Renes, J., Costello, C., Batina, L.: Complete addition formulas for prime order elliptic curves. In: EUROCRYPT 2016, LNCS, vol. 9665, Springer, pp. 403–428 (2016)

  121. Research center for information security, Side-channel attack standard evaluation board (SASEBO). http://satoh.cs.uec.ac.jp/SASEBO/en/board/index.html. Accessed January 2018 (2016)

  122. Sato, H., Schepers, D., Takagi, T.: Exact analysis of Montgomery multiplication. In: INDOCRYPT 2004, LNCS, vol. 3348, Springer, pp. 290–304 (2004)

  123. Schramm, K., Wollinger, Th., Paar, Ch.: A new class of collision attacks and its application to DES. In: FSE 2003, LNCS, vol. 2887, Springer, pp. 206–222 (2003)

  124. Schindler, W.: A timing attack against RSA with the chinese remainder theorem. In: Cryptographic hardware and embedded systems—CHES 2000, LNCS 1965, Springer, pp 109–124 (2000)

  125. Schmidt, J.M., Tunstall, M., Avanzi, R., Kizhvatov, I., Kasper, T., Oswald, D.: Combined implementation attack resistant exponentiation. In: LATINCRYPT 2010, LNCS, vol. 6212, Springer, pp. 305–322 (2010)

  126. Smart, N.: An analysis of Goubin’s refined power analysis attack. In: CHES 2003, LNCS, vol. 2779, Springer, pp. 281–290 (2003)

  127. Smart, N.: The Hessian form of an elliptic curve. In: CHES 2001, LNCS, vol. 2162, Springer, pp. 118–125 (2001)

  128. Smart, N., Oswald, E., Page, D.: Randomised representations. IET Inf. Secur. 2(2), 19–27 (2008)

    Article  Google Scholar 

  129. Specht, R., Heyszl, J., Kleinsteuber, M., Sigl, G.: Improving non-profiled attacks on exponentiations based on clustering and extracting leakage from multi-channel high-resolution EM measurements. In: COSADE 2015, LNCS, vol. 9064, Springer, pp. 3–19 (2015)

  130. Stebila, D., Thériault, N.: Unified point addition formulæ and side-channel attacks. In: CHES 2006, LNCS, vol. 4249, Springer, pp. 354–368 (2006)

  131. Strobel, D., Oswald, D., Richter, B., Schellenberg, F., Paar, Ch.: Microcontrollers as in security devices for pervasive computing applications. Proc. IEEE 102(8), 1157–1173 (2014)

    Article  Google Scholar 

  132. Standaert, F.X., Gierlichs, B., Verbauwhede, I.: Partition vs. comparison side-channel distinguishers: an empirical evaluation of statistical tests for univariate side-channel attacks against two unprotected CMOS devices. In: ICISC 2008, LNCS, vol. 5461, Springer, pp. 253–267 (2009)

  133. Strauss, E.G.: Addition chains of vectors (problem 5125). Am. Math. Mon. 70, 806–808 (1964)

    Google Scholar 

  134. Thériault, N.: SPA resistant left-to-right integer recoding. In: SAC 2005, LNCS, vol. 3897, Springer, pp. 345–358 (2005)

  135. Trichina, E., Belleza, A.: Implementation of elliptic curve cryptography with built-in counter measures against side channel attacks. In: CHES–2002, LNCS, vol. 2523, Springer, pp. 98–113 (2002)

  136. Tunstall, M., Joye, M.: Coordinate blinding over large prime fields. In: CHES 2010, LNCS, vol. 6225, Springer, pp. 443–455 (2010)

  137. Vélu, J.: Isogénies entre courbes elliptiques. C. R. Acad.Sci. Paris, Ser. I Math. Ser. A. 273, 238–241 (1971)

  138. Venelli, A.: Contribution à la sécurité physique des cryptosystèmes embarqués. Université Aix-Marseille, Thèse Docteur de Informatique (2011)

  139. Verneuil, V.: Cryptographie à base de courbes elliptiques et sécurité de composants embarqués. Université de Bordeaux, Thèse École Doctorale de Mathématiques et Informatique (2012)

  140. Walter, C.D.: Sliding windows succumbs to big mac attack. In: CHES 2001, LNCS, vol. 2162, Springer, pp. 286–299 (2001)

  141. Walter, C.D.: Simple power analysis of unified code for ECC double and add. In: CHES-2004, LNCS, vol. 3156, Springer-Verlag, pp. 191–204 (2004)

  142. Walter, C., Thompson, S.: Distinguishing exponent digits by observing modular subtractions. In: Topics in Cryptology—CT-RSA 2001, LNCS 2020, Springer, pp. 192–207 (2001)

  143. Wang, L., Li, Q., Zhang, G., Yu, J., Zhang, Z., Guo, L., Zhang, D.: A new SPA attack on ECC with regular point multiplication. In: CIS 2015, IEEE, pp. 322–325 (2016)

  144. Washington, L.C.: Elliptic Curves Number Theory and Cryptography. Discrete Mathematics Series. Chapman and Hall/CRC, Boca Raton (2008)

    MATH  Google Scholar 

  145. Wenger, E., Großschädl, J.: An 8-bit AVR-based elliptic curve cryptographic RISC processor for the internet of things. In: MICROW 2012, IEEE, pp. 39–46 (2012)

  146. Yen, S.M., Ko, L.S., Moon, S.J., Ha, J.C.: Relative doubling attack against Montgomery ladder. In: ICISC 2005, LNCS, vol. 3935, Springer, pp. 117–128 (2006)

  147. Yen, S.M., Lien, W.C., Moon, S.J., Ha, J.C.: Power analysis by exploiting chosen message and internal collisions vulnerability of checking mechanism for RSA-decryption. In: Mycrypt 2005, LNCS, vol. 3715, Springer, pp. 183–195 (2005)

  148. Yen, S.-M., Joye, M.: Checking before output may not be enough against fault-based cryptanalysis. IEEE Trans. Comput. 49(9), 967–970 (2000)

    Article  Google Scholar 

  149. S-M. Yen, S. Kim, S. Lim and S-J. Moon, A Countermeasure against one physical cryptanalysis may benefit another attack. ICISC 2001, Springer, LNCS 2288, pp. 269–294, (2002)

Download references

Acknowledgements

The authors are grateful for the financial support given by Universidad de Santiago de Chile, USACH, through DICYT projects 062033AO, 061513VC (Universidad de Santiago de Chile, Chile), STICAMSUD 19-STIC-02 and STIC-AmSud/CAPES program 88881-198035/2018-01/CAPES (Brazil).

Author information

Authors and Affiliations

  1. Departamento de Matemática y Ciencia de la Computación, Universidad de Santiago de Chile, Santiago, Chile

    Rodrigo Abarzúa

  2. Departamento de Ingeniería Eléctrica, Universidad de Santiago de Chile, Santiago, Chile

    Claudio Valencia

  3. Instituto de Computação, Universidade Estadual de Campinas, Campinas, Brazil

    Julio López

Authors
  1. Rodrigo Abarzúa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Claudio Valencia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Julio López
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rodrigo Abarzúa.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This research was supported by the following research grants: DICYT projects 062033AO, 061513VC (Universidad de Santiago de Chile, Chile), STICAMSUD 19-STIC-02 and STIC-AmSud/CAPES program 88881-198035/2018-01/CAPES (Brazil).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Abarzúa, R., Valencia, C. & López, J. Survey on performance and security problems of countermeasures for passive side-channel attacks on ECC. J Cryptogr Eng 11, 71–102 (2021). https://doi.org/10.1007/s13389-021-00257-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13389-021-00257-8

Keywords

Search

Navigation