Is 'Host key verification failed' a hacker, or did the server just change?

Almost always the server changed, and almost never a hacker — but 'almost' is why SSH stops you instead of guessing. The overwhelming majority of these are benign: the server was reinstalled, a cloud instance was rebuilt, the IP was reassigned to a different machine, or a container came up fresh. All of those hand you a legitimately new host key, and SSH can't tell them apart from a man-in-the-middle intercepting your connection with a key of their own. That's the point of the check: it refuses to decide for you. Your job is to confirm which case you're in before you clear the warning, not to assume the scary one or the boring one.

How do I actually verify the new key is safe before deleting the old one?

Get the real fingerprint from a channel that doesn't run over the suspicious connection. For a cloud server, the provider's console or first-boot log usually prints the host key fingerprint — compare it to what SSH is now showing you. For a server you administer, read the fingerprint locally with ssh-keygen -lf on the server's own key file. If both match what your client sees, the change is real and you can safely update known_hosts. If you can't verify it through any independent path, don't connect — an unverifiable key change is exactly the situation the warning exists for.

What's the command to fix it once I've confirmed the change is real?

Remove only the stale entry, not the whole file: ssh-keygen -R hostname (SSH even prints the exact command, including the known_hosts path and line number, in the warning). That deletes the old key for that host; your next connection prompts you to accept the new one, trust-on-first-use style. Don't hand-edit known_hosts unless you know it's hashed — and never delete the entire file to make the error go away, because you'd be discarding every host key you've ever verified and silencing this exact protection for all of them at once.

I'm getting the error on the very first connection to a host. Why?

Then it's not a changed key — it's a different failure that ends with the same line. If you've never connected before, there's nothing in known_hosts to conflict with, so a 'verification failed' usually means either StrictHostKeyChecking is on (common in automation and CI) and SSH won't auto-accept an unknown host, or you answered anything other than 'yes' to the fingerprint prompt, or known_hosts isn't readable. The 'REMOTE HOST IDENTIFICATION HAS CHANGED' banner only appears for a genuine mismatch; without that banner, you're looking at strict checking on a host SSH has simply never been told to trust.

Host key verification failed (SSH)

Problem

You try to ssh to a host you’ve reached before, and instead of a prompt you get a wall of hash marks and a refusal:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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)!
...
Offending ECDSA key in /home/you/.ssh/known_hosts:12
...
Host key verification failed.

The connection stops dead. Nothing you type gets through.

What This Actually Means

SSH remembers the public key of every server you’ve accepted, in ~/.ssh/known_hosts (plus any system-wide entries in /etc/ssh/ssh_known_hosts). On every connection it re-checks: does the key this host is presenting match the one I stored last time? When the answer is no, it doesn’t ask, it doesn’t guess — it aborts.

That refusal is the feature, not a malfunction. The whole security model of SSH is trust on first use: you verify a host once, SSH pins its key, and from then on it can detect if the key ever changes. A changed key has exactly two explanations, and SSH cannot tell them apart from where it sits:

The server legitimately has a new key.
Something is impersonating the server with a key of its own — a man-in-the-middle.

Case 1 is common and boring. Case 2 is rare and serious. The warning is loud because the stakes of case 2 are high, not because case 2 is likely. Your job is to figure out which one you’re actually in.

The Fork That Decides What You Do Next

Before you touch known_hosts, answer one question: do you have a reason to expect this host’s key to have changed?

If yes — you or someone on your team just reinstalled the OS, rebuilt the VM, recycled the cloud instance, redeployed the container, or the hostname points at a pool of machines behind a load balancer and you landed on a different one — then a new key is exactly what you’d expect. This is the benign majority. Confirm the new fingerprint (below), then clear the old entry.
If no — nothing changed on your side, the server was supposed to be stable, and it suddenly has a different key — then slow down. That’s the pattern worth being suspicious of. Don’t clear the warning to make it go away; verify the key through an independent channel first, and if you can’t, don’t connect.

The mistake almost everyone makes is treating every occurrence as case “yes” and reflexively running ssh-keygen -R. That works, right up until the one time it shouldn’t — and there’s no way to tell that time apart after you’ve deleted the evidence and trusted whatever answered.

Verify Before You Delete

The right move in both cases is the same: get the host’s real fingerprint from somewhere that doesn’t ride the connection you’re suspicious of, and compare.

Cloud servers: the provider’s web console or the instance’s first-boot log almost always prints the SSH host key fingerprint. Compare it to what your client is now showing.
Servers you administer: log in through another path (console, out-of-band management) and read the key locally with ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub. That’s the ground truth.
No independent path at all: then you can’t safely verify the change, and “I’ll just delete it” is precisely the decision the warning is trying to stop you from making on autopilot.

Modern OpenSSH shows SHA256 fingerprints by default (SHA256:…). If your records are in the older MD5 hex format, print the matching form with ssh-keygen -E md5 -lf.

Top 3 Causes

The server was rebuilt or the IP was reassigned. Reinstalling the OS, rebuilding a VM, recreating a container, or a cloud provider handing your old IP to someone else’s new instance all produce a genuinely new host key. This is the single most common cause, and it’s the one people correctly expect — but should still verify.
One name, many machines. A hostname that resolves to a load-balanced or round-robin pool can put you on a different backend than last time, each with its own host key. The “change” flips back and forth depending on which node you hit. The fix isn’t deleting keys repeatedly; it’s making sure every node shares a key, or you’re pinning the right one.
A key-type change, or a first-time strict-check failure. If SSH now negotiates a different key type than the one you stored (say the server added Ed25519 and you’d pinned RSA), or you’re connecting for the first time under StrictHostKeyChecking=yes in a script or CI job, you can hit a verification failure without a genuine mismatch. The giveaway is the absence of the “IDENTIFICATION HAS CHANGED” banner — that banner only fires for a real conflict.

Diagnose with DechoNet

IP Check — look up the IP behind the hostname to see what it’s associated with now. If a cloud provider reassigned it, or it now maps to a different network or owner than you expect, that alone explains a legitimate key change — and tells you the “change” is infrastructure, not an attacker.
Reverse DNS Check — check the PTR record for the IP. A reverse name that suddenly belongs to a different host or provider is strong corroboration that the machine on the other end really did change.
Port Check — confirm port 22 (or your custom SSH port) is actually open and answering from the outside, so you can separate “the key changed” from “I’m not even reaching the server I think I am.”

Resolution Checklist

Read the warning fully. If it includes “REMOTE HOST IDENTIFICATION HAS CHANGED”, it’s a real key mismatch; if it doesn’t, you’re looking at strict checking or a first-connection issue, not a change.
Ask the expectation question: is there a known reason this host’s key should have changed? Rebuild, redeploy, IP reassignment, load-balanced pool?
Verify the new fingerprint through an independent channel (provider console, out-of-band login, ssh-keygen -lf on the server itself). Do not skip this because it’s inconvenient.
Only once verified, remove the stale entry: ssh-keygen -R hostname. SSH prints the exact command, file, and line number in the warning — use that.
Reconnect and accept the new key when prompted. If you manage many clients, distribute the corrected key rather than having everyone re-accept blindly.
If you could not verify the key, do not connect. Treat an unexplained, unverifiable change as a potential interception until proven otherwise.

When to Escalate

If nothing on your side changed and you cannot get the real fingerprint to match through any independent path, stop and treat it as a possible man-in-the-middle: report it, and reach the host through a different network before trusting anything.
If the error toggles on and off for one hostname, you’re almost certainly hitting a multi-host pool with mismatched keys — that’s an infrastructure fix (unify the host keys), not something to paper over with repeated deletions.
Related connection failures worth checking when SSH won’t behave: ssh: connect to host port 22: Connection refused for when you can’t reach the service at all, which is a different problem from reaching it and distrusting its key.

Check your own domain now

Free, no sign-up. Runs the exact check this guide describes and shows what to fix.