16
$\begingroup$

In a recent mail on the IETF CFRG mailing list it was claimed that:

The (currently missing) security considerations (or somewhere) should describe why Curve25519 is ok when used in contexts where we'd otherwise ask for 128 bit strength, (basically because it's close enough), and also why the 224 bit level is considered a good choice. There was a lot of debate on the list about that, and I've seen the issue come up elsewhere so this text will avoid re-litigating that and should be worthwhile even if it takes a little time to agree.

I read this such that Curve25519 only provides security on the 224-bit level i.e. 112 bit security.
But when I look up Curve25519 on Wikipedia I get to see in the very first line that

Curve25519 is an elliptic curve offering 128 bits of security

Wikipedia itself references to Bernsteins original paper "Curve25519: new Diffie-Hellman speed records" which indeed confirms Wikipedia as follows:

Every known attack is more expensive than performing a brute-force search on a typical 128-bit secret key cipher.

So my question is:
Does Curve25519 indeed provide significantly less security than 128-bit?

$\endgroup$
  • $\begingroup$ You can find such information on Curve25519 an other curves on safecurves. For example the costs for the rho method. $\endgroup$ – Chris Aug 27 '15 at 22:30
  • $\begingroup$ BTW some recent recommendations like the german BSI use an imaginary security level of "100 bits" to work around some estimates. All interpretations would pass this. TR-02102 german PDF $\endgroup$ – eckes Jan 7 '16 at 2:15
21
$\begingroup$

Some claim that Curve25519 has 112 bit security, others that it has 128 bit security; which is it?

Well, actually, neither - it's actually somewhere in the middle.

For a curve without known weaknesses (and Curve25519 doesn't have known weaknesses), then if the curve order has a large prime factor around $2^{2k}$, then the best known attacks against it take $O(2^k)$ time (where the O-notation conceals a constant which is a bit larger than 1, but is constant for the various types of curves), and so by convention, we say that such a curve as "k-bits of strength".

Now, for Curve25519, the curve order has a prime factor circa $2^{252}$; by the above standard metric, this yields a security of 126 bits. This is slightly less than the 128 bit security that the curve P256 claims; however it is significantly more than the 112 bit security that was claimed on the IETF mailing list.

Is the difference between 126 and 128 bit security significant? In my opinion, no; a work effort of 128 bits ought to be sufficiently large that a factor of 4 decrease in the attacker's time still should make this infeasible.

In addition:

Every known attack is more expensive than performing a brute-force search on a typical 128-bit secret key cipher.

Makes a very good point; against an elliptic curve, the fundamental operation that is perfomed during the attack is an elliptic curve point addition; this is significantly more expensive than (say) testing an AES key. And, I believe this remains true even if you factor in a 4-times speedup on the elliptic curve side.

$\endgroup$
  • 1
    $\begingroup$ Don't forget that 5 bits of the private key are always the same $\endgroup$ – Richie Frame Aug 27 '15 at 20:13
  • 7
    $\begingroup$ @RichieFrame: actually, 4 of those bits are already accounted for by the fact that the full order size is 255 (not 256) bits, and that the cofactor is 8. DJB does leave one addition bit fixed (however, that's not inherent in the Curve25519; that's how Dan suggests it be used); however even with that change, that reduces the strength to 125.5 bits... $\endgroup$ – poncho Aug 27 '15 at 20:18
  • $\begingroup$ Funfact: I just saw a response to the comment in question on the CFRG list and the 224-bit level part was targeting Ed448 / Curve448 and not Curve25519. oops. But nonetheless great answer and it also (indirectly) answers that 255 bit (or a bit less) is totally OK :) $\endgroup$ – SEJPM Aug 29 '15 at 16:35
  • $\begingroup$ BTW: DJB addressed this also in his response to NIsT re-opened FIPS 184-6 discussion: PDF $\endgroup$ – eckes Jan 7 '16 at 2:10

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.