REMOTE HOST IDENTIFICATION HAS CHANGED — investigate before you delete

The changed host key warning is the only moment in normal operations when SSH refuses to continue and demands a decision. It is also the warning most reliably discarded, because the fastest route back to a working session is to delete one line. That habit converts the one interception detector you have into a formality.

What the message actually says

The upstream text is worth reading field by field rather than skimming for the line number.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 <TYPE> key sent by the remote host is
SHA256:....
Please contact your system administrator.
Add correct host key in <known_hosts path> to get rid of this message.
Offending <TYPE> key in <file>:<line>
Host key for <host> has changed and you have requested strict checking.
Host key verification failed.

Two details are commonly misremembered. First, upstream OpenSSH prints only Offending <TYPE> key in <file>:<line> and Add correct host key in <path> to get rid of this message. The familiar “remove with: ssh-keygen -f ... -R ...” line is a patch carried by Debian and Red Hat family distributions, not upstream behaviour, so a runbook that tells the reader to look for it will fail on other platforms. Second, the message names the file and the line. That is the precise entry the client objected to, and it is more useful than the hostname, because a fleet file can hold several entries for overlapping patterns.

Two sibling banners exist in the same code path and mean different things: WARNING: POSSIBLE DNS SPOOFING DETECTED!, raised when CheckHostIP is enabled and the entry for the name disagrees with the entry for the address, and WARNING: REVOKED HOST KEY DETECTED!, raised when the presented key carries the @revoked marker. The revoked banner is never a false alarm caused by a rebuild.

Three explanations, and only one is benign

flowchart TD
    A["Host key changed"] --> B{"Was this host rebuilt\nor reinstalled?"}
    B -- "change record exists" --> C["Legitimate rotation"]
    B -- "no record" --> D{"Did the name or address\nmove to another machine?"}
    D -- "yes" --> E["Address or name reuse"]
    D -- "no" --> F["Treat as interception\nuntil disproved"]

The three branches carry very different costs when guessed wrongly.

• Legitimate rebuild or key rotation. A host was reimaged, a container was recreated, an appliance was factory reset, or a planned host key rotation reached this machine. Evidence for this lives outside SSH: a change record, a provisioning run, a build timestamp, an instance identifier that differs from the one you connected to last week.
• Name or address reuse. In a dynamic estate the identifier you typed may now resolve to a different machine entirely. A recycled cloud address, a DHCP lease handed on, a load balancer or NAT that fronts several backends, a port-forward left pointing somewhere else. Nothing is compromised, and nothing was rebuilt; you are simply talking to a different computer.
• Interception. Someone is terminating your session and relaying it. This is the least likely explanation on a normal Tuesday and the only one where deleting the entry completes the attack.

Rank them in that order by likelihood, but never let likelihood substitute for evidence. The cost asymmetry is severe: confirming a rebuild takes a minute, and misreading an interception as a rebuild hands over every credential you type next.

One question separates the first two branches faster than any command: did anyone else see the warning? A genuine key change affects every client that held the old entry, so if a colleague connected to the same name minutes earlier with no warning at all, the host did not change its key and your path to it did. Conversely, if the whole team is warned simultaneously and a build pipeline shows a reimage at that hour, the investigation is essentially over. Get that answer from a chat channel before you touch a file; it costs one message and reorders the entire hypothesis list.

Getting ground truth off the network

The investigation has one requirement: the answer must come from somewhere other than the SSH connection you are suspicious of. Asking the possibly-hostile endpoint what its key is proves nothing.

# On the host itself, through the serial console, BMC or cloud
# console. Not through SSH.
for KEYFILE in /etc/ssh/ssh_host_*_key.pub; do
  ssh-keygen -l -f "$KEYFILE"
done

Compare the fingerprint printed there against the one in the warning. If your provisioning pipeline recorded fingerprints at build time, or the platform publishes them in the instance console output, that record serves the same purpose and is faster to reach. Next, read the entry that actually matched, using the file and line the warning gave you.

KNOWN_HOSTS="$HOME/.ssh/known_hosts"
OFFENDING_LINE=37
sed -n "${OFFENDING_LINE}p" "$KNOWN_HOSTS" > /tmp/offending-entry.pub
ssh-keygen -l -f /tmp/offending-entry.pub

That tells you what you previously trusted, including which name pattern the entry covered. Now look at what the network offers today and at whether the name still points where it used to.

TARGET=web-01.lab.example
getent hosts "$TARGET"
ssh-keyscan -t ed25519 "$TARGET" > /tmp/observed-key.pub
ssh-keygen -l -f /tmp/observed-key.pub

If the address changed and the new address belongs to a machine someone else now owns, you have address reuse and the old entry is simply stale. If the address is unchanged, the host was not rebuilt, and the console shows a different fingerprint from the one being offered, stop and escalate.

Sometimes no console exists and no build record was kept, which is common with appliances and with hosts inherited from a team that has moved on. The honest position then is that you cannot verify the new key, and the decision becomes a risk one rather than a technical one. Two things still help. Connect from a completely different network path, such as a machine in another site or a different provider, and compare the fingerprint the two paths observe; an interceptor sitting on one path will not usually be on both. And treat the session that follows as untrusted regardless: no passwords typed, no agent forwarded, no secrets pasted, nothing but the commands needed to establish what the machine is.

The other half of the investigation is blast radius. If the warning appeared partway through a working session, or if anyone connected past it earlier, then whatever was typed reached an endpoint whose identity is unproven. List the credentials that could have crossed that connection, including sudo passwords, database passwords pasted into a client, tokens exported into the environment and anything an agent could have signed for, and rotate them on the assumption that they were captured.

StrictHostKeyChecking, stated honestly

The setting has four values and they are not points on a single scale.

• ask, the default. New keys are added only after the user confirms; a changed key is refused.
• yes. Keys are never added automatically, and a changed key is refused. Correct where trust is distributed in advance.
• accept-new. A genuinely new key is added automatically, and a changed key is still refused. This is the value for first-contact automation, and it is what people usually mean when they reach for no.
• no or off. New keys are added automatically and a changed key does not stop the connection.

That last value is the trap. On a changed key, ssh does not simply skip the prompt: it proceeds in a degraded mode and says so once, starting with Password authentication is disabled to avoid man-in-the-middle attacks. Keyboard-interactive authentication, agent forwarding, X11 forwarding, port forwarding, tunnel forwarding and UpdateHostKeys are all disabled alongside it. An automation job configured this way does not fail loudly when a host key changes. It connects, then breaks in a way that looks like a firewall problem, because the port forward it depends on silently stopped existing. Verification of the host is also gone, which was the point of the setting.

Production discipline

1. Answer the rebuild question first, from a change record. If the host was reimaged an hour ago by a pipeline that logged it, the investigation is finished in under a minute.
2. Never obtain the expected fingerprint over SSH. Console, BMC, cloud API or build-time inventory. Anything else is asking the suspect for an alibi.
3. Use accept-new, never no, for automation. It removes the prompt on genuinely new hosts and keeps the detection you would otherwise be turning off.
4. Repair by line, and keep a copy. Remove the specific entry the warning named, retain the old line and the new fingerprint, and check for a second entry recorded against the address.
5. Escalate on a revoked-key banner immediately. That message cannot be produced by a rebuild; it means the presented key is on a list somebody deliberately created.

Cross-course references

• Linux for Production Sysadmins - Part LXX (Out-of-Band Access) covers serial consoles and BMCs, which are the channels that can answer the fingerprint question without using the network path under suspicion.
• Kubernetes for Production Sysadmins - Part CXXIX (Security Incident) covers the escalation path once an interception hypothesis survives the first round of evidence.
• Git, CI/CD & GitOps for Infrastructure Engineers - Part XCV (Compromised Runner) covers a build host that authenticates onwards, which is exactly the machine a relayed SSH session would be aiming at.

Quiz