SSH - Authenticity of the host could not be verified.

If you are connecting to your servers via SSH, this would not be due to any changes by Linode. If you are connecting using SSH via LISH, you can verify the correct LISH Gateway Fingerprints.

If you are concerned about a Man in the Middle Attack, or whenever you see this message, you should manually check the proper key on the server. I found SSH Check Server Fingerprint to be very helpful in explaining this process. To outline the steps here:

1. Login to your server directly via LISH

2. Run the following script to output your keys

   cd /etc/ssh
   for file in *sa_key.pub
   do   ssh-keygen -lf $file
   done
   

3. Compare it to the error message you are seeing when connecting via SSH.

4. If the format differs from what you are using, you can use FingerprintHash to specify the hash. For example, in my CentOS server, my keys specify SHA256, so I'll run the following on my local machine to confirm the match:

ssh -o FingerprintHash=sha256 <centos7IP>

Once you confirm that the keys match, you can be assured you are connecting into your server.

*noob question: I just applied Rebuild on my Linode instance. I selected the same OS and I believe I selected the same Key Pair that I was already associated with it. Now I'm getting that same error message (WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!). I thought I would be able to just copy authorized_keys from /.ssh, but was surprised to see that on my old Linode that still works, I don't have an authorized_keys file there, just a known_hosts file. And on my newly rebuilt Linode I only have an authorized_keys file there. I thougt about just creating a new key but I don't want to lock myself out of my old Linode… Advice and guidance are appreciated.

Now I'm getting that same error message (WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!). I thought I would be able to just copy authorized_keys from /.ssh, but was surprised to see that on my old Linode that still works, I don't have an authorized_keys file there, just a known_hosts file.

Rebuilding the node has re-generated the hosts's keys.

Those are not the same as authorized_keys or known_hosts, the three types of keys are:

1 - The hosts's own keys, these are typically in /etc/ssh with names like ssh_host*

The purpose of these keys is to uniquely identify the host itself, the "machine".

2 - The known hosts file stores the host keys (above) for the remote hosts that you've connected to.

A mismatch vs. an already stored key will result in the message you're seeing ("REMOTE HOST IDENTIFICATION HAS CHANGED").

The purpose of known_hosts is exactly this - to store the host keys of whatever servers you previously connected to, and to watch for any changes. A change could represent an MITM attack, or a changed host key for valid reasons.

3 - Authorized keys file - stores user (not host) keys (the public part) and is used to grant access to users.

To summarize: host keys identify a host, known_hosts stores host keys and is used to detect changes, authorized_keys stores user keys and is used to grant password-less access.

Advice and guidance are appreciated

You can remove the old host keys from your known_hosts file with any text editor. The format is simple, one host (with key) per line.

Thank you. Your advice was a patronizing and sadistic attempt to pretend to "point me in the right direction" without actually helping me. Here is what is actually needed to solve this issue, clearly stated:

1. On the LOCAL MACHINE (Not the Linode Server, where I wasted a ton of time trying to solve my problem):
   a. Edit .ssh/known_hosts > Delete the entry pertaining to the IP Address of the rebuilt Linode machine
   b. SSH into the local server
2. On the Remote Machine:
   a. Edit /root/.ssh/authorized_keys > Add local SSH Key to bottom of file

The fact that I wasted several days trying to figure this out, and couldn't figure it out after receiving "help" is a clear indication of a documentation and user support issue at Linode. I have regretted trying to learn how to deploy python / django projects to publically available IPs on Linode, and this is just another example of what is lacking here. I imagine that most people that have to rebuild a Linode System may run into this issue, but rather than having timely and meaningful documentation on how to solve this problem, I only get useless pedantic snark from the community. Thank you for nothing. I figured it out with the help of resources from Digital Ocean and helpful industry professionals. No wonder Digital Ocean is owning you guys in this space.

Hey @josephrussavage, thanks for following up with the solution to your issue, and for taking the time to share your experience here. Having started from zero myself when I first started working with Linode, I also had several frustrating moments while learning, and took those moments as opportunities to improve our platform whenever I could. Accordingly, I went ahead and rebuilt one of my own Linodes to recreate your experience, and I wanted to share my analysis of how we could improve in response to your experience.

First, I wanted to make sure that we did offer guidance in our documentation to address the problem you ran into.

I found that, though this guidance never reached you, we do have a "Note" at the end of the SSH login instructions in our Getting Started Guide addressing this exact scenario (it is indeed a frequent issue):

Note
 
If you recently rebuilt an existing Linode, you might receive an error message when you try to reconnect via SSH. SSH clients try to match the remote host with the known keys on your desktop computer, so when you rebuild your Linode, the remote host key changes.
 
To reconnect via SSH, revoke the key for that IP address.
 
For Linux and macOS:

ssh-keygen -R 198.51.100.4  

For Windows, PuTTY users must remove the old host IP addresses manually. PuTTY’s known hosts are in the registry entry:

HKEY_CURRENT_USER\Software\SimonTatham\PuTTY\SshHostKeys  

Even so, the above language could be improved for clarity.

Otherwise, I'm seeing that while we have extensive documentation on both Public Key Authentication with SSH and Troubleshooting SSH, this common message goes unmentioned.

Finally, while rebuilding myself, I noticed that we don't make any mention of this issue on the Rebuild page of Cloud Manager. When the immediate experience after rebuilding a Linode and trying to access it via SSH results in this:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

we could definitely prepare our customers better for receiving such a message.

Accordingly, I'm going to work on getting this issue referenced in our Troubleshooting SSH guide, as well as directly in Cloud Manager itself prior to rebuilding to help preempt the problem entirely, and improving the existing language in our documentation.

If you have any other thoughts or suggestions on this, please don't hesitate to share them.