“Host Key Verification Failed” — What It Means

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!

Almost everyone's first instinct is to find the offending line in known_hosts, delete it, and get on with their day. Usually that instinct is right. Occasionally it is the worst possible response, and the whole reason the warning exists.

Two minutes of checking tells you which situation you are in.

What the warning actually detects

Every SSH server has a host key — a key pair that identifies the machine, quite separate from the keys that identify you. On your first connection, your client shows you its fingerprint and asks whether to trust it:

The authenticity of host 'web1.example.com (203.0.113.10)' can't be established.
ED25519 key fingerprint is SHA256:qE7x1V0Pz9Kk3nR2sW8mYb4LhTuJ6cA0dF5gN1oX2yQ.
Are you sure you want to continue connecting (yes/no/[fingerprint])?

Say yes and the fingerprint is written to ~/.ssh/known_hosts. From then on, your client checks every connection against that record. This is trust on first use: the first handshake is taken on faith, and every one after it is verified.

The warning means the key the server just presented does not match the one on file. Either the server's identity genuinely changed, or you are not talking to the server you think you are.

The two-minute triage

Ask one question: did anything happen to that machine?

The key legitimately changes when:

• the server was rebuilt, reinstalled or reprovisioned
• a cloud instance was recreated (same DNS name, new machine)
• OpenSSH was reinstalled, or /etc/ssh/ssh_host_* was regenerated
• the hostname or IP now points at a different machine — a failover, a DHCP lease change, a reused elastic IP
• you are connecting through a load balancer or port forward that reaches different backends

None of those apply and nothing changed on your side? Then treat it as an interception until proven otherwise. On a café or hotel network, that is not paranoia — it is the exact scenario the check was designed for.

Verifying properly

The only verification that means anything comes from a channel you already trust — not from the connection you are suspicious of.

On the server, via a hosting console, cloud serial console or physical access:

ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub
# 256 SHA256:qE7x1V0Pz9Kk3nR2sW8mYb4LhTuJ6cA0dF5gN1oX2yQ root@web1 (ED25519)

Compare that string, character for character, with what your client is showing. Match means the server was rebuilt and you can proceed. Mismatch means stop and investigate the network path.

Most cloud providers print the host key fingerprints in the instance's boot log or console output for exactly this purpose — worth knowing where yours does it before you need it.

Clearing a key you have verified

Do not hand-edit the file. Use the tool:

ssh-keygen -R web1.example.com

That removes every entry for the host, including the hashed forms, and keeps a backup at known_hosts.old. If the server listens on a non-standard port, include it:

ssh-keygen -R '[web1.example.com]:2222'

Then reconnect and accept the new fingerprint deliberately — comparing it against the value you obtained out of band:

ssh deploy@web1.example.com

You can also accept a specific fingerprint at the prompt by pasting it instead of typing yes, which is a nice way to prove to yourself you actually checked.

Why known_hosts looks like gibberish

|1|F1PkT8k9y0Qz3vB2mN4rS6tW8xY=|hR7pL2nQ4sV6yB8dF0gJ2kM4oP6= ssh-ed25519 AAAAC3Nza...

HashKnownHosts yes is the default on most distributions: hostnames are stored as salted hashes so that a stolen file does not hand an attacker a list of every machine you administer. It is why grep finds nothing and why ssh-keygen -R is the right removal tool.

To look up a host without un-hashing everything:

ssh-keygen -F web1.example.com

Preventing the whole dance

Pin the key at provisioning time. If you control how servers are built, collect the host key during provisioning and distribute it, so nobody ever answers a trust-on-first-use prompt blind:

ssh-keyscan -t ed25519 web1.example.com >> ~/.ssh/known_hosts

That is only safe if run over a path you trust — the same warning as before. Its real value is in a build pipeline, where the key is captured on the internal network at creation.

Make first use strict for hosts that matter. For a specific important host:

Host prod-db
    HostName db.internal
    StrictHostKeyChecking yes

With yes, SSH refuses to connect to an unknown host at all rather than offering to trust it — so the key must already be in known_hosts. The default, ask, is the prompt you know.

Never use StrictHostKeyChecking no. It appears in a lot of CI snippets and it disables the entire protection: your client will silently accept whatever key it is handed, every time. If you need unattended connections, pin the key properly instead.

What good clients do differently

The prompt has a design flaw: it appears at the moment you are trying to get work done, and the safe answer requires leaving to go and check something. That is why people click through it.

A client that stores what you trusted and shows it back to you — a Known Hosts screen listing every pinned fingerprint, with a clear warning when one changes — makes the check something you can actually perform. That is how Moray handles it. The first time you connect, it shows the server's SHA256 fingerprint and its randomart picture (the same one ssh-keygen -lv draws) and waits for you to choose Trust & Connect. The key is then pinned per host. If it ever changes, the connection stops on a "Server identity changed" screen with the old and new keys side by side, and Cancel is the default. A Known Hosts list shows everything you have accepted, so "has this changed?" is answerable rather than theoretical.

The short version

• The warning means the server's identity changed. It is doing its job.
• Rebuilt or reprovisioned the machine? Expected — clear and re-verify.
• Changed nothing? Treat it as interception until you have checked the fingerprint out of band.
• Clear entries with ssh-keygen -R, never by editing the file.
• Never set StrictHostKeyChecking no to make it go away.

Related: SSH keys explained covers the difference between your key and the host's — the two get confused constantly, and they solve opposite problems.