How do I get the equivalent strength of an ECC key?

Question

I know how to calculate the comparable symmetric strength of an RSA modulus: calculate the running time for a field sieve. This is how NIST gives approximate symmetric sizes for asymmetric algos in their publications: for RSA you can calculate running time of the field sieve:

$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$

What's the equivalent for ECDHE? Eg. what is the running time for the best known algorithm for attacking a given ECC curve?

RFC 4492 states:

the following table gives approximate comparable key sizes for symmetric- and asymmetric-key cryptosystems based on the best-known algorithms for attacking them.

Symmetric	ECC (binary curve)	ECC (prime curve)	DH/DSA/RSA
80	163	160	1024
112	233	224	2048
128	283	256	3072
192	409	384	7680
256	571	521 (not a typo)	15360

How can I replicate the ECC column's numbers?

Edit: some some research, the paper mentioned in the RFC now 404s but a copy found at http://infoscience.epfl.ch/record/164526/files/NPDF-22.pdf mentions:

2.6.3. Attacks. A DLNFS equivalent or other subexponential method to attack EC systems has never been published. The most efficient method published to attack EC systems is Pollard’s parallelizable rho method, with an expected run time of 0.88√q group operations.

However I still don't know how to replicate the results: an elliptic curve has P and Q but how do I know what Q is, for, eg, secp521r1?

Edit: Deirdre Connolly on Twitter mentioned an approximation:

$log_2(0.88 \cdot \sqrt{2^{n}})$

Which matches the RFCs results. Will do some more research and post it as an answer in the next few days if she doesn't.

Answer 1

The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg:

$\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$

The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\frac{\pi}{4}}\sqrt{ℓ}} $, where $ℓ$ is the order (number of points) of the subgroup of points on the curve generated by the public base point. The size of $p$ determines the upper bound of $ℓ$, though it is not exactly the upper bound itself, it's generally pretty close. So for example, Curve25519 has an $ℓ$ of about $2^{252}$, so:

$ \log_2{\sqrt{\frac{\pi}{4}}\sqrt{2^{252}}} = 125.82537860389293 $

Our approximation based on the ECC key size gets us pretty close to this:

$\log_2{0.886\sqrt{2^{256}}} = 127.82537860389293 $

As otus notes below, Koblitz curves are slightly different.

The strength of any ECC key is bound to the strength of the underlying curve and domain parameters, and in general all the valid keypairs generated for a specific curve should have the same size/strength. There are some points that are invalid and should not be used, but your ECC implementation should handle that for you.

More info on determining the runtime of Pollard's Rho and thus the theoretical security level of various curves at SafeCurves: http://safecurves.cr.yp.to/rho.html

Answer 2

The previous answer has the correct formula for estimating the security level of prime field elliptic curves. However, the table seems to just list the closest Koblitz curve sizes used, as Richie Frame points out.

If you computed the actual security strength of the curves in question, you would not end up with exactly the values in the left column. For example, with the K-571 curve the formula above would give you about 284 rather than 256. Further, with Koblitz curves Pollard's rho algorithm can be accelerated (pdf) by a factor of about $\sqrt{m}$, where $m$ is the size of the field (the number in the table). So actually K-571 has a security level of about 280 bits.

So why don't the numbers match whichever way you compute them?

That's because the Koblitz curves have been chosen to have a prime $m$ to avoid other attacks. They basically chose the smallest parameters that gave an elliptic curve with enough security for their target level. In comparison the left hand column is just the common "nice" security levels that correspond to symmetric keys that are expressed in bytes.