SSH host key seems to be changing unexpectedly

Question

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.

Solution

There are three common reasons you would be getting that message.
In rough order of probability they are:

1. 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.

2. 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.)

3. 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.

Comments

[Zoredache]

Related: serverfault.com/questions/416779/…

[Ben]

It is related, but my question is more about why this problem keeps recurring when the server's keys aren't changing, rather than what to do when I get the error.

[Ben]

Thanks for the quick answer. I believe that I can eliminate #1 and #2 because every time this happens, I eventually remove the old key and add the new key to my known_hosts file during troubleshooting, which sometimes then allows me to log in with pubkey authentication, and other times (usually from my Windows machine) it still gives me trouble. But none-the-less, I eventually get it working from everywhere, and then some period of time goes by and I get another warning like this. It does lead me to think it could be #3, but so far I don't see any evidence of it

[Ben]

And it also seems strange that this coincided with me changing the sshd config (but then changing it back--even diffing the file with the original shows no changes) and only started giving me trouble after that. I thought maybe I just screwed something up on the machine, but I've re-imaged and re-applied this configuration again (with puppet, but that should have no bearing since puppet isn't making any changes when this issue occurs) and I have the same issue at seemingly random intervals each time.

[Ben]

Another interesting piece of information (maybe) is that sometimes the error is regarding the server's RSA host key, and other times it's regarding the ECDSA host key. Is it normal that it would be checking both types of keys from the same machine?

[voretaq7]

@Ben There are other possible causes I haven't listed - but these are the three that I've actually seen in the real world. If you're certain about the configuration state try using ssh-keyscan from some of the affected client machines and check the server logs. Also note that if you're doing something funky like sharing your known_hosts file between different versions of the ssh client that could be a possible cause of this strangeness (I've never done such a thing so I can't say for sure...)

[Ben]

I'll try running ssh-keyscan next time I get this error and see if I can further narrow down what's happening (I'll see if the fingerprint returned matches one of the three keys on the server, etc). And I'm not sharing known_hosts across machines or anything like that.

[Ben]

You've helped me narrow this down. I some some additional checking and realized that the nameservers at Rackspace were returning two different records for the same hostname. I don't know where one came from, but it seemed that either one or the other IP would be returned first in the list (seemingly at random). I eventually found and eradicated the stray DNS record and haven't received this problem again since then.

[Izkata]

Comments were the clue I needed as well; I have some devices on my home network that this suddenly started happening to, turned out my router shuffled them around during DHCP refreshes after a year of being consistent.