We have a server at work that had the following key types: ssh-rsa, ecdsa-sha2-nistp256, ssh-ed25519.

Recently at new key of type ssh-ed25519-cert-v01@openssh.com was added to the server and its causing some host key verification errors under OpenSSH 8.4p1 if the known_hosts file already contains the ecdsa-sha2-nistp256 key. If you're using an older version of OpenSSH or your known_hosts file has the ssh-rsa key, then this doesn't happen.

I think that this is because in 8.4p1 the host key ordering algorithm was changed to not do anything if it thinks the known key is the same type as the first key in the default priority. This change didn't take into account the fact that all the certificate algorithms were prioritized over the non-certificate algorithms.

https://anongit.mindrot.org/openssh.git/commit/?id=b3855ff053f5078ec3d3c653cdaedefaa5fc362d

Before this change, if an ECDSA key was encountered in the known_hosts file the preference would be changed to prefer the ECDSA type over ED25519-cert. The order would be: ECDSA-cert, ECDSA, ED25519-cert, RSA-cert, ED25519, RSA

After this change it detects that ECDSA is already the top priority and leaves the order alone, which means that ED25519-cert is prefered over ECDSA. The default order is: ECDSA-cert, ED25519-cert, RSA-cert, ECDSA, ED25519, RSA

# here is the server's host key advertisement from the debug output:

debug2: host key algorithms: ssh-rsa,rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519,ssh-ed25519-cert-v01@openssh.com

# get all the host keys

$ ssh-keyscan -t ssh-ed25519 10.201.18.12 > known_host_ed25519
# 10.201.18.12:22 SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.3
$ ssh-keyscan -t ssh-rsa 10.201.18.12 > known_host_rsa
# 10.201.18.12:22 SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.3
$ ssh-keyscan -t ecdsa-sha2-nistp256 10.201.18.12 > known_host_ecdsa
# 10.201.18.12:22 SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.3

# No problems with OpenSSH 8.3p1

$ ssh -V
OpenSSH_8.3p1 Debian-1, OpenSSL 1.1.1h  22 Sep 2020
$ ssh -o UserKnownHostsFile=known_host_ecdsa 10.201.18.12 /bin/true
$ ssh -o UserKnownHostsFile=known_host_rsa 10.201.18.12 /bin/true
$ ssh -o UserKnownHostsFile=known_host_ed25519 10.201.18.12 /bin/true

# OpenSSH 8.4p1 gives a host key verification error if the known key is ECDSA

$ ./ssh -V
OpenSSH_8.4p1, OpenSSL 1.1.1h  22 Sep 2020
$ ./ssh -o UserKnownHostsFile=known_host_ecdsa 10.201.18.12 /bin/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:LTkLApkY9YiVCTzXQawvLtpUgv2D1IYVzMbcsa+96OY.
Please contact your system administrator.
Add correct host key in known_host_ecdsa to get rid of this message.
Offending ECDSA key in known_host_ecdsa:1
ED25519 host key for 10.201.18.12 has changed and you have requested strict checking.
Host key verification failed.
$ ./ssh -o UserKnownHostsFile=known_host_rsa 10.201.18.12 /bin/true
$ ./ssh -o UserKnownHostsFile=known_host_ed25519 10.201.18.12 /bin/true