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.

No ECDSA host key is known for … and you have requested strict checking

The same check, failing in the opposite direction. Where the classic warning means “I know this host and the key changed”, this one means “I’ve never seen this host and you told me not to guess” — StrictHostKeyChecking=yes plus an empty or missing known_hosts entry. You’ll meet it almost exclusively in scripts and CI: a pipeline clones from github.com or ssh.bitbucket.org (wording varies: No ED25519 host key is known, No RSA host key is known — same condition), the runner is a fresh container with a blank known_hosts, and the job dies before the first byte of git traffic.

The lazy fix is StrictHostKeyChecking=no, and it’s just as wrong here as above. The right fix is to seed the trust before the connection:

• Pre-populate known_hosts from the provider’s published keys. GitHub, GitLab and Bitbucket all publish their SSH host keys in their docs — paste the entries into the runner’s known_hosts (an env-provisioned file or a baked image layer). This is verification done properly: the keys came from an authenticated HTTPS page, not from whoever answered port 22 first.
• ssh-keyscan only with a fingerprint check. ssh-keyscan github.com >> ~/.ssh/known_hosts trusts whatever is on the wire at that moment. If you must scan, compare the result against the published fingerprints (ssh-keygen -lf) before appending.
• StrictHostKeyChecking=accept-new for the cases where first-contact trust is an accepted risk — it still hard-fails if a known key later changes.

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.