Security of elliptic curves

Question

How can we say an elliptic curve is secure and can be used for cryptographic applications?

Answer 1

Mathematically speaking, we cannot. There is no proof that elliptic curves are actually "secure". But the same apply to about all other cryptographic algorithms, so we have to make do with the next best thing: since we cannot prove that any curve is "secure", we'll use curves that we do not know how to break (and not for lack of trying).

That last part is very important: we gain some level of trust in the robustness of a curve through that curve being exposed to the fierceness of many cryptographers for a long time. If a curve was thus specified and used and attacked for years, and none of them succeeded at even making a dent in it, then we begin to say that the curve is "probably strong"; or, similarly, that if that curve has weaknesses, then these weaknesses are not obvious. This is about the best we can achieve.

An important consequence is that only fully specified, standardised curves that have been analysed for years can claim to be "secure" in that sense. So, in practice, use one of the standard curves. Which means one of the three most common NIST curves (P-256, P-384 and P-521; see FIPS 186-4), or one of the two "newer" (but nifty) curves Curve25519 and Curve448 (see RFC 7748).

---

That being said, we can list a few basic criteria that "secure" curves must fulfill. Matching all these criteria does not guarantee security in any way, but if any of them is not matched, then cryptographers will laugh and mock it.

• The curve order (number of points on the curve) must be a large enough prime integer, or a multiple of a large enough prime integer. "Large enough" means here that the equivalent of discrete logarithm for elliptic curve can be solved in time $O(2^n)$ for a prime of size $2n$ bits. Since we want at least "100-bit security", that prime integer should have at least 200 bits in length (cryptographers are suckers for powers of 2, so traditionally we aim for "128-bit security"). Implementation in many contexts is made easier if the curve order is prime, and not only a multiple of a big prime, so if a curve order is not exactly prime, it better have a good reason for that.

• The curve should not be anomalous or singular or supersingular. These are special curves with additional mathematical property, which may thus lead to easier attacks. Note: for some specific contexts (pairing-based cryptography), we have to use special curves, and the possible weaknesses must be compensated for with, basically, use of bigger curves (hence slower).

• The embedding degree of the curve must be large enough to discourage attacks that leverage the same mathematics as pairings (e.g. MOV attack). If the curve is defined in a finite field of size $q$, and the curve order is (a multiple of) the big prime $r$, then the embedding degree is the smallest integer $k \gt 1$ such that $r$ divides $q^k-1$ (this is the Balasubramanian-Koblitz theorem). The MOV and FR attack turn discrete logarithm on the curve (work factor $O(2^{r/2})$) into multiplicative discrete logarithm in a finite field of size $q^k$, where subexpoential algorithms are known.

  In general, unless you use a special curve (e.g. supersingular) or deploy some extensive mathematical juggling aiming at generating a curve with a small embedding degree, a "random" curve will have an extremely high embedding degree ($k$ will have about the same size as $r$). One widespread ECC standard (ANSI X9.62) mandates that, when generating a curve (assuming you want to do that, but, as explained above, this is probably a bad idea), you should verify that $k$ is greater than $100$ (i.e. you check that $r$ does not divide $q^k-1$ for all $k$ from $2$ to $100$).

• Since a curve is defined with an equation over a specific field and with a couple of extra parameters, there is room for inserting arbitrary values. Cryptographers don't like arbitrary values. If somewhat "magic" constants must appear, they prefer these values to be nothing up my sleeve numbers. We don't know how we could somehow "rig" a curve with special parameters, in a way which cannot be detected (e.g. with a low embedding degree), but in all generality we prefer it when such rigging cannot happen because values are not arbitrarily chosen.

• Implementing elliptic curve securely is hard. For instance, the "new" curves Curve25519 and Curve448 are easier to implement securely for several reasons, the two main being:

  • These curves are derivative from Montgomery curves and thus admit an efficient point multiplication algorithm that is "naturally" constant-time (it won't leak secret values through varying execution time or memory access pattern).

  • Each of these curves is actually two curves, where any patterns of bits will be interpreted as a point on one of the curves or on the other. This avoids the need to perform point validation and make tricky decisions about the handling of invalid input data.

  Thus, a "secure curve" must be such that it makes it easy, or at least not impossibly hard", to implement computations in a secure way. On that criterion, the NIST curves (P-256...) are "less secure" than Curve25519 and Curve448. Note, though, that even when a curve is easier to implement securely, that does not mean that it is easy in absolute terms. For about the same reason that you should not invent your own curves, you should not either make your own implementations. And if you use an implementation which was done with great care and was reviewed by many competent people, then the difference between curves in that respect is mostly nullified.

It shall be noted that while we want to avoid "special structure" in curves, one specific special structure is especially alluring in terms of performance: choosing a base field that promotes efficient computations. For instance, Curve25519 is defined in the field of integers modulo $q = 2^{255}-19$. This value being very close to a power of $2$, this makes computations much faster. This is the point where cryptographers tend to throw away caution for the sake of good benchmarks. We do not know how a special base field structure could be leveraged to break discrete logarithm faster; but we declared anathema on random parameters with no better justification, so it is kinda weird that we allow special fields and not arbitrary curve equation parameters. My gut feeling (which is thus scientifically unsubstantiated) is that if the standard curves ever get into cryptanalytic trouble, this will be due to special base field structure. But it won't prevent me from sleeping at night.

---

If any of the above seemed obscure, then go read this book.

Answer 2

Elliptic curve security relies on the difficulty of computing a discrete logarithm. Stinson defines the problem in his book titled $\textit{Cryptography: Theory and Practice}$.

Given a multiplicative group $G$, an element $\gamma \in G$ having order $n$, and an element $\beta \in \langle \gamma \rangle$, find the unique integer $a, 0\leq a \leq n-1$, such that $$\gamma^a = \beta.$$ The integer $a = log_{\gamma}\beta$ is kown as the discrete logarithm of $\beta$.

As of today, if the order of your group is chosen large enough, there is no polynomial time algorithm that can solve this problem (unless your adversary has access to a quantum computer).