How to roll over ssh host keys?

Question

I'm trying to upgrade my ssh server from 2048-bit RSA keys to larger keys, as recommendations are to phase out 2048-bit keys soon.

I generated a new key, then added it to the sshd config, like this:

HostKey /etc/ssh/ssh_host_rsa_key            (old 2k-bit key first)
HostKey /etc/ssh/ssh_host_rsa4096_key        (new larger key 2nd)

After restarting sshd, I ssh'd to the host, I don't get the identification changed warning, however the new also isn't cached in ~/.ssh/known_hosts. If I put the lines in the opposite order, I get the identification changed warning. Similarly, when I add an ed25519 key, no matter what order I put it in, the client doesn't add the new key to the known hosts file.

This seems to make SSH host key rollover impossible—difficult to believe that's really the case, though, considering security routinely requires upgrading keys.

I know you can just swap the key, then every client needs to run ssh-keygen -R to remove the old key, then manually verify and accept the new key—but that's a real pain, especially if you have a lot of clients connecting or don't administer all the clients. Not to mention, if you don't administer the clients, there is a very good chance they won't actually check the host key and instead just hit Y—so the attempt to improve security will likely actually open you to man-in-the-middle attacks instead.

Is there some way to make SSH host key upgrades work? That is, clients should learn the new more secure key (and also hopefully un-learn the obsolete key). And without giving the host key changed man-in-the-middle warning.

Answer 1

The Host Key rotation is supported since OpenSSH 6.8 (both client and server adds support in this version).

So the process should work like this:

• Generate and add new keys with the option HostKey newkey (after the existing ones) to the /etc/ssh/sshd_config
• Restart sshd
• The clients have to set up UpdateHostKeys yes in their configuration (either globally, or per-host)
• The connecting clients will pick up all the new keys
• After some time (months?) you can remove the old keys from the sshd_config and restart sshd
• The clients (that connected during the transition period) will already have the new keys (the old will not be removed, which is the only problem here) and they will not show the MitM attack warning.

The new enough-clients will be able to pick up the new keys. This feature is not enabled by default, probably because it is quite new and soon showed some security consideration. But these days, it should be fine to use it.

Answer 2

sshd always use the first line, so delete it, then restart sshd.