So you ssh to a usual machine and get:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
3f:d6:e7:72:9a:ab:4e:e1:21:91:3a:88:6b:78:83:ce.
Please contact your system administrator.
Add correct host key in /Users/username/.ssh/known_hosts to get rid of this message.
Offending key in /Users/username/.ssh/known_hosts:73
RSA host key for localhost has changed and you have requested strict checking.
Host key verification failed.
It's worrying.... Has someone hacked my machine (again!?). Or am I being paranoid for the 13th time this week?
This error is due to a mismatch between the RSA key that you already have stored on your machine in the /Users/username/.ssh/known_hosts file, and the one that ssh has just obtained over the network on this login attempt. Note: newer versions of ssh now store hashes of hostnames (see: ssh-keygen -H) in the known_hosts file to maintain privacy. Either the ssh server key has been changed legitimately (by you or some admin) or it's been hacked. It's also possible that someone on has set up a machine on the same IP address as the server you're trying to contact then you'll find you can't login - in which case you (or some admin) needs to track down the rogue machine.
To check the key is correct login to the machine in question - preferably on the console, but if you're connecting via ssh then you'll have to ignore the warnings above. Then you can directly print your server's key's fingerprint. There are a few types of keys: RSA, DSA, ECDSA (for SSHv2), and RSA for SSHv1. If your on a 'standard' Linux box then it's probably at: /etc/ssh/ssh_host_rsa_key.pub (or for DSA /etc/ssh/ssh_host_dsa_key.pub). If you're on a Mac OSX it is in: /etc/ssh_host_rsa_key.pub (or /etc/ssh_host_key.pub or /etc/ssh_host_dsa_key.pub). e.g. So on a Mac OSX box try:
% ssh-keygen -l -f /etc/ssh_host_rsa_key.pub
2048 3f:d6:e7:72:9a:ab:4e:e1:21:91:3a:88:6b:78:83:ce. /etc/ssh_host_key.pub
The key fingerprint (of the corresponding key type - in this case RSA) should match the one shown above. If these don't match then something fishy is going on....
Also just for info you can list all the fingerprints of all your stored host keys
% ssh-keygen -l -f .ssh/known_hosts
Instead you can just compare the public keys stored on your client in ~/.ssh/known_hosts with the keys on the server in /etc/ssh/ssh_host_*.pub
It is also possible that if you've upgraded your version of ssh (or altered your ssh-agent setup), and your machine has previously stored an RSA key in your ~/.ssh/known_hosts file but it is now getting an ECDSA key from the server which obviously won't match but may still be a valid key for that machine. It seems that ssh could work out this problem for itself without any lack of security but currently can lead to such warnings.
[22jan16: Updated to simplify and include ECDSA keys]