14
$\begingroup$

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   |  DH/DSA/RSA
               ------------+---------+-------------
                    80     |   163   |     1024
                   112     |   233   |     2048
                   128     |   283   |     3072
                   192     |   409   |     7680
                   256     |   571   |    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 * 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.

$\endgroup$
  • 1
    $\begingroup$ Thanks @otus. I still don't know how to get NISTs results even after reading the paper. If you know I'll happily award you the answer! $\endgroup$ – mikemaccana Dec 21 '15 at 18:03
  • $\begingroup$ I'm pretty sure they just took one (or some) data points to find the constant (0.88) hidden behind the $\mathcal O(\sqrt{n})$ complexity or they just analyzed the best pollard rho version hard enough to get 0.88 as an estimate. $\endgroup$ – SEJPM Dec 21 '15 at 19:21
  • $\begingroup$ Note: "Q" in the video is used to denote an arbitrary second point for addition. This may be P or some multiple thereof usually. $\endgroup$ – SEJPM Dec 21 '15 at 19:38
  • 2
    $\begingroup$ FYI, the ecc sizes in the RFC chart show Koblitz curve sizes, which have a different security level than prime field curves $\endgroup$ – Richie Frame Dec 22 '15 at 1:02
13
$\begingroup$

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{\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{\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

$\endgroup$
  • $\begingroup$ It might be a good idea to pull out $n$ from the equation, so you end up with something like $\frac{l}{2} - 0.17$. $\endgroup$ – CodesInChaos Dec 23 '15 at 11:14
  • $\begingroup$ Where does pi/4 come from? Isn't Pollard's Rho complexity sqrt(pi/2 * l) ? $\endgroup$ – user13741 Dec 23 '15 at 19:49
  • 2
    $\begingroup$ @user13741, it's due to an optimization that halves the search space. $\endgroup$ – otus Dec 24 '15 at 14:04
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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