How strong is the ECDSA algorithm?

Question

Some cryptographic algorithms are as strong as the size of their key is, while other have some weaknesses that limit their strength (such as SHA-1). How strong is the ECDSA algorithm, and does that strength depend on anything (for example, the curve used and so forth)?

Answer 1

First of all, I'm no expert in this area. Generally $n$ bit ECC seems to have a security level of about $n/2$, but I found some claims that it's lower for certain types of curves.

---

RFC4492 - Elliptic Curve Cryptography (ECC) Cipher Suites contains the following table:

               for Transport Layer Security (TLS)

                Symmetric  |   ECC   |  DH/DSA/RSA
               ------------+---------+-------------
                    80     |   163   |     1024
                   112     |   233   |     2048
                   128     |   283   |     3072
                   192     |   409   |     7680
                   256     |   571   |    15360

It doesn't seem to distinguish between different curve types.

---

I found an RFC draft (not a real standard RFC) that claims the following security levels:

Symmetric  |  ECC2N  |  ECP  |  DH/DSA/RSA
       80  |   163   |  192  |     1024
      128  |   283   |  256  |     3072
      192  |   409   |  384  |     7680
      256  |   571   |  521  |    15360

This is consistent with other other sources that put the security level of ECC at $n/2$. Binary curves (which includes Koblitz curves as used in Bitcoin) seem to be a bit worse than prime curves (used pretty much everywhere else).

The blog entry Not every elliptic curve is the same: trough on ECC security elaborates:

Additionally, something that most people does not know, but that it’s extremely relevant to our analysis, is that there are different kind of ECC curve cryptography and their “size” it’s different depending on the kind of curve:

• ECC Curves over Prime Field (often referred as Elliptic Curve and represented by P-keysize)
• ECC Curves over Binary Field (often referred as Koblitz Curve and represented by K-keysize)

Given a security strength equivalence the Elliptic Curve and the Kobliz Curve have different key size, for example when we read ECC 571 we are referring to Koblitz Curve with an equivalent strength to ECC 521 Prime curve.

For some curves (like supersingular ones) there are specific attacks, which make them significantly weaker.