Remote host identification has changed on two hosts, and only one was rebuilt

Reported symptoms

The estate is two hundred and forty Linux hosts across three racks, reached over SSH by a deploy pipeline, a nightly backup job and about fifteen engineers. Host keys have always been accepted on first contact and never thought about again. The last time anybody edited a known_hosts file by hand was during a rack migration two years ago.

At 08:14 UTC the deploy pipeline stopped at its first step. The incident channel filled up faster than the facts did:

• 08:14, the pipeline logs the changed host identification banner for web-04.lab.example and exits non-zero before any change is made.
• 08:17, an engineer notes that web-04 was rebuilt at 22:10 the previous night and proposes clearing the entry and moving on.
• 08:25, a second engineer tries bastion-2.lab.example by hand and gets the same banner, at which point the working theory becomes a fleet-wide known_hosts corruption.
• 08:31, somebody points out that the backup job has been reporting success all night, which is offered as proof that SSH is fine.
• 08:39, a third engineer starts writing a loop that would have run ssh-keygen -R across every name in the inventory.

That loop was stopped one minute before it ran. What nobody had yet noticed was that only one of the two hosts had been rebuilt, that the backup job had not been fine since 22:11 the previous evening, and that the three week old ticket about agent forwarding no longer working was the same incident seen from a different angle.

Evidence provided

$ ssh -o BatchMode=yes deploy@web-04.lab.example true

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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:/hOjaMxlXaTaWekzkFCIxR4PRU/c7eLkooB565Y7X6I
Please contact your system administrator.
Add correct host key in /home/deploy/.ssh/known_hosts to get rid of this message.
Offending ED25519 key in /home/deploy/.ssh/known_hosts:14
Host key for web-04.lab.example has changed and you have requested strict checking.
Host key verification failed.

$ ssh -o BatchMode=yes deploy@bastion-2.lab.example true

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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:9Qk2rTNvXcE0aLpYd7sBHf4uMwZ1jRoK6bViGtA3nXQ
Please contact your system administrator.
Add correct host key in /home/deploy/.ssh/known_hosts to get rid of this message.
Offending ED25519 key in /home/deploy/.ssh/known_hosts:9
Host key for bastion-2.lab.example has changed and you have requested strict checking.
Host key verification failed.

Note what the banner does and does not say. It names the offending line so you can find it, and it tells you to add the correct host key. It does not tell you which key is correct, and upstream OpenSSH does not offer to remove the entry for you. If your terminal showed a helpful command to delete the line, that hint came from a distribution patch, not from the software that just refused the connection.

The provisioning system captures the host key fingerprint of every build at first boot and files it against the build record. Nobody in the channel knew this existed.

# inventory export: host_key_provenance, 2026-08-26T08:44Z
name                    address          first_boot            ed25519_fingerprint
build-07.lab.example    198.51.100.24    2026-08-25T22:06Z     SHA256:9Qk2rTNvXcE0aLpYd7sBHf4uMwZ1jRoK6bViGtA3nXQ
web-04.lab.example      198.51.100.31    2026-08-25T22:14Z     SHA256:/hOjaMxlXaTaWekzkFCIxR4PRU/c7eLkooB565Y7X6I
bastion-2.lab.example   198.51.100.11    2026-02-03T09:52Z     SHA256:6x39cg8OAp7PZgisHreCLRO7g0vp6s0VZIw+DcTgKtE

Two rows settle the incident and one row is the incident. The web-04 fingerprint recorded four minutes after its rebuild is character for character the key that web-04 is sending now. The bastion-2 record is six months old, has no build since, and does not match what the name is answering with. The key the name is answering with belongs to build-07.

The internal zone is generated from the same provisioning database by a nightly job.

; /var/named/generated/lab.example.zone  (serial 2026082504)
build-07        IN  A   198.51.100.24
bastion-2       IN  A   198.51.100.24
web-04          IN  A   198.51.100.31

$ getent hosts bastion-2.lab.example build-07.lab.example

The backup job never saw a banner because it was told not to care.

# /etc/backup/ssh.conf, unchanged since 2026-04-02
Host *.lab.example
    User backup
    StrictHostKeyChecking no
    ForwardAgent yes

# /var/log/backup/run-20260825.log, first connection after the zone regeneration
2026-08-25T22:11:07Z connecting bastion-2.lab.example
2026-08-25T22:11:07Z ssh: Password authentication is disabled to avoid man-in-the-middle attacks.
2026-08-25T22:11:07Z ssh: Keyboard-interactive authentication is disabled to avoid man-in-the-middle attacks.
2026-08-25T22:11:07Z ssh: Agent forwarding is disabled to avoid man-in-the-middle attacks.
2026-08-25T22:11:07Z ssh: Port forwarding is disabled to avoid man-in-the-middle attacks.
2026-08-25T22:11:08Z transfer started
2026-08-25T22:11:44Z run complete, exit 0

Work the evidence before reading on

The interesting thing here is not that two hosts changed their keys. It is that the two changes have nothing in common except the message they produced, and that the message is identical whether the cause is a rebuild you authorised or a name that now points somewhere else.

1. The banner for web-04 prints a fingerprint. Where else in the evidence does that exact string appear, and what does the timestamp next to it tell you about whether the change was authorised?
2. The banner for bastion-2 prints a different fingerprint. Search the inventory export for it. What is it attached to?
3. Two names in the generated zone share one address. Which of the two is wrong, and how do you tell from the inventory rather than by guessing?
4. The backup log shows four notices at 22:11 and then a successful transfer. What did the backup account authenticate to, and what did it offer while it was doing so?

Before continuing: for each of the two hosts, say whether the key it is presenting is the right key, and name the single line of evidence that settles it. If you cannot, you must not edit known_hosts yet.

Root cause

The zone regeneration wrote one host address under another host name

build-07 was rebuilt at 22:02. The job that regenerates lab.example from the provisioning database ran at 22:08 and emitted bastion-2 with 198.51.100.24, the address belonging to build-07. From that moment every client resolving bastion-2.lab.example connected to a continuous integration worker. The changed host key warning at 08:25 was therefore completely correct and had nothing to do with any rebuild. The fingerprint in that banner, SHA256:9Qk2rTNvXcE0aLpYd7sBHf4uMwZ1jRoK6bViGtA3nXQ, is the build-07 row in the inventory export, recorded at 22:06 that same evening. Deleting line 9 of known_hosts would have replaced a true warning with a permanent silent misdirection.

The rebuild of web-04 was genuine, and the estate could not say so

web-04 really was rebuilt at 22:10, and its first boot fingerprint recorded at 22:14 is the key it is presenting now. That is a benign change. The defect is that nothing in the connection path could establish it. Trust on first use records what a host said the first time anybody asked, which answers the question is this the same key as last time but never the question is this the right key. The inventory held the answer all along, and the runbook did not mention it, so five engineers spent twenty-five minutes debating a fact that was already written down.

The backup job had been told to accept exactly this

StrictHostKeyChecking no did not skip a prompt. It let the backup account authenticate to build-07 believing it was bastion-2, which is why the client emitted four separate notices at 22:11 saying which authentication methods it was withdrawing. Those notices are the whole content of the three week old agent forwarding ticket. The backup account carries a key that reaches every host in the estate, and it offered that key, with agent forwarding requested, to a build worker that any pipeline author can run code on.

Resolution

1. Freeze the exposure before you diagnose anything. Pause the deploy pipeline and stop the backup timer so that no further connection offers a credential to a peer you have not identified. The pipeline has already failed safe; the backup job has not, and it will run again on schedule.
2. Copy the affected known_hosts files aside, with cp -a, before any tool writes to them. Note the line numbers the banners named, 14 for web-04 and 9 for bastion-2, and record the fingerprint each banner printed. This is your only record of the prior state.
3. Classify each host independently against the provisioning inventory, which is an out of band channel the network cannot influence. A fingerprint that matches a first boot record with a build time you can corroborate is a rebuild. A fingerprint that matches no record for that name is an unresolved identity, whatever the name suggests.
4. For web-04, whose presented key matches the record written at 22:14, replace only line 14. Remove the stale entry with ssh-keygen -R web-04.lab.example and append the recorded key from the inventory. Take the key material from the provisioning record, never by scanning the live host, because scanning proves only that something on the network is willing to answer.
5. For bastion-2, do not connect and do not edit line 9. Reach the real machine at 198.51.100.11 through the console or serial path and confirm which host is actually running there. Open a security case: a privileged account authenticated to a build worker under another name for ten hours.
6. Fix the zone generation template so the name field and the address field are read from the same inventory row, regenerate the zone, bump the serial and confirm that bastion-2 and build-07 no longer share an address. Until this lands, every client that resolves the name is still being misdirected.
7. Rotate every credential the backup account could have presented between 22:11 on 25 August and the freeze. That is the backup SSH key itself, anything reachable through the forwarded agent, and any token the transfer script read from its environment. Treat them as disclosed, because a pipeline author on build-07 could have read them.
8. Restore strict checking in the backup wrapper. Remove StrictHostKeyChecking no outright rather than lowering it, and do not substitute accept-new here: this job connects to hosts it has met before, so first contact handling is not what it needs. Where genuine first contact automation exists elsewhere, accept-new is the correct setting and must be documented with the window it leaves open.

Verification

1. Read the running host key of the real bastion-2 from its console session with ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub and compare it by eye with the inventory record and with the copy of line 9 you preserved. This reads the key from the machine itself rather than from anything the network offered.
2. Resolve both names from a resolver other than the one the incident used, and confirm each returns the address its own inventory row holds. Two names returning one address is the defect; one name returning its own address is the fix.
3. Reconnect to web-04 with ssh -v and confirm the session establishes with no banner and no prompt. A silent success proves the entry matches; a suppressed warning would not, which is why nothing in this procedure disables checking.
4. Run the deploy pipeline against a single host and confirm it completes the SSH step rather than skipping it. Check the exit status, not just the absence of a red line in the log.
5. Re-enable the backup job with strict checking restored, point a test run at a host whose key you have deliberately not recorded, and confirm it fails. A job that cannot fail on a changed host key can never report one, so proving the failure path is part of proving the fix.
6. Authenticate with each rotated credential and confirm the superseded material is refused. Rotation that was never tested against the old value is an assumption, not a control.
7. Confirm the agent forwarding ticket is resolved by the same change, and close it against this incident rather than separately. If it still reproduces, the wrapper configuration was not the only place the setting appeared.

Prevention

• Give hosts an identity that survives a rebuild. An SSH host certificate authority replaces per host trust on first use with one CA key distributed as a known_hosts line carrying the @cert-authority marker. A rebuilt host presents a freshly issued certificate and no client sees a warning, because the client is checking a signature rather than remembering a key.
• Bound the certificate, then alert on it. Issue host certificates with a thirteen week validity, renew at nine weeks, warn at three weeks remaining and page at one week. A certificate authority with no expiry policy is a long lived key with extra steps.
• Make the provenance record authoritative, not incidental. Capture the first boot fingerprint automatically, store it beside the build record, and name that record in the runbook as the thing an operator consults before editing known_hosts.
• Fail the merge, not the incident. Add a continuous integration check that rejects StrictHostKeyChecking no or off in any script, playbook or unit file, and permit accept-new only in a named bootstrap path with a comment stating the exposure window.
• Diff generated infrastructure before publishing it. The zone job should compare its output against the previous run and refuse to publish when an existing name changes address without a matching change record. This one control would have stopped the incident at 22:08.
• Watch the trust files themselves. Alert on any edit to a shared known_hosts file, and review quarterly for names whose address has moved with no build behind it.