Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
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. –  CodesInChaos Apr 28 '12 at 23:15
    
@CodeInChaos: Would you care to expand this comment into an answer? –  Paŭlo Ebermann Apr 29 '12 at 21:05
1  
@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. –  CodesInChaos 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. –  David Schwartz Apr 30 '12 at 7:06
add comment

1 Answer

up vote 12 down vote accepted

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.

share|improve this answer
1  
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. –  Paŭlo Ebermann 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. –  CodesInChaos Apr 30 '12 at 9:27
    
Since supersingular curves are vulnerable to some attacks(MOV) why people still use them? –  curious Apr 21 '13 at 16:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.