Does reinstalling openssh-server change the host key?

Question

I recently noticed several ssh brute force attacks on my server that runs ubuntu and openssh-server. Besides taking some countermeasures I have naturally become extra careful. When I tried to ssh into the server this morning I got the dns spoofing warning:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@       WARNING: POSSIBLE DNS SPOOFING DETECTED!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
The ECDSA host key for somehost.com has changed,
and the key for the corresponding IP address xx.xx.xxx.xxx
is unknown. This could either mean that
DNS SPOOFING is happening or the IP address for the host
and its host key have changed at the same time.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 ip address has most likely changed, that wouldn't be surprising. But I have not changed the ubuntu setup recently. However, I reinstalled openssh-server by executing

sudo apt-get remove openssh-server

and reinstalling it with

sudo apt-get install openssh-server

This makes me think that the host key only depends on the directory /etc/ssh/. In my case it looks like this:

drwxr-xr-x   2 root root   4096 Sep  3 19:12 .
drwxr-xr-x 160 root root  12288 Sep 27 08:41 ..
-rw-r--r--   1 root root 300261 Aug 11 18:24 moduli
-rw-r--r--   1 root root   1756 Aug 11 18:24 ssh_config
-rw-r--r--   1 root root   2542 Sep  3 19:09 sshd_config
-rw-------   1 root root    668 Apr 21 15:27 ssh_host_dsa_key
-rw-r--r--   1 root root    606 Apr 21 15:27 ssh_host_dsa_key.pub
-rw-------   1 root root    227 Apr 21 15:27 ssh_host_ecdsa_key
-rw-r--r--   1 root root    178 Apr 21 15:27 ssh_host_ecdsa_key.pub
-rw-------   1 root root    411 Apr 21 15:27 ssh_host_ed25519_key
-rw-r--r--   1 root root     98 Apr 21 15:27 ssh_host_ed25519_key.pub
-rw-------   1 root root   1675 Apr 21 15:27 ssh_host_rsa_key
-rw-r--r--   1 root root    398 Apr 21 15:27 ssh_host_rsa_key.pub
-rw-r--r--   1 root root    338 Sep  3 19:12 ssh_import_id

Today is Sep 27, so all ssh_host* files have not changed since april. I'm not exactly sure if the users public key influences the host key. So just to be sure, I checked the user ssh directory ~/.ssh/, which looks like this:

drwx------  2 user user 4096 Sep  5 18:41 .
drwxr-xr-x 49 user user 4096 Sep 27 08:43 ..
-rw-------  1 user user  748 Apr 21 19:20 authorized_keys
-rwx------  1 user user 3326 Jan 21  2016 id_rsa
-rw-rw-rw-  1 user user  748 Jan 21  2016 id_rsa.pub
-rw-r--r--  1 user user 2726 Mai  3 13:00 known_hosts

So the user public key hasn't changed either.

Question: Is there anything else that influences the host key or the host fingerprint? Anything that I am not taking into account? Is it possible that reinstalling openssh-server changed the host key? If yes, where are the files that were updated?

[EDIT] I have meanwhile checked the ECDSA fingerprint on the server itself by executing (see this for details)

$ nmap localhost --script ssh-hostkey

and the fingerprint matches the one that is shown in the spoof notice. So it seems that not the server has changed but rather the known_hosts file on the machine that I was using to connect to the server. Maybe Germar is right and the IP address matched a server that I connected to earlier. I am still not exactly sure why I got the spoofing notice. But unless the nmap command is not spoofed aswell (I assume it is not) I should have a secure connection.

Answer 1

Your original host keys would be deleted if you had purged openssh-server, using either apt-get purge openssh-server or apt-get remove --purge openssh-server. In this case the keys would be regenerated, and would naturally be different. If openssh-server was just removed, the key files should not have been touched on reinstallation.

The host keys do indeed only depend upon the files in /etc/ssh/, unless ssh is configured to look elsewhere. This would be evident by any unusual looking HostKey lines in /etc/ssh/sshd_config. The default HostKey lines are:

# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key

It is definitely worth checking the file to see whether you're using host keys from a non-standard location, as your key files appear not to have been modified.

If the keys on the server are as expected, the warning is most likely being generated at the client end of things. As Germar said, the problem could be caused by reuse of a dynamically assigned IP address which had previously been used by another server.

Answer 2

When you remove the package and reinstall, the keys are left intact. Only if you purge the package they will get removed. And only if the key files do not exist the will be created. To get the full idea of what is going on, you can read these files:

/var/lib/dpkg/info/openssh-server.postinst
/var/lib/dpkg/info/openssh-server.postrm
/var/lib/dpkg/info/openssh-server.preinst
/var/lib/dpkg/info/openssh-server.prerm

These are the scripts being run by dpkg when removing or installing - or reconfiguring - the package.