How strong is the ECDSA algorithm?

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)?

• Depends a bit on the curve. Security level is around n/2 for prime curves, a bit less for kobitz curves. So Secp256k1 isn't the wisest choice for a 256 elliptic curve, but should still be secure enough in practice. Apr 28 '12 at 23:15
• @CodeInChaos: Would you care to expand this comment into an answer? Apr 29 '12 at 21:05
• @PaŭloEbermann I was hoping for somebody who knows what he's talking about to write an answer. For me ECC is pretty much magic. Apr 29 '12 at 21:56
• For mere mortals, all you need to know is that so long as you use curves that have been professionally vetted, the security level is about the same as a symmetric cipher with a key length about half the curve size. So a 256-bit ECDSA key is about as hard to break as 128-bit AES. Apr 30 '12 at 7:06

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 seem to be a bit worse than prime curves.

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.

• It's a bit strange that this draft has a lower size (163 versus 192) for the 80-bit-security binary curve, but higher sizes for all the higher securities. It looks like a mixup, but it is consistently used throughout the document. Apr 30 '12 at 7:33
• And the ECC2N column of that draft is identical to the ECC column of the TLS spec. It'd be interesting to know, how those numbers were calculated. Apr 30 '12 at 9:27
• Since supersingular curves are vulnerable to some attacks(MOV) why people still use them? Apr 21 '13 at 16:37
• I suspect that the weird ECC sizes in those tables are simply the sizes of standardized curves and don't reflect security differences between binary and prime fields. Apr 7 '16 at 17:30