openssh bugs - Oct 2020 - [Bug 3221] New: hostkey preference ordering is broken in some situations

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

            Bug ID: 3221
           Summary: hostkey preference ordering is broken in some
                    situations
           Product: Portable OpenSSH
           Version: 8.4p1
          Hardware: Other
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P5
         Component: ssh
          Assignee: unassigned-bugs at mindrot.org
          Reporter: nuxi at vault24.org

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 at 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
at 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

-- 
You are receiving this mail because:
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |djm at mindrot.org

--- Comment #1 from Damien Miller <djm at mindrot.org> ---
please attach the output of "ssh -vvv user at host" for a failing
connection

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

--- Comment #2 from NUXI <nuxi at vault24.org> ---
Created attachment 3449
  --> https://bugzilla.mindrot.org/attachment.cgi?id=3449&action=edit
ssh -vvv output

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |3217
             Status|NEW                         |ASSIGNED

--- Comment #3 from Damien Miller <djm at mindrot.org> ---
yes, that is a real bug and you have found the AFAIK only combination
of known_hosts contents and server host key that triggers it.


Referenced Bugs:

https://bugzilla.mindrot.org/show_bug.cgi?id=3217
[Bug 3217] Tracking bug for 8.5 release
-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

--- Comment #4 from Damien Miller <djm at mindrot.org> ---
FWIW, OpenSSH 8.5 will move ssh-ed25519 (and its cert counterpart) to
the head of the list and this will dodge that particular bug.

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #5 from Damien Miller <djm at mindrot.org> ---
fixed in 8.5 - due very soon

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=3221

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |CLOSED

--- Comment #6 from Damien Miller <djm at mindrot.org> ---
closing resolved bugs as of 8.6p1 release

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.