Among the ECC algorithms available in openSSH (ECDH, ECDSA, Ed25519, Curve25519), which offers the best level of security, and (ideally) why?

migrated from superuser.com Feb 4 '14 at 9:58

This question came from our site for computer enthusiasts and power users.

  • 13
    That's a pretty weird way of putting it. Curve25519 is one specific curve on which you can do Diffie-Hellman (ECDH). Diffie-Hellman is used to exchange a key. Ed25519 and ECDSA are signature algorithms. – CodesInChaos Feb 4 '14 at 10:36
  • related: SSH Key: Ed25519 vs RSA – maxschlepzig Sep 29 '16 at 8:01
  • 1
    Also see Bernstein's Curve25519: new Diffe-Hellman speed records. He seems to do a pretty good job and answers a lot of your questions. – jww Oct 15 '16 at 8:49
up vote 82 down vote accepted

In SSH, two algorithms are used: a key exchange algorithm (Diffie-Hellman or the elliptic-curve variant called ECDH) and a signature algorithm. The key exchange yields the secret key which will be used to encrypt data for that session. The signature is so that the client can make sure that it talks to the right server (another signature, computed by the client, may be used if the server enforces key-based client authentication).

ECDH uses a curve; most software use the standard NIST curve P-256. Curve25519 is another curve, whose "sales pitch" is that it is faster, not stronger, than P-256. The performance difference is very small in human terms: we are talking about less than a millisecond worth of computations on a small PC, and this happens only once per SSH session. You will not notice it. Neither curve can be said to be "stronger" than the other, not practically (they are both quite far in the "cannot break it" realm) nor academically (both are at the "128-bit security level").

Even when ECDH is used for the key exchange, most SSH servers and clients will use DSA or RSA keys for the signatures. If you want a signature algorithm based on elliptic curves, then that's ECDSA or Ed25519; for some technical reasons due to the precise definition of the curve equation, that's ECDSA for P-256, Ed25519 for Curve25519. There again, neither is stronger than the other, and speed difference is way too small to be detected by a human user. However most browsers (including Firefox and Chrome) do not support ECDH any more (dh too).

Using P-256 should yield better interoperability right now, because Ed25519 is much newer and not as widespread. But, for a given server that you configure, and that you want to access from your own machines, interoperability does not matter much: you control both client and server software.

So, basically, the choice is down to aesthetics, i.e. completely up to you, with no rational reason. Security issues won't be caused by that choice anyway; the cryptographic algorithms are the strongest part of your whole system, not the weakest.

  • 83
    The "sales pitch" for 25519 is more: It's not NIST, so it's not NSA. Not speed. – Martin Schröder Feb 5 '14 at 10:02
  • 15
    Actually, it's very much speed as well. Well constructed Edwards / Montgomery curves can be multiple times faster than the established NIST ones. imperialviolet.org/2010/12/21/eccspeed.html – Ivo Feb 7 '14 at 12:51
  • 3
    In fact, if you really want speed on a recent PC, the NIST-approved binary Koblitz curves are even faster (thanks to the "carryless multiplication" opcode which comes with the x86 AES instruction); down to something like 40000 cycles for a generic point multiplication in K-233, more than twice faster than Curve25519 -- but finding a scenario where this extra speed actually makes a noticeable difference is challenging. – Tom Leek Feb 7 '14 at 12:57
  • 17
    More "sales pitch" comes from this IETF draft: While the NIST curves are advertised as being chosen verifiably at random, there is no explanation for the seeds used to generate them. In contrast, the process used to pick these curves is fully documented and rigid enough so that independent verification has been done. This is widely seen as a security advantage, since it prevents the generating party from maliciously manipulating the parameters. – ATo Aug 21 '16 at 7:25
  • 10
    According to DJB's safecurves.cr.yp.to website, the NIST curve may not be as safe or foolproof as the Curve25519. – Totor Nov 9 '16 at 14:49

From the Introduction to Ed25519, there are some speed benefits, and some security benefits. One of the more interesting security benefits is that it is immune to several side channel attacks:

  • No secret array indices. The software never reads or writes data from secret addresses in RAM; the pattern of addresses is completely predictable. The software is therefore immune to cache-timing attacks, hyperthreading attacks, and other side-channel attacks that rely on leakage of addresses through the CPU cache.
  • No secret branch conditions. The software never performs conditional branches based on secret data; the pattern of jumps is completely predictable. The software is therefore immune to side-channel attacks that rely on leakage of information through the branch-prediction unit.

For comparison, there have been several real-world cache-timing attacks demonstrated on various algorithms. http://en.wikipedia.org/wiki/Timing_attack

I was under the impression that Curve25519 IS actually safer than the NIST curves because of the shape of the curve making it less amenable to various side channel attacks as well as implementation failures. See: http://safecurves.cr.yp.to

Ed25519 has the advantage of being able to use the same key for signing for key agreement (normally you wouldn't do this). I am not well acquainted with the mathematics enough to say whether this is a property of it being an Edwards curve, though I do know that it is converted into the Montgomery coordinate system (effectively into Curve25519) for key agreement... Ed25519 is more than a curve, it also specifies deterministic key generation among other things (e.g. hashing) , worth keeping in mind. This is a frustrating thing about DJB implementations, as it happens, as they have to be treated differently to maintain interoperability.

There is an important practical advantage of Ed25519 over (EC)DSA: The latter family of algorithms completely breaks when used for signatures together with a broken random number generator. Such a RNG failure has happened before and might very well happen again.

Theoretically, implementations can protect against this specific problem, but it is much harder to verify that both ends are using a correct implementation than to just prefer or enforce (depending on your compatibility needs) an algorithm that explicitly specifies secure behavior (Ed25519).

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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