Created attachment 3198 [details] possibility to order host keys in client The HostKeyAlgorithms option in the client has a difference from all the other algorithm limiting options that should be sorted according to the list of known hosts available. This works fine out of the box with default negotiated list, but when one tries to limit (or extend) the algorithm list to something else than default, the ordering is turned off and one can simply hit the hostkey changed, even though it did not change at all (only different one is offered for a connection). There is attached proposed patch to implement new configuration option HostKeyAlgorithmsOrder, which will turn on sorting also on the user-provided list of host keys. Other possibility to resolve this problem would be to introduce another configuration option HostKeyAlgorithmsAllow or similar, which would have this semantics (would be ordered before the algorithm negotiation).
I'm kinda loath to add another option. Maybe another magic character, e.g. HostKeyAlgorithms=:ssh-ed25519,ssh-rsa etc to specify a list ordered by the known host keys? (i mean, it's ugly but so it yet another option...)
Thank you for the suggestion. This would also solve the original problem. Not sure about the character as ":", but "~" might work as "approximate" list?
Created attachment 3313 [details] Introduce a new modifier for HostKeyAlgorithms to allow ordering Damien, I rewrote the patch to use the colon prefix notation to signalize the same. Would it work this way for you?
OpenSSH 8.2 will enable UpdateHostKeys by default. IMO this goes some way to avoiding this problem.
Right. After the first successful authentication, the client will learn all the server host keys and we should be able to validate whatever key server provides according to our preference. But getting over the first connection can still problem and it is hard to guess how long it can take to make sure the users already connected at least once to the particular host to be safe to roll out this change. Therefore I see the UpdateHostKeys as a good addition, but the attached patch would still significantly simplify the migration path and decrease user frustration when dealing with failed host key checking.
i might be hitting this issue, can someone confirm that this it the same one or i might want to open another one? if i run this on default configuration and accept the RSA key: rm ~/.ssh/known_hosts ssh user@localhost -oHostKeyAlgorithms=rsa-sha2-512 then this works: ssh user@localhost this also works: ssh user@localhost -oHostKeyAlgorithms=rsa-sha2-512,ssh-ed25519 this doesn't work: ssh user@localhost -oHostKeyAlgorithms=ssh-ed25519,rsa-sha2-512 now edit ssh_config, setting HostKeyAlgorithms to the *default* value from man ssh_config. then this also doesn't work: ssh user@localhost this behavior is very unexpected and at the very least should be mentioned in the manual?