SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography

There are several different standards covering selection of curves for use in elliptic-curve cryptography (ECC). Each of these standards tries to ensure that the elliptic-curve discrete-logarithm problem (ECDLP) is difficult. ECDLP is the problem of finding an ECC user's secret key, given the user's public key.

Unfortunately, there is a gap between ECDLP difficulty and ECC security. None of these standards do a good job of ensuring ECC security. There are many attacks that break real-world ECC without solving ECDLP. The core problem is that if you implement the standard curves, chances are you're doing it wrong:

• Your implementation produces incorrect results for some rare curve points.
• Your implementation leaks secret data when the input isn't a curve point.
• Your implementation leaks secret data through branch timing.
• Your implementation leaks secret data through cache timing.

These problems are exploitable by real attackers, taking advantage of the gaps between ECDLP and real-world ECC. Secure implementations of the standard curves are theoretically possible but very hard.

Most of these attacks would have been ruled out by better choices of curves that allow simple implementations to be secure implementations. This is the primary motivation for SafeCurves, http://safecurves.cr.yp.to/. The SafeCurves criteria are designed to ensure ECC security, not just ECDLP security.