I was asked to do a research about attacks on various digital signature schemes. There is one thing that bothers me for which I could not find a direct answer.

For digital signatures that are based on prime numbers (like RSA) attacks are theoretic for example "chosen ciphertext attack" or "known plaintext attack", a very good source could be "Twenty years of attacks on RSA cryptosystem"

For Elliptic Curve Cryptography (ECC) based digital signatures attacks are purely physical, for example "fault attacks" or "side-channel attacks", a typical source is "A survey of fault attacks"

Why there are no theoretic attacks on ECC? the reason that answer is important for me is because I am supposed to implement an attack for a specific ECC digital signature. Since it is not implemented on an actual device (at least yet) I can't do that (attacks are physical) and I can't figure another similar work as my guideline.

I barely managed to find some few paragraphs like this "The main reason for the attractiveness of ECC is the fact that there is no sub-exponential algorithm known to solve the discrete logarithm problem on a properly chosen elliptic curve" is this the reason? or am I missing something very obvious?

  • Look up batch cracking attacks and the attacks that have an effect of squaring the key space in security
    – Natanael
    Dec 15 '14 at 14:35
  • "chosen ciphertext attack" isn't really an attack. It's more like an attack model. Dec 16 '14 at 14:36

A couple of pitfalls with ECC:

  • Invalid curve attacks: Attacker encodes a point which is not on the curve and has low order. Deadly attack on Diffie-Hellman. I don't think this can be exploited with ECDSA since there is no attacker controlled point.
  • Point on twist on a non twist secure curve: Same as above, but works for compressed points as well.
  • Incorrect handing of special cases: Traditional ECC addition formulas need to handle several special cases. It's easy to forgot one.
  • (EC)DSA needs a uniformly distributed per-signature value. Using the same value twice or using a guessable value leads to key recovery. Even a small bias can lead to key recovery if enough signatures are known by the attacker. RFC6979 describes a deterministic generation method.
  • Applications relying on unusual properties the signature scheme doesn't provide. For example signatures are malleable, which caught some bitcoin applications by surprise.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.