How SSH authentication works

The first SSH client I used was PuTTY, on Windows, sometime around 2000, and the first thing it ever showed me was a dialog saying the server’s host key wasn’t cached in the registry, with a long hex fingerprint and a question about whether I trusted this host. I clicked Yes. I’ve clicked Yes, or typed yes, probably several thousand times since, and for a good fraction of them I couldn’t have told you what I was agreeing to.

The xz backdoor made me go back and actually read how this works, because the most common question I got from people on the team who aren’t security-minded was “but isn’t SSH encrypted?” It is. The backdoor didn’t break any of the cryptography. It replaced a piece of the code that checks it, and to see why that’s so bad you need to know which piece. So this is the protocol, drawn out, as of OpenSSH 9.6 and 9.7, which is what most people are running this spring.

SSH is three protocols stacked up. The transport layer (RFC 4253) sets up an encrypted channel and proves you’re talking to the right server. The user authentication layer (RFC 4252) runs inside that channel and proves to the server who you are. The connection layer (RFC 4254) runs inside that, and multiplexes shells, commands and port forwards over the one connection. Almost everything interesting happens in the first two.

Hello, and what do you speak

The client opens a TCP connection to port 22, and before anything else, both sides send a plain line of text identifying themselves, something like SSH-2.0-OpenSSH_9.6. You can see it yourself with nc against any ssh server. That line matters later, because it gets mixed into the key exchange.

Then both send a KEXINIT message, which is a set of lists: the key exchange methods I support, the host key types, the ciphers, the MACs, the compression methods, each in order of preference. The rule for picking is simple. For each category, the winner is the first algorithm on the client’s list that’s also somewhere on the server’s. Nothing is encrypted yet, so an attacker in the middle could in principle edit these lists to push both sides toward something weak. The protocol’s defense against that comes in a moment, and it’s the clever part.

Agreeing on a key

The usual key exchange today is curve25519-sha256, which is the Diffie-Hellman idea I drew out with small numbers back in 2013, done on an elliptic curve instead. Each side makes up a fresh, throwaway key pair for this connection only. The client sends its public half, Q_C. The server sends its public half, Q_S. Each combines its own private half with the other side’s public half, and they arrive at the same shared secret, K, which never crossed the wire. Someone who recorded the whole conversation has Q_C and Q_S and can’t get K from them, and since the private halves are thrown away when the connection closes, stealing the server’s disk next year doesn’t help either.

(Since OpenSSH 9.0, two years ago, the default has actually been a hybrid, sntrup761x25519-sha512@openssh.com, which does an X25519 exchange and a post-quantum one called Streamlined NTRU Prime and mixes both results. The idea is that someone recording traffic today and holding it until they have a quantum computer still has to break the classical half too. Your client is probably already using it. Run ssh -v and look for the kex: algorithm: line.)

So far this is anonymous. Both sides have a secret, but the client has no idea whether it’s sharing it with the real server or with someone in the middle who did a separate exchange with each side. That’s what the host key is for.

The host key, and the exchange hash

Along with Q_S, the server sends its long-term public host key, K_S, and a signature. What it signs is the important bit. Both sides compute an exchange hash, H, over everything that’s happened so far:

H = hash(V_C ‖ V_S ‖ I_C ‖ I_S ‖ K_S ‖ Q_C ‖ Q_S ‖ K)

That’s the two version strings, both KEXINIT messages in full, the host key, both ephemeral public keys, and the shared secret. The server signs H with its host private key. The client computes H for itself and checks the signature against K_S.

If anyone tampered with anything along the way, the algorithm lists, the version strings, the ephemeral keys, then the client’s H and the server’s H are different and the signature fails. That’s the defense against downgrades I mentioned. And because K is in the hash, a man in the middle who ran separate exchanges with each side can’t produce a valid signature over the client’s H without the server’s private host key. The signature proves two things at once: whoever is on the other end holds that host key, and they saw the same conversation you did.

The first H of a connection also becomes its session identifier, which comes up again in a minute. And all the actual encryption keys are derived from K and H by hashing them with a letter, A through F, one each for the two IVs, the two encryption keys and the two integrity keys, client-to-server and server-to-client. Then each side sends NEWKEYS and everything after is encrypted.

So what’s known_hosts for?

There’s a gap, though. The signature proves the other end holds the private key for K_S. It doesn’t prove that K_S belongs to the server you meant. In TLS, a certificate authority vouches for that. Plain SSH has no CA, so the first time you connect, your client has nothing to compare K_S against, and it asks you. That’s the PuTTY dialog, and the “authenticity of host can’t be established” prompt, and the fingerprint is a hash of K_S (these days a SHA-256 in base64). If you say yes, the key goes into ~/.ssh/known_hosts, and every later connection checks against it. If it ever changes, you get the big “REMOTE HOST IDENTIFICATION HAS CHANGED” warning with the row of @ signs.

It’s called trust on first use, and the weak point is obvious: the first use. If you’re being intercepted the first time you connect, you’ll happily save the attacker’s key. In practice you defend against it by getting the fingerprint some other way (from the console, from your cloud provider’s instance output, from a DNS SSHFP record with DNSSEC), or by using SSH host certificates, where a CA you control signs each server’s host key and your known_hosts trusts the CA instead of each key. If you’ve got more than a few dozen machines that come and go, certificates are the sane answer. We only use them for part of our fleet, and after this month the rest is on my list.

A sidebar: Terrapin

Just before Christmas, researchers at Ruhr University Bochum published Terrapin, which is a nice illustration of how subtle this layer is. SSH numbers its packets, and the integrity checks depend on those sequence numbers. They showed that during the unencrypted part of the handshake, an attacker in the middle could inject a message to shift the counters, and then quietly delete the first encrypted message, for some cipher modes (ChaCha20-Poly1305, and CBC modes with encrypt-then-MAC). The message you’d most want to delete is the one that negotiates certain security extensions. The fix in OpenSSH 9.6 is a “strict kex” mode where both sides reset their sequence numbers at NEWKEYS and refuse any unexpected message during the exchange. It needs both ends updated to take effect. I mention it because the exchange hash covers what was said, and Terrapin is about the protocol state around it, and that turned out to matter too.

Now prove who you are

With an encrypted channel to a server it trusts, the client asks for the ssh-userauth service. Passwords work, and they travel inside the encrypted channel, so they aren’t sniffable, but they’re as guessable and phishable as passwords everywhere.

Public key authentication is the one most of us use. The client sends a request saying “I’d like to log in as sijin using this public key”. The server can answer whether it would accept that key at all, which lets the client try keys one at a time without signing anything. Then the client sends the real request, with a signature made by its private key over the session identifier, the username, the service name and the public key itself.

That session identifier is what makes this safe against replay. The signature is only valid for this connection’s H, which depended on fresh random keys from both sides, so a signature captured from one session is useless in any other. The server never sees your private key, and neither does anyone who compromised the server later. What the server does is look the public key up in ~/.ssh/authorized_keys for that user (or check that it’s a user certificate signed by a CA it trusts, which is the user-side version of the host certificates above), verify the signature, and if both pass, send USERAUTH_SUCCESS.

After that it’s the connection protocol: channels for your shell, for scp, for port forwards, for agent forwarding if you turned it on (which lets the server ask your local agent to sign things on your behalf, which is exactly as much trust as it sounds like, so only turn it on for servers you’d trust with your key).

Where xz hooked in

Back to the red box in the diagram.

Upstream OpenSSH doesn’t use liblzma. On Debian, Ubuntu, Fedora and their relatives, sshd is patched to notify systemd when it’s ready, that pulls in libsystemd, and libsystemd pulls in liblzma. So on those systems, the backdoored library was loaded into the sshd process, running as root, at startup. In Andres Freund’s write-up, the malicious code used a feature of the dynamic linker to redirect one function sshd calls, RSA_public_decrypt from OpenSSL. That function is part of how sshd checks an RSA signature, and it gets called during user authentication, when a client presents an RSA key or a certificate signed with one.

From the public analysis since: the replacement looks at what the client presented, and checks whether it carries a command signed with an Ed448 key that only the attacker holds. If it doesn’t, it hands off to the real function, and everything behaves normally, which is why nobody noticed anything except a half-second delay. If it does, it runs the command, as root, before authentication has finished.

That’s what I tried to explain to the person who asked “but isn’t SSH encrypted?” Everything above the red box worked perfectly. The key exchange was fine, the host key was real, the channel was encrypted with keys nobody else had. The attacker didn’t need to break any of it, because they were on the other end of it, inside the program doing the checking. The protocol’s guarantees are all of the form “if the server’s code is the server’s code”. And the gating with the attacker’s own key means it wasn’t a hole anyone could use. It was a door with one key, which is about the most careful piece of supply-chain work I’ve ever read about.