ECDSA vs ECDH vs Ed25519 vs Curve25519

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

ECDH is for key exchange (EC version of DH)

ECDSA is for signatures (EC version of DSA)

Ed25519 is an example of EdDSA (Edward's version of ECDSA) implementing Curve25519 for signatures

Curve25519 is one of the curves implemented in ECC (most likely successor to RSA)

The better level of security is based on algorithm strength & key size
eg. Ed448 ciphers have equivalent strength of 12448-bit RSA keys

An algorithm NTRUEncrypt claims to be quantum resistant, and is a lattice-based alternative to RSA and ECC.