Ubuntu OpenSSH vulnerability: how to update host keys

So there was a key generation weakness in Ubuntu openssh packages. The upgrade process regenerates your host keys. But now all of your other machines complain that the host key has changed. And Ubuntu hashes your known_hosts file (HashKnownHosts yes, in /etc/ssh/ssh_config), so you don't know which line to remove. Clean out your whole known_hosts file?

No. To find the hashed key, use:

ssh-keygen -F hostname
ssh-keygen -F ip_address

Remove both of the matching lines from ~/.ssh/known_hosts.

Now you're connecting to your server box and it prompts you if you want to accept the new key. Is that signature correct, or is there a man in the middle? You did keep an ssh session open to the machine while upgrading, right? So on the server, run:

ssh-keygen -l -f /etc/ssh/ssh_host_rsa_key.pub

(or _dsa_key, perhaps). If that fingerprint matches, you're set. If not, you've probably got a man in the middle. Or you just checked the fingerprint on the wrong machine ;)