Hostkey rotation, redux

A couple of weeks ago I described the host key rotation support forthcoming in OpenSSH 6.8. Almost immediately after smugly declaring "mission accomplished", the bug reports started rolling in. First Mike Larkin noticed an interaction with ssh's CheckHostIP option that would cause host key warnings, then Theo de Raadt complained about the new code unnecessarily rewriting known_hosts when no changes needed to be made, finally Philipp Kern and Jann Horn pointed out a way for a hostile server to abuse the extension.

Given all this, I disabled the feature and went back to the drawing board. Host keys handling has long been one of my least favourite parts of OpenSSH - the code is poorly tested, mistakes might catastrophically break host authentication and there are lots of overlapping and interacting features (e.g. host key hashing, the aforementioned CheckHostIP, host with port specifiers, CA / revocation markers). So my first task was to improve the API to make it possible to solve the CheckHostIP interactions and add some sorely-needed unit tests for it (well, at least of the code that I was going to be fiddling with).

The abuse problem was more tricky - the attack was:

a malicious server (say, "host-a") could advertise the public key of another server (say, "host-b"). Then, when the client subsequently connects back to host-a, instead of answering the connection as usual itself, host-a could proxy the connection to host-b. This would cause the user to connect to host-b when they think they are connecting to host-a, which is a violation of the authentication the host key is supposed to provide.

The fix for this is to have the server prove to the client that it has the private keys that correspond to the public keys that it offers. Unfortunately, this is a little fiddly since we don't want to have to calculate and send signatures for each of a server's host keys on every connection (it's slow and expensive) and we can't precompute the signatures (otherwise a hostile server could just replay them and the above attack is back on). So I settled on a way for a client to ask the server to prove ownership of particular keys, allowing a flow like this:

S->C: hostkeys@openssh.com; list of public hostkeys
Client: Check known_hosts, see which keys are new
C->S: hostkeys-prove@openssh.com; new keys server must prove ownership of
S->C: (reply); private key signature for each key

The signatures proving ownership of the private keys are bound to the specific connection instance, so they cannot be replayed. Unfortunately, this means that the hostkeys rotation support is a little less useful: it is not longer possible to offer public keys without having their private halves online to complete the proofs. I hope to bring this capability back in a future release, perhaps by (ab)using the certificate format to allow pre-computed proofs that are tied to specific hostnames.

The host key proof extensions are now committed to HEAD. I also added a UpdateHostKeys=ask mode that prompts the user for confirmation before modifying known_hosts, since that seemed reasonable and symmetric with StrictHostkeyChecking=yes. Anyway, if you are interested in this then please try out HEAD and/or review the code or protocol specification.

Key rotation in OpenSSH 6.8+

Update: Two things that I neglected to mention in the above: 1) host keys that are not offered as part of the server->client notification are automatically removed from known_hosts, and 2) the updating of known_hosts can be disabled using a new UpdateHostkeys option in ssh_config and ~/.ssh/config.

Update 2: Jann Horn (after Philipp Kern) points out that a malicious server (say, "host-a") could advertise the public key of another server (say, "host-b"). Then, when the client subsequently connects back to host-a, instead of answering the connection as usual itself, host-a could proxy the connection to host-b. This would cause the user to connect to host-b when they think they are connecting to host-a, which is a violation of the authentication the host key is supposed to provide. The solution for this is for the server to prove to the client that server is in possession of the private key as well as the public. I'll add this before release (or delay the feature), but it's going to make the key rotation more onerous.

Update 3: (last one, promise). See the follow-up post.

Something that's bugged me about the SSH protocol is its lack of key continuity - key algorithm changes and key rotations are basically unsupported, as there is no in-protocol way for a client to learn updated host keys for hosts that the user already trusts. About the best one can do is cat /etc/ssh/*.pub once logged in to manually learn the host's other keys, but this only works if you have shell access and is a kludge anyway...

This makes it difficult for users to switch away from weak public key algorithms like ssh-dss to stronger ones and makes it practically impossible for a host to gracefully rotate its hostkeys. (I'm ignoring host certificates here, which do solve the problem but are mostly useful within an organisation).

These problems have become more urgent as the DSA supported in the SSH protocol has not aged gracefully, being within the range of a motivated attacker now. OpenSSH has preferred other host key algorithms for over 14 years, but it is the only "REQUIRED" public key algorithm in the SSH transport protocol (RSA was only "RECOMMENDED" because its patent hadn't expired back when they were written, and ECDSA was still future-tech), so people who have maintained systems for long periods of time could still be using this crappy algorithm today.

I've wanted the SSH protocol to provide a way to get users onto better host key algorithms for a while and finally got around to implementing it a couple of weeks ago: OpenSSH 6.8 will ship with a protocol extension that allows a server to inform a client of all of its host keys, and support in the client to update known_hosts when such a message is received. So, when an OpenSSH ≥6.8 client connects to a OpenSSH ≥6.8 server (or any other client/server that adopts the extension) where the user already trusts or explicitly accepts the host key, the user's known_hosts file will be updated with all the server's host keys, not just the one that authenticated the host during key exchange.

This fixes both the shortcomings I mentioned above: first, the client learns all the server's host key types, and can select the best possible host key algorithm (ed25519 is our current favourite) on subsequent connections. Secondly, it allows a server to gracefully rotate keys by publishing additional keys for a period to allow clients to learn them, before removing the deprecated key(s) and letting the new ones become the primary ones.

To practically rotate host keys, the operator of a sshd server should add additional HostKey statements to their sshd_config for the new keys, while keeping the existing keys in place. I.e.

# Old keys
HostKey /etc/ssh/ssh_host_ed25519_key
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_dsa_key
# New keys
HostKey /etc/ssh/ssh_host_ed25519_key_new
HostKey /etc/ssh/ssh_host_rsa_key_new
HostKey /etc/ssh/ssh_host_ecdsa_key_new

Once these lines are added, sshd can be restarted to begin offering the new keys to clients who connect. The old keys, appearing first in the configuration, will be the ones actually used to authenticate the host to the client. Once the operator is satisfied that enough users have had a chance to pick up the new keys, they can rename replace the original keys with the new keys and remove the extra HostKey lines from sshd_config.

This mechanism isn't perfect: first, it only works for users who actually connect to the server - if they don't happen to connect during the grace period when both old and new keys are offered then they will have to learn the new key manually afterwards. As such, it doesn't cope well with sudden key rotations (e.g. when the operator has reason to believe a key has been compromised).

Fortunately both these cases can be addressed with a bit of forethought: when setting up a server, generate some reserve keys. Keep their private halves offline (e.g in a safe), but list them in sshd_config as described above. OpenSSH ≥6.8 will notify clients of the reserve public keys on every connection, so if you ever need to rotate keys in a hurry then they are already ready to go. You could generate multiple sets of reserve keys if you like - you aren't limited to a single set.

The host key rotation support is in OpenBSD -current and the git HEAD version of portable OpenSSH. Please try it out!

If you implement SSH yourself and want to add the extension to your own software, then setails of the protocol extension are in the PROTOCOL file in the source distribution. It's trivial though: a global request hostkeys@openssh.com, sent once after authentication completes containing one or more public key blobs encoded as strings. In my biased opinion, its a small, easy to implement tweak to the SSH protocol that provides a significant improvement to the protocol.