SSH to github.com only adds RSA keys - excludes ed25519 host keys

Question

I am doing some tests around ssh. From what I have seen a server usually has multiple host keys. When a client tries to connect, it tries to negotiate which key types to use DSA, RSA, ECDSA, etc. But on key signature confirmation by the user, those host keys are added to known_hosts.

This brings up my problem:

I am sure I saw in known_hosts keys for github both for RSA and ECDSA(or ed25519). Now when I connect to github it only adds the RSA key. If I tweak the preferred algorithm with HostKeyAlgorithms and set it to ed25519 only, it obviously refuses to connect with WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!.

I tested with a local openssh server and indeed it adds all the host keys. Why does github behave differently?

Config file:

Host *
    ServerAliveInterval 60
    HostKeyAlgorithms rsa-sha2-512,rsa-sha2-256,ssh-ed25519

Answer 1

GitHub has several different host keys: RSA, ECDSA, and Ed25519. OpenSSH, when performing key rotation via UpdateHostKeys, will only accept keys that meet certain criteria, one of which is that they are not listed multiple times in the file.

Because older versions of OpenSSH used to store an IP address for host keys as well, this prevents those keys from being automatically updated in many cases. That's why OpenSSH turned off the CheckHostIP setting in 8.5 and newer. You can see what choices OpenSSH has made based on running ssh -vvv [email protected]. Note that this decision is made by OpenSSH on the client side; the server always offers the keys, but the client decides whether to update them.

If it is the IP addresses, you can remove those entries from your known_hosts file and then the host key rotation should work. However, this will be hard if you have a hashed known_hosts file, such as the default on Debian and Ubuntu.

If you don't specify any settings for HostKeyAlgorithms, OpenSSH will reorder the algorithms such that it prefers host key algorithms for which it already has host keys, so things just work. However, if you specify specific algorithms, then it will override those defaults and always ask for them in the order you specified, even if that results in a failure to connect with the message you saw.