The first thing I will say is ouch. The typical reasons for a finger print change are the ssh server key was re-generated (by someone), the sshd reinstalled (not just updated from yum or apt-get), your local ssh client reinstalled or --- the real reason for the check --- there is a man-in-the-middle.
In the key update scenarios, either you did it or someone else did it. If it wasn't you, then you are likely compromised.
In the MITM scenario, everything you typed was captured and is now replayable by an adversary. In which case you are likely compromised. Nothing is hidden from the MITM.
So, before you assume you are compromised, please check to make sure Dig O does not manage your service for you and does not make these changes on your behalf. Also, if you updated your local ssh client then they key could have been stomped on. Look for logical reasons not to expect the worst --- but you are very very correct to be paranoid. [personally I always expect the worst. I have worked many many dozens of very significant intrusions.]
In the worst case you merely have to scratch the OS and restore your data (not executable files, libraries, passwords or ssh_keys from a potentially corrupt backup, but just your data. If you restore services you have a race condition ... update the authentication passwords instantly.
All this assumes that any intrusion doesn't start with your local client and have propogated to the remote server -- :).
In general you should understand where that message came from and if it wasn't you -- time to get to work.
openssh
changed the default algorithm for calculating fingerprint hash from MD5 to SHA256 causing similar results. The message was The authenticity of host (...) can't be established and a new fingerprint was displayed.known_hosts
is not hashed, so a change of hash function wouldn't invalidate the stored public keys.known_hosts
on my Mac and see that in the past it wasssh-rsa
being recorded, now it isecdsa-sha2-nistp256
(for one certain machine which has been remembered under different IPs). Can't say exactly, but seems like the change in displayed hash and the change in requested key type occurred at the same time. Maybe I misinterpreted the reason for my problem. Now I've got to do more investigation...