What risks are involved when choosing a curve for an implementation of ECC?

Question

What risks are involved when specific curves are chosen for an ECC implementation?

How should I audit a system that uses ECC with regards to a specific curve?

Bonus: How can I (or a cryptographer) determine if a curve is backdoored?

Answer 1

There are three main kinds of problems that you could conceptually envision in a choice of curve:

1. The curve may have some structure which allows for some known attacks to run efficiently. Possible structural weaknesses include the following (this list is not exhaustive):

   • The chosen curve subgroup may have a non-prime order.
   • The chosen curve subgroup may have a prime order which is too small.
   • The curve could have a very low embedding degree that allows Weil-descent like attacks.
   • The curve may allow practical computation of a symmetric pairing and be used in a protocol that requires resistance to the decisional Diffie-Hellman problem.

2. The curve might have some unknown structure which allows for an attack to run efficiently, as long as the attacker is aware of that structure. This is what we could rightfully call a "backdoored curve". The important point here is that there is published way of making backdoored curve. We don't actually know if it is even possible that a curve be "backdoored", let alone how to do it.

   It can be argued that any structure that allows attacks (a problem relevant to the first category above) used to be an "unknown structure" (this second category) before it was discovered and published. However, all of these have been discovered in the first few years after the first suggestion of using elliptic curves for cryptography in 1985. It has been more than 20 years since that kind of thing was last encountered. Thus, we can say that if there still are ways to "backdoor curves", i.e. as-yet-unknown curve structures that allow attacks but are not, by definition, currently detectable (since we don't know what to look for), then these hypothetical attacks are most probably not obvious.

   Beyond that it is just rumours, gossip, and occasional downright calumny. My own gut feeling is that if there still are funky things hidden in curves and not general to all curves, then they would probably be related to the choice of field. We tend to define curves with integers modulo primes with a "special format" that helps with efficient implementation, e.g. $p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$ for NIST curve P-256, or $p = 2^{255}-19$ for Curve25519. My bet is that if something wrong is found with either curve, then it will probably be due to that special modulus format. But it's just a bet. It's no more substantiated than that.

   The SafeCurves site is a good source for listing all known attacks, with an extra layer of gossip, which takes a stance somewhat different from mine: it sees "lack of rigidity" as a potential issue worth considering, but not special formats for the field modulus. Remember that it's all gut feelings at this point.

3. Implementation issues are likely to be the prevalent problem. Having a nice mathematical structure is good, but at some point there must be some actual code that runs on concrete, physical hardware. Incorrect computations, lack of validation of inputs, side-channel leaks... all of these lead to practical attacks. Implementing cryptography is a difficult art, even more so when complicated mathematics are involved.

In practice, any system that uses a curve which is not one of the few "standard" curves is a system that, by definition, uses a custom implementation, and it can be expected that this implementation suffers from a number of issues. One spectacular example was Sony, who, for the complete firmware and OS of their PlayStation 3 console, decided to make their own curves (no less than 64 different curves!). This implied that they had to use their own implementations for everything related to the curves, and, famously, they totally goofed up their ECDSA signatures.

Thus, as first-order approximation: if you audit a system that uses an elliptic curve, and that curve is not one of P-256 (aka "secp256r1"), Curve25519 (aka "ed25519"), or Curve448 ("ed448"), run away.

Among alternate curves that are sort-of OK, you could find secp256k1 (the "Bitcoin curve"), which has some internal structure (it's called a "GLV curve") that does not seem to lead to any fast attack, and the corresponding library is known to be a very decent implementation (for one, it's constant-time) (but OpenSSL's implementation of secp256k1 is not constant-time, so beware). An other one is NIST curve P-384, but good implementations of that curve are rather scarce. About anything else is bad news, unless some specific property (e.g. "pairing-friendliness") was specifically sought.

Answer 2

Risks of choosing specific curves

Using your own crpytographic scheme (a.k.a. "rolling your own crypto") is extremly bad. Anyone can invent an encryption algorithm they themselves can't break. It's much harder to invent one that no one else can break. It's also bad practice to use a non-open-source API for cryptography because you might not know how exactly it's implemented.

But using specific curves doesn't necessarily imply that it's unsecure. Standardized ECC often uses specific curves that are presumed to be secure.

So in general it's good practice to use standardized ECC (i.e. curves from the safe-curve-project) and open-source implementations that have been vetted and are broadly in use.

Auditing a ECC system regarding specific curves

The first thing you should do is research. If you find a paper that raises concern about the security of a specific EC then you should probably find another one.

How to determine if a curve is backdoored

Like many other cryptographic schemes ECC uses random number generators, specifically CSPRNGs.

The problem is, that such CSPRNGs could potentially have a keltographic backdoor, if certain conditions are met. One example of this is a (former) CSPRNG, the Dual_EC_DRBG.

Many cryptographers (i.e. this PDF) have raised concern about this generator and through the Snowden leaks it is now presumed that the NSA had put a kleptographic backdoor in this generator. This video by Computerphile explains it quite well.

The vulnerability of ECC is not the discrete logarithm problem, this is (very likely) not solved. It's rather the implementation of the ECC scheme and especially the usage of certain CSRNGs. If there is a constant in the CSRNG it should be stated how and why this constant was calculated and chosen.