nach oben

Cryptography and Communications

Erschienen in:

01.03.2015

Horizontal collision correlation attack on elliptic curves

– Extended Version –

verfasst von: Aurélie Bauer, Eliane Jaulmes, Emmanuel Prouff, Jean-René Reinhard, Justine Wild

Erschienen in: Cryptography and Communications | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Elliptic curves based algorithms are nowadays widely spread among embedded systems. They indeed have the double advantage of providing efficient implementations with short certificates and of being relatively easy to secure against side-channel attacks. As a matter of fact, when an algorithm with constant execution flow is implemented together with randomization techniques, the obtained design usually thwarts classical side-channel attacks while keeping good performances. Recently, a new technique that makes randomization ineffective, has been successfully applied in the context of RSA implementations. This method, related to a so-called horizontal modus operandi, introduced by Walter in 2001, turns out to be very powerful since it only requires leakages on a single algorithm execution. In this paper, we combine such kind of techniques together with the collision correlation analysis, introduced at CHES 2010 by Moradi et al., to propose a new attack on elliptic curves atomic implementations (or unified formulas) with input randomization. We show how it may be applied against several state-of-the art implementations, including those of Chevallier-Mames et al., of Longa and of Giraud-Verneuil and also Bernstein and Lange for unified Edward’s formulas. Finally, we provide simulation results for several sizes of elliptic curves on different hardware architectures. These results, which turn out to be the very first horizontal attacks on elliptic curves, open new perspectives in securing such implementations. Indeed, this paper shows that two of the main existing countermeasures for elliptic curve implementations become irrelevant when going from vertical to horizontal analysis.

Vorheriger Artikel The distributions of individual bits in the output of multiplicative operations

Nächster Artikel Complete reverse-engineering of AES-like block ciphers by SCARE and FIRE attacks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

Among the unified formulas, we especially focus on the Edward’s ones in [9] introduced by Bernstein and Lange since they lead to efficient doubling and addition computations compared to the Weierstrass case [16].

We shall sometimes need to consider the known value as a pair of variables: in this case we will use the notation (X,Y) instead of X.

In contexts where the adversary is not allowed to choose the algorithm input but knows it, the first step just aims at fixing the input value for the rest of the attack.

Possibly, the observations acquisition phase may mix horizontal and vertical techniques. In this case, the attack will be termed Rectangle.

For readability reasons we do not recall the full patterns but the interested reader can find them in [17].

Guidelines are given in [17] to define the dummy operations in a pertinent way.

We also performed experiments with the correlation defined in (9) and observed that the attacks were always less efficient than with the correlation in (10), which is in line with the analysis conducted in Section 4.4

In this context, the SNR simply equals ω/4σ ².

Contrary to the attacks described in Section 4, the attack against Algorithms 2 and 3 does not try to detect two similar operations with a common operand but tries to detect when a same operand is manipulated two times. Even if this scenario is not exactly the one analyzed in this paper, we think that the corresponding attack stays efficient as it is based on the same principles.

For instance, if L is related to the manipulation of two shares M ₁ and M ₂ of O, then one can for instance assume that half of the V _i corresponds to M ₁ and the other half to M ₂. Moreover, (2) is a particular case of (11) where all manipulated data are assumed to be equal to O.

If t is odd, it can be right-padded with a zero.

Karatsuba, A., Ofman, Y. (eds.): Multiplication of Many-Digital Numbers by Automatic Computers, vol. 145 (1962)

ANSI X9.62: Public Key Cryptography for the Financial Service Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). American National Standards Institute (1998)

ANSI X9.63: Public Key Cryptography for the Financial Service Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. American National Standards Institute (1998)

Baek, Y.-J., Vasyltsov, I.: How to Prevent DPA and Fault Attack in a Unified Way for ECC Scalar Multiplication - Ring Extension Method In:. ISPEC, pp. 225–237 (2007)

Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Proceedings on Advances in Cryptology—CRYPTO ’86, pp 311–323. Springer-Verlag, London (1987)

Batina, L., Gierlichs, B., Prouff, E., Rivain, M., Standaert, F.-X., Veyrat-Charvillon, N.: Mutual information analysis: a comprehensive study. J. Cryptol. 24(2), 269–291 (2011)CrossRefMATHMathSciNet

Bauer, A., Jaulmes, E., Prouff, E., Wild, J.: Horizontal and vertical side-channel attacks against secure RSA implementations. In: Dawson, E. (ed.) Topics in Cryptology — CT-RSA 2013, volume 7779 of Lecture Notes in Computer Science, pp. 1–17. Springer (2013)

Bauer, A., Jaulmes, E., Prouff, E., Wild, J.: Horizontal collision correlation attack on elliptic curves. In: Lange, T., Lauter, K.E., Lisonek, P. (eds.) Selected Areas in Cryptography, volume 8282 of Lecture Notes in Computer Science, pp. 553–570. Springer (2013)

Bernstein, D.J., Lange, T.: Analysis and Optimization of Elliptic-Curve Single-Scalar Multiplication. Cryptology ePrint Archive, Report 2007/455, (2007) http://eprint.iacr.org/

10.

Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) Advances in Cryptology — Proceedings of ASI-ACRYPT 2007, volume 4833 of Lecture Notes in Computer Science, pp. 29–50. Springer (2007)

11.

Billet, O., Joye, M.: The Jacobi Model of an Elliptic Curve and Side-Channel Analysis. Cryptology ePrint Archive, Report 2002/125 (2002)

12.

Bogdanov, A., Kizhvatov, I., Pyshkin, A.: Algebraic methods in side-channel collision attacks and practical collision detection. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) Progress in Cryptology – INDOCRYPT 2008, volume 5365 of LNCS, pp. 251–265. Springer-Verlag (2008)

13.

Booth, A.: A signed binary multiplication technique. Q. J. Mech. Appl. Math. 4(2), 236–240 (1951)CrossRefMATHMathSciNet

14.

Brickell, E.F.: A survey of hardware implementation of RSA (Abstract). In: CRYPTO, volume 435 of Lecture Notes in Computer Science, pp. 368–370. Springer (1989)

15.

Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.-J. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2004, volume 3156 of Lecture Notes in Computer Science, pp. 16–29. Springer (2004)

16.

Brier, É., Joye, M.: Weierstraß elliptic curves and side-channel attacks In: Naccache, D., Paillier, P. (eds.) Public Key Cryptography – PKC 2002, volume 2274 of Lecture Notes in Computer Science, pp. 335–345. Springer (2002 )

17.

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

18.

Ciet, M., Joye, M.: Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Faults. Cryptology ePrint archive, report 2003/028 (2003)

19.

Clavier, C., Feix, B., Gagnerot, G., Giraud, C., Roussellet, M., Verneuil, V.: ROSETTA for single trace analysis – recovery of secret exponent by triangular trace analysis. In:. INDOCRYPT, pp. 140–155 (2012)

20.

Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: Soriano, M., Qing, S., Lopez, J. (eds.) ICICS, volume 6476 of Lecture Notes in Computer Science, pp. 46–61. Springer (2010)

21.

Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Improved collision-correlation power analysis on first order protected AES. In: Preneel, B., Takagi, T. (eds.) Cryptographic Hardware and Embedded Systems, 13th International Workshop – CHES 2011, volume 6917 of Lecture Notes in Computer Science, pp. 49–62. Springer (2011)

22.

Clavier, C., Joye, M.: Universal exponentiation algorithm – a first step towards provable SPA-Resistance. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Em- bedded Systems – CHES 2001, volume 2162 of Lecture Notes in Computer Science, pp. 300–308. Springer (2001)

23.

Cohen, H., Frey, G. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press (2005)

24.

Comba, P.G.: Exponentiation cryptosystems on the IBM PC. IBM Syst. J. 29(4), 526–538 (1990)CrossRef

25.

Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems – CHES ’99, volume 1717 of Lecture Notes in Computer Science, pp. 292–302. Springer (1999)

26.

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

27.

Gandolfi, K., Mourtel, C., Olivier, F.: Electromagnetic analysis: concrete results. In: Koç Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems CHES 2001, volume 2162 of Lecture Notes in Computer Science, pp. 251–261. Springer (2001)

28.

Gierlichs, B., Batina, L., Tuyls, P., Preneel, B.: Mutual information analysis. In: Oswald, E., Rohatgi, P. (eds.) CHES, volume 5154 of Lecture Notes in Computer Science, pp. 426–442. Springer (2008)

29.

Giraud, C., Verneuil, V.: Atomicity improvement for elliptic curve scalar multiplication. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) Smart Card Research and Advanced Applications, 9th International Conference – CARDIS 2010, volume 6035 of Lecture Notes in Computer Science, pp. 80–101. Springer (2010)

30.

Golić, J., Tymen, C.: Multiplicative masking and power analysis of AES. In: Kaliski, B.S. Jr., Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2002, volume 2523 of Lecture Notes in Computer Science, pp. 198–212. Springer (2002)

31.

Goundar, R.R., Joye, M., Miyaji, A., Rivain, M., Venelli, A.: Scalar multiplication on Weierstraß elliptic curves from co-z arithmetic. J. Cryptographic Engineering 1(2), 161–176 (2011)CrossRef

32.

Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to elliptic curve cryptography. In: Springer Professional Computing Series (2003)

33.

ISO/IEC JTC1 SC17 WG3/TF5 for the International Civil Aviation Organization: Supplemental Access Control for Machine Readable Travel Documents. Technical Report (2010)

34.

Joye, M., Tymen, C.: Protections against differential analysis for elliptic curve cryptography. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2001, volume 2162 of Lecture Notes in Computer Science, pp. 386–400. Springer

35.

Joye, M.: Highly regular right-to-left algorithms for scalar multiplication. In: Paillier, P., Verbauwhede, I. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2007, volume 4727 of Lecture Notes in Computer Science, pp. 135–147. Springer (2007)

36.

Knuth, D.E.: The Art of Computer Programming, vol. 2, 3rd edn. Addison Wesley (1988)

37.

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

38.

Koç, Ç.K: Cryptographic Engineering. Springer (2008)

39.

Kocher, P.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) Advances in Cryptology – CRYPTO ’96, volume 1109 of Lecture Notes in Computer Science, pp. 104–113. Springer (1996)

40.

Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) Advances in Cryptology – CRYPTO ’99, volume 1666 of Lecture Notes in Computer Science, pp. 388–397. Springer (1999)

41.

Kocher, P.C., Jaffe, J., Jun, B., Rohatgi, P.: Introduction to differential power analysis. J. Cryptographic Engineering 1(1), 5–27 (1998)CrossRef

42.

Liardet, P.-Y., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2001, volume 2162 of Lecture Notes in Computer Science, pp. 401–411. Springer (2001)

43.

Longa, P.: Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields. Master’s thesis: School of Information Technology and Engineering, University of Ottawa, Canada (2007)

44.

Micali, S., Reyzin, L.: Physically observable cryptography (Extended Abstract). In: Naor, M. (ed.) Theory of Cryptography Conference – TCC 2004, volume 2951 of Lecture Notes in Computer Science, pp. 278–296. Springer (2004)

45.

Miller, V.S.: Use of elliptic curves in cryptography. In: Wiliams, H.C. (ed.) Advances in Cryptology – CRYPTO ’85, volume 218 of Lecture Notes in Computer Science, pp. 417–426. Springer (1985)

46.

Montgomery, P.L.: Modular multiplication without trial division. Math. Comp. 44(170), 519–521 (1985)CrossRefMATHMathSciNet

47.

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

48.

Moradi, A.: Statistical tools flavor side-channel collision attacks. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pp. 428–445. Springer (2012)

49.

Moradi, A., Mischke, O., Eisenbarth, T.: Correlation-enhanced power analysis collision attack. In: Mangard, S., Standaert, F.-X. (eds.) Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010. Proceedings, volume 6225 of Lecture Notes in Computer Science, pp. 125–139. Springer (2010)

50.

Prouff, E., Rivain, M., Bévan, R.: Statistical analysis of second order differential power a.nalysis. IEEE Trans. Comput. 58(6), 799–811 (2009)CrossRefMathSciNet

51.

Quisquater, J.-J., Samyde, D.: A new tool for non intrusive analysis of smart cards based on electro-magnetic emissions, the SEMA and DEMA methods. Presented at the rump session of EUROCRYPT 2000 (2000)

52.

Schramm, K., Wollinger, T., Paar, C.: In: Johansson, T. (ed.) Fast Software En- cryption – FSE 2003, volume 2887 of Lecture Notes in Computer Science, pp. 206–222. Springer (2003)

53.

Standaert, F.-X., Malkin, T.G., Yung, M.: A unified framework for the analysis of side-channel attacks. In: EUROCRYPT, volume 5479, Lecture Notes in computer science. pp. 443–461. Springer (2009)

54.

Tunstall, M., Joye, M.: Coordinate blinding over large prime fields. In: Mangard, S., Standaert, F.-X. (eds.) Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010. Proceedings, volume 6225 of Lecture Notes in Computer Science. Springer (2010)

55.

Verneuil, V.: Elliptic Curve Cryptography and Security of Embedded Devices, PhD thesis, Universite de Bordeaux (2012)

56.

Walter, C.D.: Sliding windows succumbs to big Mac attack. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2001, volume 2162 of Lecture Notes in Computer Science. Springer (2001)

Titel: Horizontal collision correlation attack on elliptic curves
– Extended Version –
verfasst von: Aurélie Bauer
Eliane Jaulmes
Emmanuel Prouff
Jean-René Reinhard
Justine Wild
Publikationsdatum: 01.03.2015
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 1/2015
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-014-0111-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2015

Construction of RSBFs with improved cryptographic properties to resist differential fault attack on grain family of stream ciphers

Complete reverse-engineering of AES-like block ciphers by SCARE and FIRE attacks

Guest Editorial

Masking and leakage-resilient primitives: One, the other(s) or both?

Threshold implementations of small S-boxes

A survey of fault attacks in pairing based cryptography