Fixing SSH Error: Host Key Verification Failed After VPS Re-installation

by

Root Cause Diagnosis

Re-installing the VPS regenerates the SSH host keys in /etc/ssh/sshhost*_key, so the server now presents a different public key from the one your client stored in ~/.ssh/known_hosts on first connection. The client compares the presented key with the stored entry for that IP or hostname, finds a mismatch, and aborts with WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! followed by Host key verification failed. This is a client-side trust check, not a server fault, and it protects against man-in-the-middle attacks, so the fix is to remove the stale entry only after confirming the change is legitimate.

Quick Fix

Remove the old entry for the host and reconnect:

ssh-keygen -R your.server.ip.or.hostname
ssh user@your.server.ip.or.hostname

Type yes when prompted to accept the new fingerprint. Verify that fingerprint first (Step 2) if the network between you and the VPS is untrusted.

Step-by-Step Resolution

1. Read the error to locate the offending entry

The error output names the file and line number:

Offending ECDSA key in /home/user/.ssh/known_hosts:12

Line 12 is the stale entry. The message also states which key type is mismatched (RSA, ECDSA, or ED25519).

2. Verify the new fingerprint out-of-band

Get the server’s real fingerprints from the provider’s web console or VNC/serial console (not over the SSH session in question):

for f in /etc/ssh/ssh_host_*_key.pub; do ssh-keygen -lf "$f"; done

Compare the output with the fingerprint SSH shows when you reconnect. If you cannot reach a console, fetch the keys directly and compare:

ssh-keyscan -t ed25519,ecdsa,rsa your.server.ip 2>/dev/null | ssh-keygen -lf -

Note that ssh-keyscan over the same network path does not prove authenticity. It only shows what the network currently presents.

See also  Resolving Docker DNS lookup failure inside container on custom bridge network

3. Remove the stale entry

Preferred method, which also creates a backup at ~/.ssh/known_hosts.old:

ssh-keygen -R your.server.ip
ssh-keygen -R your.hostname

Run it for every name the host was stored under, because known_hosts keeps separate entries for the hostname, the IP, and non-default ports. For a non-default port, use the bracketed form:

ssh-keygen -R "[your.server.ip]:2222"

Manual alternative using the line number from Step 1:

sed -i '12d' ~/.ssh/known_hosts

4. Reconnect and accept the new key

ssh -o StrictHostKeyChecking=ask user@your.server.ip

Compare the displayed fingerprint (SHA256:...) with the one from Step 2, then answer yes. The new key is appended to ~/.ssh/known_hosts.

5. Restore the old host keys instead (optional)

If you want to avoid the warning on all clients, copy the previous host keys onto the re-installed server before clients reconnect. This works only if you kept a backup of /etc/ssh/sshhost*:

sudo cp ssh_host_* /etc/ssh/
sudo chmod 600 /etc/ssh/ssh_host_*_key
sudo chmod 644 /etc/ssh/ssh_host_*_key.pub
sudo chown root:root /etc/ssh/ssh_host_*
sudo systemctl restart sshd    # use "ssh" on Debian/Ubuntu

6. Fix other clients and tools

Every machine that connected to the old server holds its own stale entry. Repeat Step 3 on each. For automation, also check:

  • Ansible: remove the entry on the control node, or set host_key_checking = False in ansible.cfg only for disposable hosts.
  • Git over SSH, rsync, scp, CI runners: they read the same ~/.ssh/known_hosts of the user running the job. Clear it under that user, or in the runner’s home directory.
  • Windows (OpenSSH): the file is C:\Users\.ssh\known_hosts. Run ssh-keygen -R from PowerShell.
  • PuTTY: delete the cached key at HKEY_CURRENT_USER\Software\SimonTatham\PuTTY\SshHostKeys in the registry, or accept the prompt when it appears.
See also  Linux out of memory killer (oom-killer) picking wrong high-priority daemon: Tuning oom_score_adj

7. Verify

ssh -v user@your.server.ip 2>&1 | grep -iE "Server host key|Host .* is known|Authenticated"

You should see the new key type and fingerprint, then a successful authentication.

Why This Fails for Some Users

  • Hashed known_hosts entries: If HashKnownHosts yes is set (default on Debian/Ubuntu), the hostname is not readable in the file. ssh-keygen -R still works because it hashes the name for comparison. Manual searching with grep will not.
  • Multiple names for one host: The same server may be stored under an IP, a DNS name, and an alias in ~/.ssh/config. Removing only one leaves the others failing. Check with ssh-keygen -F name for each.
  • System-wide known_hosts: A stale entry in /etc/ssh/ssh_known_hosts is not touched by ssh-keygen -R on the user file. Remove it with sudo ssh-keygen -R host -f /etc/ssh/ssh_known_hosts.
  • Reused IP with a different key type: If you accepted an ED25519 key before and the server now offers only ECDSA (or the reverse), you get a mismatch or a “no matching host key type” error. Force the type with ssh -o HostKeyAlgorithms=ssh-ed25519 user@host, or list keys the server exposes with ssh-keyscan.
  • Read-only or wrong-permission file: If ~/.ssh/known_hosts is not writable, SSH cannot store the new key and the failure repeats. Fix with chmod 600 ~/.ssh/known_hosts and chown $USER ~/.ssh/known_hosts.
  • Custom UserKnownHostsFile: A ~/.ssh/config or command-line -o UserKnownHostsFile=... setting points SSH to a different file. Run ssh -G host | grep -i knownhosts to see which files are actually read.
  • DNS or load-balancer round-robin: If a hostname resolves to several servers with different host keys, the error appears intermittently. Use one shared set of host keys across the pool or connect by IP.
  • SSHFP/VerifyHostKeyDNS: With VerifyHostKeyDNS yes, stale DNS SSHFP records conflict with the new keys. Update or delete the records at your DNS provider.
  • Certificate-based host keys: If the client uses @cert-authority lines in known_hosts, the re-installed server needs a fresh certificate signed by the CA, or the trust check fails regardless of the plain-key entry.
  • Genuine man-in-the-middle: If you did not re-install or rebuild the server and the key changed, do not remove the entry. Verify the fingerprint through the provider console first.
  • Agent forwarding and ProxyJump: With ProxyJump, the bastion and the target each have their own known_hosts entry. The error message names which host failed, so clear the correct one.
See also  Resolving Linux swap partition not mounting automatically on system reboot

Leave a Comment