Top

Journal of Cryptographic Engineering

Published in:

26-03-2019 | Regular Paper

Same value analysis on Edwards curves

Authors: Rodrigo Abarzúa, Santi Martínez, Valeria Mendoza, Nicolas Thériault

Published in: Journal of Cryptographic Engineering | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recently, several research groups in cryptography have presented new elliptic curve models based on Edwards curves. These new curves were selected for their good performance and security perspectives. Cryptosystems based on elliptic curves in embedded devices can be vulnerable to side-channel attacks (SCA), such as simple power analysis (SPA) or differential power analysis. In this paper, we analyze the existence of special points—whose use in SCA is known as same value analysis (SVA)—in the case of Edwards elliptic curves. These special points can be identified through a power analysis of the scalar multiplication. We show that all Edwards curves recently proposed for standardization contain some of these points and are therefore unsafe against SVA. As a countermeasure, we use the isogeny volcano approach to find SVA-secure isogenous curves to those proposed for standardization.

previous article Improved parallel mask refreshing algorithms: generic solutions with parametrized non-interference and automated optimizations

next article How to reveal the secrets of an obscure white-box implementation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

In [23], Ebeid studied implementations of this countermeasure using the Shamir-Strauss method [52] and found a vulnerability which can be attacked by via a differential power analysis (DPA) (Lemma 6.1). As a result of this study, it is recommended that each term of \([k-r]P\) and [r]P should be computed separately using a SPA-resistant algorithm.

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

Akishita, T., Takagi, T.: On the optimal parameter choice for elliptic curve cryptosystems using isogeny. In: Public Key Cryptography—PKC 2004, LNCS, vol. 2947, pp. 346–359. Springer (2004)

Aranha, D., Barreto, P., Pereira, G., Ricardini, J.: A note on high-security general-purpose elliptic curves. IARC Cryptology ePrint Archive, report 2013/647 (2013)

Avanzi, R.: Side channel attacks on implementations of curve-based cryptographic primites. IACR Cryptology ePrint Archive, report 2005/017 (2005)

Bauer, A., Jaulmes, E., Prouff, E., Wild, J.: Horizontal collision correlation attack on elliptic curves. In: SAC 2013, LNCS, vol. 8282, pp. 553–570. Springer (2014)

Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records. In: Public Key Cryptography—PKC 2006, LNCS, vol. 3958, pp. 207–228. Springer (2006)

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

Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. IACR Cryptology ePrint Archive, report 2013/325 (2013)

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

10.

Bernstein, D.J., Lange, T.: Explicit formula database. http://www.hyperelliptic.org/EFD/

11.

Bernstein, D.J., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography. http://safecurves.cr.yp.to/

12.

Bogdanov, A.: Improved side-channel collision attacks on AES. In: SAC 2007, LNCS, vol. 4876, pp. 84–95. Springer (2007)

13.

Bogdanov, A.: Multiple-differential side-channel collision attacks on AES. In: CHES 2008, LNCS, vol. 5154, pp. 30–44. Springer (2008)

14.

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)CrossRef

15.

Chari, S., Rao, J.R., Rohati, P.: Template attacks. In: Cryptographic Hardware and Embedded Systems—CHES 2002, LNCS, vol. 2523, pp. 13–28. Springer (2003)

16.

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

17.

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

18.

Ciet, M., Joye, M.: (Virtually) free randomization techniques for elliptic curve cryptography. In: Information and Communications Security—ICICS 2003, LNCS, vol. 2836, pp. 348–359. Springer (2003)

19.

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

20.

Clavier, C., Joye, M.: Universal exponentiation algorithm. In: Cryptographic Hardware and Embedded Systems—CHES 2001, LNCS, vol. 2162, pp. 300–308. Springer (2001)

21.

Coron, J.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Cryptographic Hardware and Embedded Systems—CHES 1999, LNCS, vol. 1717, pp. 392–302. Springer (1999)

22.

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

23.

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

24.

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

25.

Feix, B., Verneuil, V.: There’s something about m-ary, protected against physical attacks. In: Progress in Cryptology—INDOCRYPT 2013, LNCS, vol. 8250, pp. 197–214. Springer (2013)

26.

Gandolfi, K., Mourtel, C., Olivier, F.: Electronic analysis: concrete results. In: Cryptographic Hardware and Embedded Systems—CHES 2001, LNCS, vol. 2162, pp. 251–261. Springer (2001)

27.

Giry, D., Quinsquater, J.-J.: Bluekrypt cryptographic key length. Recommendation 2011, v26.0, April 18. http://www.keylength.com/ (2011)

28.

Goubin, L.: A refined power-analysis attack on elliptic curve cryptosystems. In: Public Key Cryptography—PKC 2003, LNCS, vol. 2567, pp. 199–210. Springer (2003)

29.

Hamburg, M.: Ed448-goldilocks, fast, strong elliptic curve cryptography. http://ed448goldilocks.sourceforge.net/

30.

Josefson, S., Liusvaara, I.: Edwards-curve digital signature algorithm (EdDSA). Internet Research Task Force memo. https://tools.ietf.org/html/rfc8032 (2017)

31.

Joye, M.: Highly regular right-to-left algorithms for scalar multiplication. In: Cryptographic Hardware and Embedded Systems—CHES 2007, LNCS, vol. 4727, pp. 135–147. Springer (2007)

32.

Joye, M., Tymen, C.: Protections against differential analysis for elliptic curve cryptography. In: Cryptographic Hardware and Embedded Systems—CHES 2001, LNCS, vol. 2162, pp. 377–390. Springer (2001)

33.

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

34.

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

35.

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

36.

Langley, A., Hamburg, M., Turner, S.: Elliptic curves for security. Internet Research Task Force memo. https://tools.ietf.org/html/rfc7748 (2016)

37.

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

38.

Martínes, S., Sadornil, D., Tena, J., Tomàs, R., Valls, M.: On Edwards curves and ZVP-attacks. Appl. Algebra Eng. Commun. Comput. 24, 507–517 (2013)MathSciNetCrossRef

39.

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

40.

Miret, J., Sadornil, D., Tena, J., Tomàs, R., Valls, M.: Isogeny cordillera algorithm to obtain cryptographically good elliptic curves. In: Australasian Information Security Workshop: Privacy Enhancing Technologies (AISW), vol. 68, pp. 127–131 (2007)

41.

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

42.

Moradi, A., Mischke, O., Eisenbarth, T.: Correlation-enhanced power analysis collision attack. In: CHES 2010, LNCS, vol. 6225, pp. 125–139. Springer (2010)

43.

Murdica, C., Guilley, S., Danger, J.-L., Hoogvourst, P., Naccache, D.: Same value power analysis using special point on elliptic curves. In: Constructive Side-Channel Analysis and Secure Design—COSADE 2012, LNCS, vol. 7275, pp. 183–198. Springer (2012)

44.

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

45.

Nascimento, E., Chmielewski, L., Oswald, D., Schwabe, P.: Attacking embedded ECC implementations through CMOV side channels. IARC Cryptology ePrint Archive, report 2016/923 (2016)

46.

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

47.

Schramm, K., Leander, G., Felke, P., Paar, C.: A collision-attack on AES: combining side channel- and differential-attack. In: CHES 2004, LNCS, vol. 3156, pp. 163–175. Springer (2004)

48.

Schramm, K., Wollinger, T., Paar, C.: A new class of collision attacks and its application to DES. In: Fast Software Encryption—FSE 2003. LNCS, vol. 2887, pp. 206–222. Springer (2003)

49.

Smart, N.: An analysis of Goubin’s refined power analysis attack. In: Cryptographic Hardware and Embedded Systems— CHES 2003, LNCS, vol. 2779, pp. 281–290. Springer (2003)

50.

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

51.

Standards for efficient cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters. Certicom Corp. Version 2.0, January 2010

52.

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

53.

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

54.

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

55.

Tunstall, M., Joye, M.: Coordinate blinding over large prime fields. In: Cryptographic Hardware and Embedded Systems—CHES 2010, LNCS, vol. 6225, pp. 443–445. Springer (2010)

56.

Witteman, M.F., van Woudenberg, J.G.J., Menarini, F.: Defeating RSA multiply-always and message blinding countermeasures. In: CT-RSA 2011, LNCS, vol. 6558, pp. 77–88. Springer (2011)

Title: Same value analysis on Edwards curves
Authors: Rodrigo Abarzúa
Santi Martínez
Valeria Mendoza
Nicolas Thériault
Publication date: 26-03-2019
Publisher: Springer Berlin Heidelberg
Published in: Journal of Cryptographic Engineering / Issue 1/2020
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-019-00206-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2020

On the feasibility of deriving cryptographic keys from MEMS sensors

Improving side-channel attacks against pairing-based cryptography

How to reveal the secrets of an obscure white-box implementation

Deep learning mitigates but does not annihilate the need of aligned traces and a generalized ResNet model for side-channel attacks

Improved parallel mask refreshing algorithms: generic solutions with parametrized non-interference and automated optimizations

Premium Partner