Why Your SSH Host Key Changed After a Rebuild, and What to Do
You rebuild a server, reconnect, and OpenSSH greets you with a wall of capital letters: "WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!" and a suggestion that someone may be eavesdropping. Nine times out of ten, nobody is. The machine simply generated new keys. The tenth time is the one the warning exists for, so it is worth knowing how to tell them apart.
What the warning is actually comparing
Every SSH server has a host key pair, usually one each of Ed25519, ECDSA and RSA, stored as /etc/ssh/ssh_host_*_key. When you first connect, your client records the public half in ~/.ssh/known_hosts, keyed by hostname and IP. This is trust on first use: nothing verified it the first time, but it will notice any change afterwards.
Your login credentials never enter into it. The host key proves "this is the machine I spoke to last time". A fresh install has a fresh identity, so the client sees a stranger answering to an old name.
The message tells you which line to look at:
Offending ED25519 key in /home/you/.ssh/known_hosts:12
Host key verification failed.
Why a rebuild changes the key
Host keys are generated on first boot or at package install, and then live only on that disk. Wipe the disk and the identity goes with it. The usual culprits:
- A reinstall from an OS image or installer, which generates new keys.
- A cloud instance recreated from a template: cloud-init normally deletes and regenerates host keys on first boot, so each instance is unique.
- A restore of data and config from backup that did not include
/etc/ssh. - Reusing the same IP or DNS name for a different machine.
That last one matters. Your known_hosts entry is attached to a name, not a server, so a different box behind the same address looks identical until the keys disagree.
Quick detour: why images do not ship with keys
Hang on, why not bake host keys into the image and avoid all this? Because every machine cloned from it would share one private key. Anyone who extracted it from one instance could impersonate all of them. Generating keys per machine on first boot is the right default, and the warning is the price.
Do not just delete the line yet
The instinctive fix is ssh-keygen -R hostname, which removes the old entry and lets you accept a new key. That works, but accepting blindly puts you back at trust on first use, which is exactly the weak moment an attacker would want. If you rebuilt the server five minutes ago, you know the change is expected. If you did not, stop.
Ask first: did I, or someone on my team, rebuild this host? If the answer is "no" or "not sure", treat the warning as real until proven otherwise.
How to verify the new key properly
You need the fingerprint from a channel that is not the SSH connection you are worried about. Pick whichever you have:
- Log in through a console: the cloud provider's web console, a hypervisor, or a keyboard on the machine.
- Print the fingerprint of the key your client will see:
ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub - On your own machine, see what the server is offering without connecting interactively:
ssh-keyscan -t ed25519 server.example.org | ssh-keygen -lf - - Compare the two SHA256 strings. If they match, you are talking to the right machine.
Some provisioning tools, and some cloud consoles, also log the fingerprints at first boot. If yours does, that is a convenient out-of-band source. I would check what your provider actually shows rather than assume.
Then replace the old entry
Once verified, remove the stale line and reconnect:
ssh-keygen -R server.example.org
ssh-keygen -R 203.0.113.10
ssh server.example.org
Do both the name and the IP, since known_hosts usually holds an entry for each. ssh-keygen -R also copes with hashed entries (HashKnownHosts yes), where you cannot grep for the hostname because it has been turned into a hash. It saves the old file as known_hosts.old.
On reconnect, OpenSSH shows the fingerprint and asks for "yes". This time you can compare it against what you checked. Do not type yes until the fingerprint matches the one you got from the console.
Stop it happening next time
If you rebuild often, the cleanest answer is to keep the identity stable. Two approaches:
- Back up and restore host keys. Copy
/etc/ssh/ssh_host_*to your secrets store before wiping, and put them back (private keys mode 600, owned by root) before sshd first starts. Missing keys can be regenerated withssh-keygen -A, which only creates the ones that do not exist. - Use host certificates. Sign each server's host key with a CA key, set
HostCertificateinsshd_config, and put one line inknown_hosts:@cert-authority *.example.org ssh-ed25519 AAAA.... Clients then trust any host the CA signed, new keys included, with no per-host prompt.
There is a third option: publish SSHFP records in DNS and set VerifyHostKeyDNS. It only helps if the zone is DNSSEC-signed; otherwise you are trusting unauthenticated DNS, which defeats the point.
When the change is not yours
If nobody rebuilt anything, do not accept the key. Check whether the IP was reassigned, whether you are on a network doing something odd (a captive portal, a different route), and compare fingerprints via the console. A genuine man-in-the-middle is rare, but the warning is the only thing standing between you and typing a password into the wrong machine.
And if you do restore the old keys onto a rebuilt box, the warning vanishes entirely, which is rather the point: the client had no idea the server was ever replaced.