99

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.

  • 14
    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
92

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.

  • 93
    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
  • 21
    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
  • 11
    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
73

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

  • "One of the more interesting security benefits is that it is immune to several side channel attacks" - To state the obvious, that depends on the implementation. Bernstein team's code, Adam Langley's code, Andrew Moon's code (et al) should be OK. But I don't think you can say the same for an arbitrary implementation. – jww Feb 8 at 11:49
  • I guess it would be more precise to say, the design of the algorithm makes it possible to implement it without using secret array indices or branch conditions. Of course you're right that it would still be possible to implement it poorly. – Brian Minton Feb 8 at 13:00
36

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).

34

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.

2

Something that no answer so far addressed directly is that your questions mixes several more or less unrelated names together as if these were equivalent alternatives to each other which isn't really the case.

ECDH and ECDSA are just names of cryptographic methods.

ECDH is a key exchange method that two parties can use to negotiate a secure key over an insecure communication channel. It's a variation of the DH (Diffie-Hellman) key exchange method. ECDH stands for Elliptic-curve Diffie–Hellman. Yet ECDH is just a method, that means you cannot just use it with one specific elliptic curve, you can use it with many different elliptic curves.

ECDSA is a signature algorithm that can be used to sign a piece of data in such a way, that any change to the data would cause signature validation to fail, yet an attacker would not be able to correctly re-sign data after such a change. It is a variation of DSA (Digital Signature Algorithm). ECDSA stands for Elliptic Curve Digital Signature Algorithm. Also ECDSA only describes a method which can be used with different elliptic curves.

The security of ECDH and ECDSA thus depends on two factors:

  1. How secure is the method itself? If the method isn't secure, the best curve in the word wouldn't change that.
  2. How secure is the curve being used? If the curve isn't secure, it won't play a role if the method theoretically is.

Curve25519 is the name of a specific elliptic curve. Other curves are named Curve448, P-256, P-384, and P-521.

Ed25519 is the name of a concrete variation of EdDSA. When performing EdDSA using SHA-512 and Curve25519, this variation is named Ed25519. EdDSA is a signature algorithm, just like ECDSA.

So if an implementation just says it uses ECDH for key exchange or ECDSA to sign data, without mentioning any specific curve, you can usually assume it will be using the NIST curves (P-256, P-384, or P-512), yet the implementation should actually always name the used curve explicitly.

To answer your question about security: ECDH and ECDSA have pretty much been proven to be conceptional secure key exchange and signing methods, thus the security of ECDH and ECDSA pretty much depends on the fact if someone finds a way how to break elliptic cryptography in general (little likely but not impossible) or to find a flaw within the curves being used (more likely).

The reason why some people prefer Curve25519 over the NIST standard curves is the fact, that the NIST hasn't clearly documented why it has chosen theses curves in favor of existing alternatives. The generic statement "The curves were ostensibly chosen for optimal security and implementation efficiency" sounds a lot like marketing balderdash and won't convince cryptographic experts.

The NIST also standardized a random number generator based elliptic curve cryptography (Dual_EC_DRB) in 2006 and the New York times claimed (after reviewing the memos leaked by Edward Snowden) that it was the NSA influencing the NIST to standardize this specific random number generator. A huge weaknesses has been discovered in that generator and it is believed that it is an intentional backdoor placed by the NSA to be able to break TLS encryption based on that generator. The ANSI apparently discovered the weakness when Dual_EC_DRB was first submitted to them but despite being aware how to avoid it, they did neither improve the algorithm, nor did they publicize the weaknesses, so it is believed that they weren't allowed to (gag order). When the weakness became publicly known, the standard was withdrawn in 2014.

With that background knowledge, of course, people started to wonder if maybe the source of the mysterious NIST curve parameters is in fact also the NSA as maybe these curves have also hidden weaknesses that are not publicly known yet but the NSA may know about them and thus be able to break cryptography based on these curves. There is no evidence for that claim, not even a presumptive evidence but it surely seems possible and more realistic than a fairy tale. That's why people lost trust into these curves and switched to alternatives where it is highly unlikely, that these were influenced by any secret service around the world.

Curve25519 was published by the German-American mathematician and cryptologist Daniel J. Bernstein in 2005, who also designed the famous Salsa20 stream cipher and the now widely used ChaCha20 variant of it. He also invented the Poly1305 message authentication. Google decided that ChaCha20 in combination with Poly1305 is a secure alternative to be used in TLS after RC4 had to be removed because the algorithm has been broken. It requires much less computation power than using the AES block chipher (very useful for mobile devices as it saves battery runtime), yet is believed to provide comparable security. ChaCha20/Poly1305 is standardized in RFC 7905 and widely used today in TLS client-server communication as of today. So if Bernstein was a NSA spy, which is very unlikely, we'd all be doomed already as then TLS as it is often used today would probably be useless to protect data from the eyes of secret services.

  • Although ECDSA can be used with multiple curves, it is not in fact used with Bernstein's. Ed25519 and Ed448 are instances of EdDSA, which is a different algorithm, with some technical advantages. And in OpenSSH (as asked) the command option ssh-keygen -t ecdsa and default filename id_ecdsa* don't specify the curve, but the actual key (contents) including on the wire and in known_hosts etc do; see rfc5656. Including nistP-521, not P-512 which does not exist. – dave_thompson_085 Jun 10 at 16:30
  • @dave_thompson_085 I never claimed that ECDSA is used with Bernstein's. I never claimed that openSSH specifies a curve. So please refrain from commenting things I've never written. And P-512 was clearly a typo just like ECDSA for EdDSA, after all I wrote a lot of text, so typos just happen. – Mecki Jun 11 at 16:02
  • I just wanted to point out that you have a typo in the revision description where you misspelled "annoying nitpickers." 🌵 – Michael Jun 14 at 17:33

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.