Paper 2015/1233

Degenerate Curve Attacks

Samuel Neves and Mehdi Tibouchi

Abstract

Invalid curve attacks are a well-known class of attacks against implementations of elliptic curve cryptosystems, in which an adversary tricks the cryptographic device into carrying out scalar multiplication not on the expected secure curve, but on some other, weaker elliptic curve of his choosing. In their original form, however, these attacks only affect elliptic curve implementations using addition and doubling formulas that are independent of at least one of the curve parameters. This property is typically satisfied for elliptic curves in Weierstrass form but not for newer models that have gained increasing popularity in recent years, like Edwards and twisted Edwards curves. It has therefore been suggested (e.g. in the original paper on invalid curve attacks) that such alternate models could protect against those attacks. In this paper, we dispel that belief and present the first attack of this nature against (twisted) Edwards curves, Jacobi quartics, Jacobi intersections and more. Our attack differs from invalid curve attacks proper in that the cryptographic device is tricked into carrying out a computation not on another elliptic curve, but on a group isomorphic to the multiplicative group of the underlying base field. This often makes it easy to recover the secret scalar with a single invalid computation. We also show how our result can be used constructively, especially on curves over random base fields, as a fault attack countermeasure similar to Shamir's trick.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in PKC 2016
Keywords
Elliptic curve cryptographyEdwards curvesImplementation issuesFault attacksCountermeasures
Contact author(s)
tibouchi mehdi @ lab ntt co jp
History
2016-01-13: revised
2015-12-28: received
See all versions
Short URL
https://ia.cr/2015/1233
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1233,
      author = {Samuel Neves and Mehdi Tibouchi},
      title = {Degenerate Curve Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1233},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1233}},
      url = {https://eprint.iacr.org/2015/1233}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.