Host key verification failed: what it means and the right way to fix it

Near the top of every search result for this error sits the same one-liner: -o StrictHostKeyChecking=no. It makes the error go away, which is why people paste it — and it does so by switching off the only identity check SSH has, which is why you shouldn't. Here's what the warning actually protects, why it fires on perfectly innocent occasions, and the fix that takes ninety seconds and doesn't leave a hole behind.

What the check is for

When you connect, the server proves who it is with its host key — a key pair that identifies the machine, the mirror image of the keys that identify you. Your client records the key's fingerprint in ~/.ssh/known_hosts on first contact, and on every later connection verifies the server still presents the same one.

That check is the only thing standing between you and a man-in-the-middle. SSH's encryption guarantees nobody can read the conversation between you and whoever holds the other end — it does not, by itself, guarantee the other end is your server. Anyone positioned in between (hostile Wi-Fi, a compromised router, DNS pointing somewhere new) can terminate the connection themselves, speak flawless SSH, and relay everything both ways — collecting your password and your session as they pass through. The one thing an impostor can't do is present your server's host key. This warning is that defense firing.

The two messages

WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! — the full banner with the @ wall: the server presented a different key than the one on record. This is the serious one. Helpfully, it names the exact entry: Offending ED25519 key in ~/.ssh/known_hosts:42.

Host key verification failed. — the terse version, usually the last line under the banner above. On its own, it also appears whenever there's a mismatch (or an unknown host) and the client can't ask you — scripts, cron jobs, git, CI, anything running without a terminal to prompt on.

Why it fires (usually innocently)

In rough order of likelihood:

1. The server was rebuilt or reinstalled. Fresh OS means fresh host keys, generated at first boot. By far the most common cause.
2. A different machine has the old address. Cloud IPs and DHCP leases get recycled — yesterday's 203.0.113.10 is somebody else's instance today. Same story when a DNS name is repointed at a replacement box.
3. Several machines behind one name. A load balancer or round-robin DNS in front of backends with individual host keys trips the warning on rotation — maddeningly intermittent.
4. Host keys were regenerated on a running box — some hardening scripts and image-cloning cleanups do this deliberately.
5. An actual interception. Rare — and, from your side of the connection, indistinguishable from the four above. Which is exactly why the warning refuses to be quiet.

That's the uncomfortable honesty of it: cases 1–4 look identical to case 5 from where you sit. The procedure below is what tells them apart.

The wrong fix, and what it actually does

ssh -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null user@host   # don't

This doesn't skip a nagging prompt — it disables server identity checking entirely. Every connection now trusts whoever answers, which converts a man-in-the-middle from "impossible without the host key" to "undetectable." The UserKnownHostsFile=/dev/null half means it will keep trusting anyone, silently, with no warning ever again.

It's worst where it's most common: pasted into CI configs and deploy scripts, where it outlives the incident that prompted it by years and quietly strips the identity check from every future connection. If a machine changes keys weekly by design, there's a defensible relaxation below — this isn't it.

The right fix: remove, then verify

Step 1 — remove the stale entry:

ssh-keygen -R web1.example.com
ssh-keygen -R 203.0.113.10                 # if you also connect by IP
ssh-keygen -R '[web1.example.com]:2222'    # non-standard ports use this syntax

This deletes the old fingerprint and backs up the file. One aside: if HashKnownHosts is on, you can't grep known_hosts for a hostname — entries are hashed. ssh-keygen -F web1.example.com finds them anyway, and -R removes them the same way.

Step 2 — get the real fingerprint out-of-band. Before reconnecting, learn what the legitimate key is through a channel that isn't the network path you're worried about: the cloud provider's web console, a serial console, the hypervisor, a colleague already logged in. On the server:

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

That prints the SHA256 fingerprint of each host key. Many cloud consoles also print them in the instance's first-boot log — the natural place to look right after a rebuild.

Step 3 — reconnect and compare. The next ssh shows the offered fingerprint and asks. Compare it against step 2 — actually compare it, character for character at the start and end at minimum; this is the whole point — then accept. The new key is recorded, and the machinery guards you again.

If the fingerprints don't match: stop. Don't type your password. You're now in the rare case, and your next moves belong on the console, not on the network.

The legitimate relaxations

For hosts that are rebuilt constantly by design — ephemeral CI runners, a dev VM re-imaged nightly — two honest options exist that don't turn checking off:

• StrictHostKeyChecking accept-new auto-trusts hosts you've never seen but still hard-fails when a known host's key changes. That preserves the property that matters — a changed identity is still an alarm — while removing first-contact prompts. Scope it to a Host block for the ephemeral group, never Host *.
• A separate UserKnownHostsFile per churn-prone group — the throwaway VMs pollute their own file, and blowing that file away doesn't touch the trust you've accumulated for real infrastructure.

For load balancers: either install the same host keys on every backend (the key then identifies the service, which is a legitimate reading), or SSH to individual node names and leave the balanced name to the protocols it actually balances.

Trust as a first-class thing

The friction in all of this is that OpenSSH shows you a fingerprint at the worst possible moment — first contact, mid-task — and then stores your trust decisions in a file most people never look at again. A client can run the same protocol with better manners: Termalin uses trust-on-first-use with a proper known_hosts — it shows each server's fingerprint on first connect, so you can verify it while the provider console is already open, and when a known host's identity changes it warns loudly instead of letting the connection through. Same model, same discipline — the difference is that trust is visible per host instead of buried in a dot-file. And for the errors that come after identity is settled — Permission denied (publickey) chief among them — the decoder ring covers the rest of the family.

Termalin is a free, cross-platform SSH client that verifies each server's identity on first connect and warns loudly when it changes — download it, or read how it handles trust and keys.