SSH From Scratch: Why That Host Key Warning Should (Sometimes) Scare You

1. The warning that should scare you, sometimes

You terminate an EC2 box and launch a fresh one on the same IP. Same key, same command you've run a hundred times before. This time it stops you cold:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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)!

Two things can cause this, and the warning looks identical either way:

Someone is sitting between you and that box.
You relaunched the instance.

SSH has no way to tell you which. By the end of this post you'll know why it can't, and why that's the correct design instead of a broken one.

2. Two unrelated key pairs

You've probably only ever touched one key file for this, the .pem AWS handed you at launch. That makes it easy to assume SSH runs on one keypair. It doesn't. It runs on two, and they do opposite jobs.

	Host key pair	Client key pair
Proves	server → client	client → server
Answers	is this box the one I meant to hit?	is this laptop who it claims to be?
Generated by	the instance itself, on its first boot	you, or the console at launch
Private half	`/etc/ssh/ssh_host_ed25519_key`, never leaves the box	your `.pem` file, never leaves your laptop
Public half	cached by your laptop in `~/.ssh/known_hosts`	installed on the box in `~/.ssh/authorized_keys`

You never noticed there were two because AWS does both halves of the setup for you:

Generating a host key, normally ssh-keygen, run once by whoever administers the box.
Deploying your public key, normally ssh-copy-id, run once by you.

One .pem download made it look like a single key was doing all the work.

3. Getting a connection at all

Before either key pair does anything, two boring things happen:

A plain TCP handshake.
Both sides announce their SSH version and the algorithms they support, then settle on the ones they share. Something like Curve25519 for key exchange, Ed25519 for signatures, ChaCha20-Poly1305 for the encryption.

No crypto yet, just an agreement on which crypto to use.

Then the key exchange. Two machines that have never met, talking over a wire anyone can read, need to end up holding the same secret without ever sending it. That's Diffie-Hellman, and four facts are all you need from it here:

It's public key math. Its only output is a shared secret K.
Both sides compute K independently. Neither one transmits it.
The symmetric cipher that encrypts every byte from here on takes its keys from K.
An eavesdropper who captured every byte of the exchange still can't compute K.

The math deserves its own post. K has one more job to do in the next section.

4. Proving the server is who it says it is

The key exchange isn't just two public values passing each other. The server also signs H, the exchange hash, with its host private key, the private half of the pair from section 2. H covers:

the version strings
the negotiated algorithms
the public values A and B
the shared secret K itself

That last one matters more than it looks:

If the server signed only its own public key, the signature would be identical on every connection. Capture it once and you could replay it forever without ever touching the private key.
Signing something that includes this session's shared secret makes the signature different every time. Only whoever currently holds the private key can produce it.

That's the actual proof against a man in the middle. A fingerprint match isn't. Fingerprints are next, and they do a different job.

5. Fingerprint ≠ signature

These two get conflated constantly. They're different objects doing different jobs.

	Signature	Fingerprint
Who makes it	the server	your own client
What it is	a signature over `H`, made with the host private key	a hash of the public key bytes just received
Checked against	the host public key, mathematically	whatever's cached in `~/.ssh/known_hosts`
What it proves	the server holds that private key, for this session	nothing cryptographic, it's local bookkeeping

Three outcomes when your client runs that comparison:

No entry in known_hosts yet → the "authenticity of host can't be established" prompt, fingerprint shown, you type yes, it's cached.
Entry matches → completely silent. No prompt, you don't even see it happen.
Entry doesn't match → the warning from section 1.

6. Now prove you're you

Server identity is settled and the channel is encrypted from here on. Now the server has to check you, using the other key pair from section 2, your client key.

The server sends a challenge.
Your client signs it with your private key, that same .pem file.
The server checks that signature against the public key already sitting in authorized_keys.

Nothing reusable crosses the wire. Not your private key, not even a hash of it. Just proof that you currently hold it.

7. Back to that warning

You now have everything you need to answer section 1. Here is what actually happens when you relaunch:

You terminate the instance. The host private key goes with it.
The new instance boots for the first time and cloud-init runs again.
sshd generates a brand new host key pair from scratch. It isn't fetched from anywhere permanent.
Your laptop still has the old fingerprint cached in known_hosts.
The hashes don't match, so the warning fires.

Same IP, same key name in the console, completely different private key underneath. From where your client is sitting, that is indistinguishable from a real machine in the middle attack. SSH can't tell "you relaunched the box" from "someone's intercepting you," and it shouldn't pretend it can. That's exactly the case the warning exists for. The fix isn't to blindly run the removal command it suggests. The fix is to know which one happened first.

A namespace gave two processes their own port table. A host key pair gives a server something no attacker on the wire can fake. Live proof, on every connection, that it still holds the same private key it always held. The warning firing isn't SSH being paranoid. It's SSH doing the one job it promised.