Here are some short notes about SafeCurves. This is mainly a "don't panic" for people who use curves that are not marked as "safe". SafeCurves does 3 different groups of checks.
These just check whether the curve makes sense. They check whether the prime that generates the field is actually a prime, whether the curve equations are defining an elliptic curve and whether the base points are actually on the curve. These things are easy to check even with little mathematical background and putting in a backdoor by violating one of these constraints would not be feasible since it would probably be discovered quickly (but it never hurts to check the simple things).
Here, curves are checked against known attacks on the ECDLP (Elliptic Curve Discrete Logarithm Problem). Some of these attacks only work if the curve parameters have a special form that satisfies certain arithmetical conditions. "Rho" basically just checks how fast the rho attack is on a given curve. The cost limit for safety set by SafeCurves is \(2^{100}\) which is arbitrarily chosen. Anything below \(2^{80}\) is considered insecure nowadays and as technology advances (chip-making, not math) this number will rise. However, the cost rises exponentially and even though the famous "Moore's Law" is exponential too, firstly it is slowing down already and secondly it is easy to escape any computational threats for a certain time by just chosing larger key sizes. Remember that adding bit to the key size (roughly) doubles the computational cost.
Security against transfers are also tested. If you are using curves that fail this test you should be worried. If your curve is not listed and you actually care about the security of your product, it is highly recommened to get an expert to check your curve (not only this particular attack, but all in "Curve Parameters" and "ECDLP Security"). If a curve is vulnerable against transfers this means that the ECDLP can be solved in polynomial time (i.e. much faster than you would want).
The story with discriminants is explained nicely on the SafeCurves site and i will not repeat it here; there is nothing controversial about it. Using curves that fail this test is not a big problem, however, as noted on the SafeCurves site, "there are speedups to the rho method for some curves where |D| is very small [...]".
Rigidity is the first real problem. The questions is simple: What if someone found an attack on the ECDLP that only works on very few curves with special algorithmic properties, but instead of publishing the attack, they create and subsequently standardize curves that can easily be broken using the newly discovered attack. It is therefore desireable that the curve's random parameters are derived from something simple. Rigidity is explained in more detail on the SafeCurves site. Using a non-rigid curve basically means trusting whoever issued the curve to not have an "ace up their sleeve" that would break the ECDLP on that particular curve. Needless to say, when it comes to security, trusting someone is difficult.
This is the part where I honestly do not always agree with SafeCurves or at least not under all circumstances. SafeCurves correctly state that the hardness of the ECDLP does not guarantee ECC (Elliptic Curve Cryptography) security. The SafeCurves approach is to design the curves in a way to guarantee ECC security using the properties of the curve.
Ladders: The main argument here is that certain curves can be implemented more safely than others because their scalar-point multiplication is less complicated. A straightforward implementation of a typical curve's multiplication algorithm is susceptible to timing attacks and needs both the x and y coordinate of a point to work. If you want to make a smartcard or cryptographic token, then you do have to worry about timing attacks and chosing a curve that provides a way to implement inherently constant-time multiplication that is also simple in that only the x coordinate is needed might save you from making some typical mistakes. However, if your application is just accessible over a network like for example a website, and you are using a sufficiently well-tested cryptographic library like openssl, taking additional precautions to make timing attacks difficult if not impossible, you are still on the safe side even if you are using a curve that is not marked as "safe" on the SafeCurves site.
Twists: These are also very well explained on the SafeCurves site. Most modern curves are not susceptible to small-subgroup attacks because their cofactor is 1. The bigger problem is an invalid-curve attack. This can easily be prevented by an implementation by checking whether points are actually on the curve or by using point compression. If an implementation does not check points (e.g. externally supplied public keys in a DH key exchange) on some curves it is easier to break ECC security than on others. When should you worry about this? The answers are, whenever there are a lot of different implementations of ECC in your system (one is bound to forget about the checks) or when you do not know if the implementation you are using is secure against invalid-curve attacks.
Completeness: This is well-explained on the SafeCurves site. The problem basically is that the off-the-shelf addition laws for Weierstrass curves do not work for a few critical points. When writing an ECC implementation, these have to be considered or else it is very easy to break ECC security. SafeCurves' solution to the problem is to use curves where there is just one addition law that applies to all points and therefore also eliminates a timing attack. However, when writing a new cryptographic library (perhaps because licensing problems do not allow to use off-the-shelf implementations) you might have to support curves that do not exhibit the simple-addition-law property. Even if you can chose the curve, you are mostly safe when chosing an existing well-tested cryptographic library, which probably includes the correct algorithms for all special points and maybe even protection against timing attacks. Most big cryptographic libraries do not yet support many (or any) of SafeCurves' safe curves though, and if you want to support multiple curves you might have to use one of the established libraries.
Indistinguishability: In my opinion, this is the most controversial of SafeCurves' requirements. It requires that it should be possible to encode a curve point in a way that it is undistinguishable from random data, to make it more difficult to filter/prevent encrypted traffic. As far as I know, traffic filters mostly work by recognizing the header. Preventing TLS is as easy as dropping all TLS packets, there is no need to search the traffic for byteblocks that could be a point on an elliptic curve. Moreover, this strategy would yield a high false-positive rate: Typical curve points are anywhere between 128 and 512 bits long, i.e. 16 to 64 bytes, and the majority of bitpatterns are valid curve points. Furthermore, checking an unaligned sequence of up to 64 bytes for whether it is a point on a curve is very computationally intensive. Nifty protocol-designers might even shift the key bits by a random number of bits. The challenge here is not to make the key indistinguishable from random data but to make the whole protocol look insuspicious.
SafeCurves also requires a certain form of curve which makes it possible to encode keys to pseudorandom data. However, recently a new paper by Mehdi Tibouchi that describes a way to represent any curve's points as pseudorandom data.
Most of the attacks discussed in the "ECC security" part only work against faulty implementations (see "Hints" below). Implementing ECC cryptography or cryptography in general is not an easy task and should be avoided. In my opinion, arguing against using certain curves because it is "relatively easy" to create erronous implementations is a weak argument: Most cryptographic libraries do not yet support curves that are considered safe by SafeCurves. Therefore if you want to use these curves you have to write a new implementation or integrate an existing one into an existing cryptographic library, both of which creates opportunities for making mistakes that have consequences on the security of ECC. SafeCurves' safe curves should be used by people who do not have a choice but to write a new implementation of ECC anyway, but for everyone who uses existing, well-tested cryptographic libraries which would require to add code to support these curves should probably stick to curves that are "just" secure in the "Curve Parameters" and "ECDLP Security" sections, because good cryptographic libraries are unlikely to suffer from implementation problems. This does not mean nobody should add support for new types of curves to existing cryptographic libraries, it just means not everyone is suited for the task.
Feel free to comment on/correct me by sending me an email.
Written on 06.02.2014