I rolled out a new /etc/ssh/sshd_config with Puppet on an Ubuntu 12.04 test server. The config was exactly the same as the previous config, except it had removed the following line:
HostKey /etc/ssh/ssh_host_ecdsa_key
I noticed I was getting a lot of similar but varying errors trying to connect to the box starting then, such as:
"The RSA host key for %hostname% has changed,
and the key for the corresponding IP address %ipaddress%
is unchanged."
I assumed this was because my computer was previously using the ECDSA key by default and that was unavailable now. So I added that line back to sshd_config and restarted SSH.
It did not resolve the issue entirely, and I am running into constant problems ever since then. I'll be able to connect to the server just fine several times, maybe even for several days in a row. Then all of a sudden I start getting errors that the host key has changed and the server stops accepting my public key for authentication.
It always seems that once I mess around with it for a little while and connect from a different location, I will suddenly be able to connect with my public key again and I no longer get the error about a possible man-in-the-middle attack.
I tried regenerating all 3 host keys several days ago (removed them and ran dpkg-reconfigure openssh-server which regenerated them). As expected I had to remove the old keys and accept the new ones before I could connect. I thought maybe it was fixed then, but the problem is now back.
Nothing has modified any of the host keys in /etc/ssh/ since I regenerated them last–so what could possibly cause me to frequently not be able to connect, have my public key not work, then eventually accept the new key and have things start working fine again for a while?
When things are not working (when I get the error about the host key changing, and then the server stops accepting my public key), nothing is written to the server's /var/log/auth.log. This leads me to think that maybe it's somehow hitting a different machine sometimes, but I don't know how that's possible either as the DNS entry is correct and always returns the same IP address.
Best Answer
There are three common reasons you would be getting that message.
In rough order of probability they are:
You have changed the host keys yourself, and didn't clear or update them on your client machines.
This is the most common situation. Checksum the key files and be ABSOLUTELY CERTAIN they haven't changed.
You have changed your SSH configuration to present (or request) a different key type than before.
e.g. you previously wanted RSA or DSA keys, now you use ECDSA -- that's a "key change".
If this is the case, verify and accept the new keys (or if this isn't what you wanted, undo the change).
(It sounds like you're in situation #2 -- Undo your changes, restart sshd, and verify that things work as expected. If you haven't accepted the new keys anywhere undoing the change should make the error go away.)
SOMEONE IS DOING SOMETHING NASTY
The Man-in-the-Middle attack SSH warns you about has reared its ugly head. Someone is actively trying to intercept your communication to steal your private key or do something else you almost certainly don't want them to be doing.
If you've eliminated 1, and you are certain you didn't do 2, it behooves you to assume 3 until you can prove otherwise. That means Don't log in. -- All the SSH security in the world doesn't help when users ignore the big giant warning banner and hand their keys over to attackers.
Investigate the channel between you and your server, check the server's connection logs (from a known good terminal) while you try to log in, etc. -- there are so many ways to execute an attack here that I can't enumerate all the possible countermeasures and detection strategies, but the folks over at IT Security would surely have some ideas.