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.