SSH: Host key verification failed

Hi, it's BlueByte. You go to ssh into a server — or git push over SSH — and instead of a prompt you get Host key verification failed, sometimes under a wall of hashes warning that the remote identification has changed. Nothing on your machine is broken, and it isn't necessarily an attack: SSH is doing its job, and the key the server presented doesn't match what it recorded last time. We'll walk through the two forms of this message, why the key stopped matching, how to confirm the new one is safe to trust, how to clear the stale entry, and how to keep it from surprising you again.

The two messages that both end in "Host key verification failed"

Two distinct situations produce this error. The first is a changed key:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
...
Offending ECDSA key in /home/you/.ssh/known_hosts:12
Host key verification failed.

The line that matters is Offending ... key in ~/.ssh/known_hosts:12 — it names the exact file and line number of the recorded key that no longer matches. The second form is a first connection under strict checking, common in scripts and CI:

No ECDSA host key is known for github.com and you have requested strict checking.
Host key verification failed.

Here there's no conflict — SSH simply has no record of the host, and StrictHostKeyChecking won't let it accept a key it can't verify on its own.

What known_hosts is protecting you from

The first time you connect, SSH stores the server's public host key in ~/.ssh/known_hosts (trust on first use). On every later connection it compares the key the server offers against that record. A mismatch is exactly what you'd see if traffic were being intercepted — so SSH refuses rather than silently trusting a new key. That's why the fix is never "turn the check off": it's to establish that the new key is genuine, then record it.

Why the key stopped matching

Most mismatches are mundane, not malicious:

• The server was rebuilt or reprovisioned — a fresh OS install generates new host keys, so the same name or IP now answers with a different key.
• An IP or hostname was reused — a cloud instance released and re-assigned to you, or DHCP handing an address to a different machine.
• The provider rotated its keys — GitHub, for example, replaced its RSA host key in 2023, and everyone caching the old one hit this error.
• You're reaching a different host than you think — a load balancer, bastion, or jump host in front of the name.

The strict-checking variant just means a host you've never recorded, in a context that forbids the interactive "are you sure?" prompt.

First, find the offending entry

Don't delete the whole file. Locate the exact stored key with ssh-keygen -F:

ssh-keygen -F github.com

It prints the matching line from known_hosts. If you already have the Offending ... :12 line from the error, that's the same information — line 12 of ~/.ssh/known_hosts.

Verify the new key before you trust it

This is the step you don't skip. Read the server's current fingerprint and confirm it against a source you trust — not against the server itself:

ssh-keyscan github.com | ssh-keygen -lf -

That prints the SHA256 fingerprints the host is offering now. Compare them to the vendor's published values — GitHub, for instance, lists its fingerprints (the Ed25519 key is SHA256:+DiY3wvvV6TuJJhbpZisF/zLDA0zPMSvHdkr4UvCOqU) in its docs. For your own rebuilt server, read the fingerprint on the box itself with ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub. If the fingerprints match, the new key is real.

Remove the stale key and reconnect

Once you've verified, drop the old entry and let SSH record the new one:

ssh-keygen -R github.com

-R removes all keys for that host from known_hosts and keeps a backup as known_hosts.old. Reconnect and SSH prompts you to accept the new key. For the strict-checking case, add the verified key deliberately instead:

ssh-keyscan github.com >> ~/.ssh/known_hosts

Only append keys you've fingerprint-checked — ssh-keyscan on its own trusts whatever answers.

A real case: a rebuilt server at the same IP

A staging box at 10.0.4.20 got reimaged. The next ssh deploy@10.0.4.20 threw the REMOTE HOST IDENTIFICATION HAS CHANGED block with Offending ED25519 key in ~/.ssh/known_hosts:8. Because I'd done the rebuild myself, I read the new fingerprint on the console with ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub, ran ssh-keygen -R 10.0.4.20 on my laptop, reconnected, compared the offered fingerprint to the one from the console, and accepted. Under a minute, and the check did exactly what it should — it flagged that the identity changed and made me confirm the change was mine.

How it differs from "Permission denied (publickey)" and "Connection refused"

Host key verification failed is about the server's identity — it happens before authentication, when SSH checks who the server is. Permission denied (publickey) is the opposite direction: you reached a trusted server, but your key wasn't accepted for the login. Connection refused is earlier still — nothing answered on the SSH port, so there was no key to check at all. Reading which of the three you got tells you where in the handshake to look.