SSH's "Host key verification failed" and "REMOTE HOST IDENTIFICATION HAS CHANGED" warnings

What it is

The ssh(1) manual page documents that the client checks the host key a server presents against the entry stored for that host in known_hosts. If no entry exists and strict checking is enabled, or the confirmation prompt cannot be shown (BatchMode=yes, no terminal, as in most automation), the client aborts with Host key verification failed.. If an entry does exist but the presented key differs from it, ssh first prints a large, hard-to-miss warning that includes WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! and a line about a possible man-in-the-middle attack, names the exact file and line holding the old entry, and then ends with the same Host key verification failed..

Why it matters

The identical message is produced by an actual key-substitution attack and by several completely ordinary events: a server rebuilt or reimaged from scratch, a floating IP or load balancer now pointing at a different host, or a machine re-provisioned from an image that regenerates its host keys on first boot. The warning text alone cannot distinguish an attack from routine infrastructure change, which is exactly why it is not safe to reflexively dismiss.

How to apply

• Diagnose before changing anything: work out whether the host could legitimately have a new key - was it rebuilt, migrated, or repointed recently? Compare timing against known infrastructure changes.
• Verify out of band: obtain the new key's fingerprint through a channel that is not the SSH connection itself - the server operator, a cloud provider's console feature for retrieving a host's key, or a value recorded by configuration management at provisioning time - and compare it against what ssh reports for the newly offered key before proceeding.
• Only once the new key is confirmed legitimate: remove the stale entry with ssh-keygen -R hostname, documented by ssh-keygen(1) as removing all keys belonging to the given host from a known_hosts file (for a non-standard port the entry is '[hostname]:2222'; an IP address may have its own entry too), then connect again and accept the new key.
• Unsafe: routinely setting ssh -o StrictHostKeyChecking=no, or scripting past the prompt, as a standing default. That removes the exact protection meant to catch a real key substitution, and should be reserved, if at all, for genuinely disposable hosts on an isolated network where the risk has been explicitly accepted - not as a general fix for the inconvenience. For first contact in automation, StrictHostKeyChecking=accept-new (OpenSSH 7.6+) records unknown hosts but still refuses changed keys; pre-seeding known_hosts with verified keys is better still.

Pitfalls

• Treating every occurrence as routine because it "usually is" in your environment; that habit is precisely what an attacker relying on this warning being ignored counts on.
• Deleting the entire known_hosts file to "start clean" instead of the one offending line, discarding verification for every other host you already trusted.