SSH Host Key Verification Failed (tested)

Host key verification failed means the key the server just sent does not match what your client expected, or you have strict checking on and no record at all. We built a throwaway sshd, rotated its host key under our own known_hosts file, and measured the exact prompts, the exact error text, the real fix, and the difference between two settings that look similar but are not.

1. The two situations behind this message

OpenSSH's known-hosts system checks the server's host key against a cache at ~/.ssh/known_hosts (or whatever UserKnownHostsFile points to). There are two different situations that both end in trouble:

Never seen this host before. ssh asks you to confirm a fingerprint. This is a normal prompt, not an error.
Seen this host before, but the key changed. ssh refuses outright and prints a large warning. This is the dangerous one, because it is exactly what a man-in-the-middle attack looks like, and also exactly what a reinstalled server looks like.

We measured both, plus the actual fix, plus a setting that quietly removes the protection without telling you.

2. Test setup

We ran a throwaway sshd on 127.0.0.1:8984, started as a normal user (no root, no system sshd involved), with a fresh ed25519 host key and a dedicated client key in authorized_keys. We pointed every client at our own throwaway known_hosts file so nothing touched any real account.

$ ssh-keygen -t ed25519 -f hostkey -N ""
$ /usr/sbin/sshd -D -f sshd_config -p 8984
$ ssh -p 8984 -o UserKnownHostsFile=/tmp/known_hosts -i clientkey jacque@localhost

3. First connection: the normal prompt

With an empty known_hosts file, the default (StrictHostKeyChecking=ask) prompt looked like this, word for word:

The authenticity of host '[localhost]:8984 ([127.0.0.1]:8984)' can't be established.
ED25519 key fingerprint is SHA256:uPaAM/ojNIlnWh3mIk/fNCAVEtRlIZm4PmR/Vx0bvgQ.
This key is not known by any other names.
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added '[localhost]:8984' (ED25519) to the list of known hosts.

Typing yes added one line to our known_hosts file. On this box it was hashed, not plaintext, because Debian's system ssh_config sets HashKnownHosts yes by default:

|1|xyOY8rQJqgRZ/nf9qkKiYp7156E=|Sa/QnPPy5eWaMR2VTSsYuOSbKZo= ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIIBvFa...

This is the only step where ssh actually asks you anything. Every situation below starts from this cached line already existing.

4. The host key changes: REMOTE HOST IDENTIFICATION HAS CHANGED

We stopped our sshd, deleted the host key, generated a brand new one, and restarted on the same port with the same known_hosts file still holding the old fingerprint. Reconnecting gave this, exactly:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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)!
It is also possible that a host key has just been changed.
The fingerprint for the ED25519 key sent by the remote host is
SHA256:yBHh8qIQfRHQGi/wlrHeeZN8z9SyEo+uf52Sjm4Sulo.
Please contact your system administrator.
Add correct host key in /tmp/sshtest2/known_hosts to get rid of this message.
Offending ED25519 key in /tmp/sshtest2/known_hosts:1
  remove with:
  ssh-keygen -f '/tmp/sshtest2/known_hosts' -R '[localhost]:8984'
Host key for [localhost]:8984 has changed and you have requested strict checking.
Host key verification failed.

Exit code was 255, same as the client's generic "no" exit status for other auth failures. We tried answering anyway: unlike section 3, there is no yes/no prompt here at all. We fed yes into the terminal the instant it appeared and it made no difference, because ssh never reads it; with strict checking on, a changed key is a hard stop, not a question.

5. The real fix: ssh-keygen -R

The error message itself prints the exact fix. We ran it and then reconnected:

$ ssh-keygen -f '/tmp/sshtest2/known_hosts' -R '[localhost]:8984'
# Host [localhost]:8984 found: line 1
/tmp/sshtest2/known_hosts updated.
Original contents retained as /tmp/sshtest2/known_hosts.old

-R deletes the stale line (keeping a .old backup) and nothing more. It does not add the new key. Reconnecting afterward landed back in section 3's situation exactly: a fresh "authenticity of host can't be established" prompt, because known_hosts is now empty for that host again. Accepting it with yes wrote the new fingerprint and the connection succeeded.

This is the correct fix only if you have actually confirmed the new key is legitimate out of band (you rebuilt the server, you rotated its host key on purpose). ssh-keygen -R does not verify anything; it just forgets the old answer so ssh will ask again.

6. StrictHostKeyChecking=no vs accept-new: the part that matters

Both settings skip the interactive prompt, but we measured a real difference in what happens to a changed key, not just a new one. We put the same stale (pre-rotation) known_hosts in front of the rotated server for each test:

Setting	Genuinely new host	Host key CHANGED since last time
`StrictHostKeyChecking=ask` (default)	Prompts, asks yes/no	Refuses outright, exit 255 (section 4)
`StrictHostKeyChecking=accept-new`	Silently accepts, exit 0, adds the key	Refuses outright, exit 255, identical wording to section 4
`StrictHostKeyChecking=no`	Silently accepts, exit 0, adds the key	Prints the full WARNING banner, then logs in anyway, exit 0

The =no case is the one to watch. We measured it directly: the connection succeeded, our command ran, and exit code was 0, with the same "REMOTE HOST IDENTIFICATION HAS CHANGED" banner from section 4 printed first as a warning rather than enforced as a block. In our run it also did not rewrite the known_hosts entry to the new key; it just let the mismatched connection through every time, silently, from the script's point of view (nothing failed, nothing exited non-zero).

accept-new behaved identically to the secure default for a changed key: flat refusal, exit 255. The only thing it skips is the yes/no prompt for a host it has truly never seen. That is the setting worth using in scripts and CI, not =no: it removes the interactive prompt without removing the protection against a swapped key, which is the actual MITM scenario this whole mechanism exists to catch.

7. Checklist, in the order we'd check it

Read the message. "Can't be established" (section 3) is a new host, normal. "IDENTIFICATION HAS CHANGED" (section 4) is a cached mismatch, stop and think.
Before running the suggested ssh-keygen -R, confirm out of band that the server's key really did change on purpose (rebuild, reinstall, provider migration) rather than assuming it.
Run ssh-keygen -R <host> (or [host]:port for a non-default port, exactly as the error prints it) to drop the stale line, then reconnect and accept the new fingerprint.
In scripts, use StrictHostKeyChecking=accept-new, never =no. We measured =no accepting a changed key and logging in anyway with exit 0; accept-new still blocked it.
If you manage the server, keep a copy of its host key fingerprint from first boot (ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub) somewhere else, so you have something to check a "changed" warning against.

Frequently asked questions

Is Host key verification failed always an attack?

No. We measured two different causes with different wording. A never-before-seen host just asks you to confirm a fingerprint (not an error). A host whose key changed since your last connection refuses outright with a WARNING banner, exit code 255. Rebuilt servers, reinstalled OSes, and reissued cloud IPs cause this constantly without any attack.

Why didn't typing yes work for the changed-key error?

Because there is no prompt to answer. We tested this directly: with StrictHostKeyChecking at its default, a changed key skips straight to 'Host key verification failed' and exit 255, with no yes/no question at all. That is different from the first-connection case in section 3, which does ask.

What does ssh-keygen -R actually fix?

It deletes the stale cached line for that host from known_hosts (keeping a .old backup) and nothing else. We measured that reconnecting afterward produces a brand-new first-time prompt, not an automatic login. You still need to accept the new key, ideally after confirming it out of band.

Is StrictHostKeyChecking=no safe for automation?

We measured it accepting a host whose key had actually changed, printing the full MITM warning banner but still completing the login with exit code 0. That is the scenario this whole system exists to stop. Use accept-new instead: in our tests it accepted genuinely new hosts the same way but still refused a changed key with the same hard error as the default setting.

What's the difference between accept-new and StrictHostKeyChecking=no?

Both skip the interactive yes/no prompt for a host you've never seen. The difference we measured is what happens when a previously-known host's key changes: accept-new still refuses it (exit 255, same as the default), while =no logs the warning and lets the connection through anyway (exit 0).

Written with AI assistance. Measured on 2026-10-02 with OpenSSH_10.0p2 (Debian 13), client and server, against a throwaway sshd on 127.0.0.1:8984 with ed25519 host keys we generated and rotated by hand (no real accounts involved). Known-hosts hashing (HashKnownHosts yes) comes from Debian's system /etc/ssh/ssh_config, confirmed with `ssh -G`, not changed by us. PlainHeaders is our extension; OpenSSH (ssh, sshd, ssh-keygen) is free.