The bug #2068423 mostly talks about the error message, but the root cause is that the crypto policy does not control the client hostkey algorithm list.

This is because the HostKeyAlgorithms option does not limit only selection, but enforces also order, which overrides the default order of hostkeys given by the content of the known_hosts file. Enforncing order of the hostkeys is something that would give most of the users scary warnings about hostkey change.

This was known issue and limitation since  we introduced crypto policies to OpenSSH (I think we even had it documented somewhere, but I can not find it now). I had an upstream bug for this for 5 years with some discussion, but it was never merged [1] that was the reason why we decided to take different approach with Zoltan, to reuse the PubkeyAcceptedAlgorithms (that come from c-p) as it did not require "API"/configuration and crypto policies changes that would be incompatible with the upstream and that would work for most common default configurations and configurations managed by c-p. For the price of potentially "breaking" some very corner cases where the users would explicitly set disjoint algorithm set for PubkeyAcceptedAlgorithms and HostkeyAcceptedAlgrithms.

If you find this confusing, the alternative option is in the upstream bug [1], but it requires modification of c-p and incompatibility with upstream OpenSSH. Do not change the patch to use HostKeyAlgorithms as it would not solve the original issue!

[1] https://bugzilla.mindrot.org/show_bug.cgi?id=2924

Jakub, and would using "-" syntax in CP help?

(In reply to Dmitry Belyavskiy from comment #12)
> Jakub, and would using "-" syntax in CP help?

No. Any option (including the - prefix) setting the `HostkeyAcceptedAlgrithms` overrides the default ordering based on local known_hosts file

I propose this to be added to the ssh_config man page under HostKeyAlgorithms:

"crypto_policies(7) does not handle the list of algorithms as doing so would break the order given by
 the known_hosts file. Therefore the list is filtered by PubkeyAcceptedAlgorithms."

Any opinions?

LGTM

Since the problem described in this bug report should be
resolved in a recent advisory, it has been closed with a
resolution of ERRATA.

For information on the advisory (openssh bug fix and enhancement update), and where to find the updated
files, follow the link below.

If the solution does not work for you, open a new bug report.

https://access.redhat.com/errata/RHBA-2023:6622