tl;dr: This article is about the keys that are used for authentication in the SSH protocol – in particular it is about Ed25519, which is a fast and secure elliptic-curve signature algorithm.

The Secure Shell (SSH) protocol is the most widely used approach for securely logging into and administering remote servers. SSH was invented by Tatu Ylonen in 1995 and has been standardized in The Secure Shell (SSH) Protocol Architecture (RFC4251), which consists of three parts:

  1. The Secure Shell (SSH) Transport Layer Protocol (RFC4253) for server authentication, confidentiality, and integrity. Usually the SSH transport layer protocol will be run over TCP/IP.
  2. The Secure Shell (SSH) Authentication Protocol (RFC4252) for authenticating a client to a server. It runs over the SSH transport layer protocol.
  3. The Secure Shell (SSH) Connection Protocol (RFC4254). It provides interactive login sessions, remote execution of commands, forwarded TCP/IP connections, and forwarded X11 connections. All of these channels are multiplexed into a single encrypted tunnel.

In order to work, SSH needs three kinds of cryptographic algorithms:

  1. A signature algorithm, which is used by the client to verify that it is connecting to the right server, and which may be used by the client to authenticate to a server (instead of just providing a user name and password).
  2. A key exchange algorithm, which is used to negotiate a symmetric key for encrypting data between client and server during an SSH session. For that two schemes are available: Diffie-Hellman-Merkle or ECDH, where the latter is an elliptic-curve-based variant of Diffie-Hellmann-Merkle.
  3. A symmetric cipher, which is used to encrypt the data between client and server once the key exchange and authentication is complete.

We won't go into the details of key exchange algorithms and symmetric ciphers here, but instead focus on the signature algorithms in SSH.

Signatures for SSH Client Authentication

Within the SSH Authentication Protocol, one central element is the key that a client uses to authenticate to a server. Such a key is asymmetric, i.e., it consists of a private/public key pair and the private key is only known to the client.

”An authentication system prevents the unauthorized injection of messages into a public channel, assuring the receiver of a message of the legitimacy of its sender.”
— Whitfield Diffie and Martin Hellmann, 1976

For the sake of completeness, we should mention that an SSH server has to have its own private/public key pair too, of course, so that clients can also verify that they are connecting to the right server during the transport layer establishment.

In simple terms, when a client wants to authenticate with a key (and not with a password) to an OpenSSH server, the following happens:

  1. A prerequisite is that both client and server have already established an SSH transport layer connection, i.e., server authentication has already been performed and both client and server have negotiated a shared session key according to the SSH Transport Layer Protocol (RFC4253).
  2. In the first optional (but very typical) step, the client will offer one or more IDs of its keys to the server by sending its user name together with key fingerprints to the server.
  3. The server searches the authorized_keys2 file of that user name for the key ID(s).
  4. If the offered key ID matches, the server responds with an acknowledgement.
  5. At this time, the user behind the SSH client will typically be required to enter his or her password for the corresponding private key (because it is generally a very good idea to locally encrypt all your private key files).
  6. The client then compiles a user authentication request that comprises of the user name, the public key algorithm name, the public key to be used for authentication, and a signature. The value of this signature is a signature by the corresponding private key over the following data: the session identifier of the current SSH transport layer session, the user name, the service name, the public key algorithm name, and the public key to be used for authentication.
  7. The server verifies that the signature in the user authentication request is correct, i.e., that the signature matches the public key of the user.
  8. Iff the signature is correct, then the client is authenticated and the server sends an acknowledgement back to the client.

After that, typically the SSH Connection Protocol (RFC4254) is used to establish an interactive login session, or open a tunnel, etc.

At the time of this writing, OpenSSH 8.0 supports four different types of signatures:

  • rsa
  • dsa
  • ecdsa
  • ed25519

The probably more widely known signature types are RSA and DSA.

RSA is named after its inventors Rivest, Shamir, and Adleman and was published in the seminal paper A method for obtaining digital signatures and public-key cryptosystems in 1978. It is a widely used asymmetric cryptographic system, that can be used to both encrypt and/or sign messages.

”The era of 'electronic mail' may soon be upon us”
— Ron Rivest, Adi Shamir, and Leonard Adleman, 1978

For example, you can generate yourself a 4096-bit SSH key of type rsa with 200 rounds for the key derivation function via the following command:

# The following command is for illustration only, read on for ed25519
ssh-keygen -t rsa -b 4096 -a 200 -C "me@host" -f ~/.ssh/my_new_id_rsa

Just in case you have never heard of using a key derivation function (KDF) for your keys: look it up now, it is important for protecting your keys, should they ever get stolen.

DSA, the Digital Signature Algorithm, is another signature algorithm that is based on private/public key pairs and which was adopted by the U.S. Department of Commerce in the Federal Information Processing Standards Publication no. 186 in 1994. However, DSA is not considered secure any more and should not be used. Also, if you use your DSA key to sign a message on a machine that has a weak random number generator and someone is sniffing enough of your traffic then your private key can be derived by the attacker.

The other two key types ECDSA and Ed25519 are based on elliptic curves.

ECDSA, the Elliptic Curve Digital Signature Algorithm, is based on a proposal by John C. Anderson in the Communications of the ACM: Responses to NIST's proposal in 1992, which was adopted as an ISO standard (ISO/IEC 14888-3:1998) and ANSI standard (ANSI  X9.62) in 1998. The National Institute of Standards and Commerce (NIST), which is part of the U.S. Department of Commerce, also adopted ECDSA in the Federal Information Processing Standards Publication no. 186-2 in 2000. NIST also proposed a special curve for ECDSA, called P-256, which some people still consider suspicious.

To cut a long story short: ECDSA suffers from the same random number risk as DSA — a weak random number generator for message signing endangers the private key. The company Sony had to experience this painfully in 2010: they used a static (!) "random" number for their ECDSA implementation in the Playstation 3. That signature was intended to sign applications for the console and someone managed to retrieve the private key. If you are interested in the details of the PS3 hack, then watch the video of the original talk at 27c3. Of course, ECDSA itself is not a bad signature. It just requires you to take very good care of your random number generators on every machine where you use your key.

This brings us to Ed25519.

Ed25519

Ed25519 is a public-key signature algorithm that was proposed by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang in their paper High-speed high-security signatures (doi.org/10.1007/s13389-012-0027-1) in 2011. More precisely, Ed25519 is an instance of the Edwards-curve Digital Signature Algorithm (EdDSA), where a twisted Edwards curve birationally equivalent to the curve called Curve25519 is used. Curve25599 is a very fast elliptic-curve-Diffie-Hellmann function that was proposed by Daniel J. Bernstein in his paper Curve25519: new Diffie-Hellman speed records in 2006.

For the mathematically interested: the Curve25519 function is $F_{p^2}$-restricted $x$-coordinate scalar multiplication on $E(F_{p^2})$, where $p$ is the prime number $2^{255} − 19$ and $E$ is the elliptic curve
$$y^2 = x^3 + 486662x^2 + x$$

Hence the name Curve25519.

There are several aspects that make Ed25519 appealing for authentication in SSH:

  • Ed25519 is considered to be secure (similar difficulty to breaking a ~3000-bit RSA key).
  • Creating a new signature with Ed25519 does not require a random input. This is very desirable from a security perspective (see the Playstation3 hack above...).
  • Ed25519 is resilient to hash-function collisions. This is good because it provides some additional protection in case the selected hash function contained some weakness.
  • Ed25519 is immune to cache-timing attacks, hyperthreading attacks, and other side-channel attacks that rely on leakage of addresses through the CPU cache. This is also very desirable from a security perspective.
  • Ed25519 does not use secret branch conditions, i.e., it is immune to side-channel attacks that rely on leakage of information through the branch-prediction unit.

See the original paper for more details on the advantages of Ed25519. For example, Ed25519 is also a very fast signature algorithm, the keys and signatures a very small etc. — this is not so important for interactive SSH logins, but very crucial for other application domains such as web servers.

However, one very common question is:

”Wouldn't it be better to use 4096-bit RSA instead of Ed25519?”

The short answer to this is: as long as the key strength is good enough for the foreseeable future, it doesn't really matter. Because here we are considering a signature for authentication within an SSH session. The cryptographic strength of the signature just needs to withstand the current, state-of-the-art attacks.

If someone managed to break an Ed25519 (or RSA, DSA, ECDSA) key today, the attacker could start impersonating the SSH client or server, of course. However, the attacker could not decrypt past SSH sessions, because these session keys have been negotiated by an ephemeral Diffie-Hellman-Merkle key exchange, which provides Perfect Forward Secrecy.

To summarize: Ed25519 is a modern and secure public-key signature algorithm that brings many desirable features, in particular the resistance against several side-channel attacks.

So, how to generate an Ed25519 SSH key?

$ ssh-keygen -t ed25519 -a 200 -C "you@host" -f ~/.ssh/my_new_id_ed25519

Make sure to use a strong password for your private key!

The parameter -a defines the number of rounds for the key derivation function. The higher this number, the harder it will be for someone trying to brute-force the password of your private key — but also the longer you will have to wait during the initialization of an SSH login session.

If you also run an SSH server, you can use the same command to generate an ed25519 host key on your server (and then place the key under /etc/ssh/ and add it to your /etc/ssh/sshd_conf).

Mozilla's Infosec group has summarized some good OpenSSH configuration tips here: https://infosec.mozilla.org/guidelines/openssh

Notes:

[1]: In 2002, Martin E. Hellman wrote in the IEEE Communications Magazine:
”The system I called the ax1x2 system in this paper has since become known as Diffie-Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie-Hellman-Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle’s equal contribution to the invention of public key cryptography. Space does not permit an explanation of the quirk of fate that seems to have deprived Merkle of the credit he deserves, but a quirk it is.”

References:

Photo by lum3n.com