8

As far as I know, Curve25519 offers "only" a security level equal to an 128bit symmetric cipher. I'd like to know if there are new (not NIST) curves, which provide a security-level comparable to a 256bit cipher AND already used by some applications?

As far as I know, there are curves like E-521 or M-511 which have a very high security margin, but I don't know any implementation which is currently using them.

(Btw., I know that 128bit is considered secure, but it seems a little bit weird that we often use 256bit symmetric ciphers combined with 4K-RSA or an 256bit curve.)

K. Biermann
  • 364
  • 2
  • 11
  • 4
    We don't always use 256-bit ciphers. AES-128 is highly used, and is still (and will for the foreseeable future continue to be) considered a perfectly reasonable option for any new cryptosystem. In the absence of any specific 256-bit requirement, many would argue that AES-256 over AES-128 is simply wasted CPU cycles. – Stephen Touset Apr 13 '15 at 18:20
  • Corrected "always" to "often" :D – K. Biermann Apr 13 '15 at 18:24
  • I guess it depends on how well you test the parameters and how much you trust the organizations, but there are the P521 and Brainpool P512 curves. Although Bernstein shows very well how using these curves can be dangerous, that doesn't mean that they are certain to have a lower security level than about half the number of bits. – Maarten Bodewes Apr 13 '15 at 20:49
  • 1
    As for your last remark: that's not so strange, the 256 bit cipher will have almost no overhead (both with regards to size and CPU power). Calculating a >4K RSA key is tricky, the HSM's will be expensive. So although 256 bit AES will not provide much of a security benefit, it won't hurt much either. I'm mostly against AES-256 because it makes a protocol look more secure than it actually is - most of the time. E.g clients wanting 256 bit AES on a smart card where side channel attacks are a much bigger threat; they are basically fooling themselves. – Maarten Bodewes Apr 13 '15 at 20:58
  • @MaartenBodewes How does 256-bit AES make side-channel attacks a bigger threat? The key schedule can output an arbitrary number of round keys, and other than that the only difference is the number of rounds. The only downside to using 256-bit AES on a smart card that I can think of is the bigger performance hit for such a resource-constrained device. – forest May 28 '18 at 02:33
  • You're not interpreting my comment as I intended. I was saying that side channel attacks in general are more a threat than attacks on a lower key size. I didn't say that AES-256 would be the cause of them. – Maarten Bodewes May 28 '18 at 03:45

2 Answers2

12

There is nothing more secure than "secure". An attacker who can break it upfront, because it has "only" 128-bit security, is an attacker who has way more available computing power than all computers on Earth taken together (even including smartphones and coffee machines). It is implausible that such an attacker would swoop down so low as to bother breaking your key; he already knows all your thoughts, directs all your actions, and probably owns your soul as well.

Security levels beyond 128 bits are not meant to provide "more security", but to appease auditors, managers, customers and prospective mates (not necessarily in that order) by a powerful display of extra bits. This is like birds of paradise: by using an oversized key, you send the signal that you are so great that you can afford wasting CPU and network bandwidth on ridiculously enlarged cryptography.

Realistically, if (when) your key is broken, then it won't be through its size; it will be through software bug, hardware leak, or key misuse in a poorly designed protocol. In that sense, we can talk about actual security:

  • The designer of Curve25519 and author of its usual implementation is Daniel J. Bernstein, who is known to "know his trade". His code probably contains far fewer bugs than what most developers would do. Using his code is, all other things being equal, a good idea.

  • On the other hand, protocols are an important issue, and it is much easier to botch a protocol than a cryptographic algorithm implementation. By looking for a curve, you are looking for the wrong thing. You should think "what protocol should I use ?" and then (only then) worry about the specific curve, in case the protocol you chose happens to allow use of several curves. Curve25519 has not (yet) percolated into all or even most well-established protocols. For instance, there is no support for Curve25519 in SSL/TLS (there is one in SSH, though).

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • Well, I'm not sure that this is entirely true; for example offers AES-256 not only a longer key but also more rounds, which could make algebraic attacks which work on AES-128 infeasible on AES-256. On the other hand, I don't think this applies to ECC. – K. Biermann Apr 13 '15 at 19:42
  • 1
    "Algebraic attacks which work on AES-128" are a rarity, though -- none is known at the moment. Moreover, for the (quite esoteric) related-key attacks (that usually don't matter at all, fortunately), AES-256 turned out to be _weaker_ than AES-128. So more rounds or more key bits can make things worse. – Thomas Pornin Apr 13 '15 at 19:51
  • Yup, this is correct. But if I'm right it is not the fault of the additional rounds that AES-256 is weaker, but the fault of the key-expansion. Correct me if I'm wrong, but as far as I know more rounds usually make the algorithms more secure (and slower). Also you are correct that there is "nothing more secure than secure", but the security-marge is not unimportant, because something considered secure today has not to be secure tomorrow. And a higher security-marge is no guaranty, that it will be secure tomorrow, but non the less it can save your ass. But this is a little bit off-topic :D – K. Biermann Apr 13 '15 at 19:55
  • 1
    That more rounds mean slower code is a fact. Whether more rounds increase security is more a "traditional point of view"... and, in particular, if an attack is found, whether additional rounds protect or not depends a lot on the details of the algorithm and of the attack. The notion of more rounds bringing some sort of "security margin" is not completely substantiated (but talking of it as a "security margin" implicitly implies acceptance of that notion). It is something we do, not really something that necessarily works. – Thomas Pornin Apr 13 '15 at 20:07
  • Why are some people so insistent on keeping a very low security level? 128 is way, way too low. – étale-cohomology Apr 28 '22 at 14:35
6

I realize this post does not directly answer your question, but I thought I'd post it anyway as a "devil's advocate" rebuttal to Thomas's post.

I fully agree with Thomas; there is no one who could give any reason to think you'll ever need more than 128 bits of security in our lifetime.

That being said, Bernstein, the author of Curve25519, did co-author an alternative curve, Curve41417, which has just over 200 bits of security. In their paper, [1] they state that it ``is easy to see that 2^128 is far beyond any computation feasible today,'' but they also reason that:

  • Cryptographic primitives need time to be reviewed---weaknesses may exist---and thus a high security margin is not a bad thing
  • It is physically possible that, in a few centuries, we may have enough computing power capable of calculating 2^128 operations per year
  • Some ECC protocols that depend on curves do not have tight security bounds; thus having a higher security margin to offset this is necessary
  • We should be asking "how much security can we get out of our performance requirements" rather than "how much performance can we get out of our security requirements," and in some cases, we can easily afford higher security margins

[1] http://cr.yp.to/ecdh/curve41417-20140706.pdf

Jay Sullivan
  • 161
  • 1
  • 4
  • 2
    Another interesting thing to note: 256-bit symmetric ciphers have 128 quantum-bits of security, due to Grover's Algorithm. In comparison, elliptic curves and RSA's security are torn to shreds by Shor's Algorithm; using 256-bit secure asymmetric algorithms does not help secure them against quantum algorithms. – Jay Sullivan Dec 28 '16 at 17:05