Does Curve25519 only provide 112 bit security?

Question

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?

Answer 1

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.