1
$\begingroup$

I have heard about the standard elliptic curves called NIST curves. What are the properties of such cryptographically secure elliptic curves? Are they standardized according to certain protocols? Also, does the attacker get any huge benefits from knowing which curve was used?

$\endgroup$
3
$\begingroup$

For typical protocols like Diffie–Hellman key agreement and Schnorr-type signature,* SafeCurves surveys the modern security criteria for elliptic curve choice. In these protocols, the adversary is assumed to know the choice of curve; the security comes from criteria of the curve, not of secrecy of the curve.

The basic criterion is that computing ‘discrete logs’—that is, given a scalar multiple $[n]P = P + \dots + P$ of a known point $P$ on the curve by a secret integer $n$, computing $n$—costs well above $2^{100}$ curve additions. But there are many other criteria, like twist security, that are not as obvious to an untrained observer, and were not considered in the design of historical standard curves like NIST P-224.

Certain criteria are not about secure vs. insecure curves per se, but rather about fast and secure vs. fast or secure implementations: for example, NIST P-256 does not admit the Montgomery ladder, which is a fast way to compute $x$-restricted scalar multiplication in constant time. In NIST P-256, you can compute scalar multiplication fast, or in constant time, but not both—so it is tempting to sacrifice security in pursuit of performance when implementing NIST P-256 or choosing an implementation of it, whereas with Curve25519 you can attain both simultaneously using the Montgomery ladder and there is no temptation to sacrifice security that way.

Some of the criteria are relevant to some protocols but not others, for instance because DH key agreement is subject to active attacks that are not relevant in the security model of signatures. Fortunately, some curves satisfy all the criteria, such as Curve25519, Ed448-Goldilocks, and E-521. The first two of those are standardized in RFC 7748, which also prescribes a rigid procedure for selecting a curve for a given prime field satisfying all the security criteria and optimizing performance by certain easy heuristics—a procedure which, incidentally, also generates E-521.


* SafeCurves does not address more exotic applications like pairing-based cryptography, which necessarily use a different class of curves.

In the various proposed post-quantum isogeny-based cryptosystems, choices of curves are secret positions in an isogeny graph of curves, but this is a rather different scenario from what is usually known as elliptic curve cryptography today, and as such seems unlikely to be relevant to your question.

The IETF chose to endorse Ed448-Goldilocks rather than E-521 because Ed448-Goldilocks performs better, and even though the theoretical attack costs on E-521 are higher than on Ed448-Goldilocks, the two both have a meaninglessly high ‘security level’ that only serves as a hedge against minor cryptanalytic advances, not to raise actual costs on what is an impossibly expensive attack to begin with.

$\endgroup$
  • $\begingroup$ In fact there is a way to use a Montgomery ladder on Weierstraß curves like P-256. As usual, Marc Joye was involved: link.springer.com/content/pdf/10.1007%2F3-540-45664-3_24.pdf But it is not very efficient, so people don't use it in practice. $\endgroup$ – Thomas Pornin May 30 '18 at 15:22
  • $\begingroup$ @ThomasPornin Usually that's called the Brier–Joye ladder, not the Montgomery ladder, and yes, it creates a conflict between performance and security. (SafeCurves even addresses it!) $\endgroup$ – Squeamish Ossifrage May 30 '18 at 15:25
-1
$\begingroup$

1, there are websites/tools to check the curves you select, but highly recommend that you use "mature" curves such as secp256k1

2, crypto protocols have nothing to do with the curve selection, such as the authentication protocol.

3, yes, only if you secretly select some insecure curve.

$\endgroup$
  • $\begingroup$ Can you please tell me the link of such websites/tools you mentioned in (1)? $\endgroup$ – Fathima Abdur Rahman Jun 7 '18 at 8:51

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.