Bug 2164016

Description of problem:

If you have an old ssh-rsa host key in known_hosts and upgrade to F37, you will be unable to connect to the host. The error is very unhelpful:

  "Bad server host key: Invalid key length"


Version-Release number of selected component (if applicable):

openssh-8.8p1-7.fc37.x86_64

How reproducible:

Always


Steps to Reproduce:
1. Use DEFAULT crypto policiies.
2. Have an old host key in known_hosts that is disallowed by the policy.
3. Try to ssh to the host.

Actual results:

Bad server host key: Invalid key length

It seems that the ssh client first finds a matching host key in known_hosts, and *then* checks whether that key is allowed by policy.

debug1: Remote protocol version 2.0, remote software version OpenSSH_8.0
debug1: compat_banner: match: OpenSSH_8.0 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to gcc.gnu.org:22 as 'jwakely'
debug3: record_hostkey: found key type RSA in file /home/jwakely/.ssh/known_hosts:58
debug3: load_hostkeys_file: loaded 1 keys from gcc.gnu.org
...
...
debug1: kex: algorithm: curve25519-sha256
debug1: kex: host key algorithm: rsa-sha2-512
debug1: kex: server->client cipher: aes256-gcm MAC: <implicit> compression: zlib
debug1: kex: client->server cipher: aes256-gcm MAC: <implicit> compression: zlib
debug1: kex: curve25519-sha256 need=32 dh_need=32
debug1: kex: curve25519-sha256 need=32 dh_need=32
debug3: send packet: type 30
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug3: receive packet: type 31
debug1: SSH2_MSG_KEX_ECDH_REPLY received
Bad server host key: Invalid key length



Expected results:

Ideally, the client would not even load a host key from known_hosts if it's a type that isn't allowed. That way a new host key would be received, and the user would be prompted to accept a new one of a type that the client can use:

The authenticity of host 'gcc.gnu.org (8.43.85.97)' can't be established.
ED25519 key fingerprint is SHA256:5DrqonN/NcBalJRSSpE86TZRuNiBYukggX/j02fe1qA.
This key is not known by any other names
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added 'gcc.gnu.org' (ED25519) to the list of known hosts.

Alternatively, the error message should make it clear that the problem is the host key read from ~/.ssh/known_hosts **not** the one being received from the server. To somebody unfamiliar with the openssh internal implementation details, it's not at all clear that "Bad server host key" means a problem with your local known_hosts file rather than a problem with the server. The reaction is simply "argh, another fedora crypto policy change ... I need to allow the server's key somehow".


Additional info:

The fix is simply to remove the offending line from known_hosts and accept a new key of a type allowed by the policy.  But because there's no clue about known_hosts in the error, people are downgrading their systemwide crypto policy to LEGACY to be able to connect to servers that they need to reach. This does not improve security!

If improving the error message is not possible, could we at least add something to https://docs.fedoraproject.org/en-US/quick-docs/dnf-system-upgrade/#sect-resolving-post-upgrade-issues pointing out that old host keys might be unusable and suggesting that the solution is to remove those entries from known_hosts and accept a new host key.

There is currently no info I could find in fedora docs about the right fix for this error.

There is no mention of known_hosts in any of 
https://fedoraproject.org/wiki/Changes/CryptoPolicy
https://fedoraproject.org/wiki/Changes/StrongCryptoSettings
https://fedoraproject.org/wiki/Changes/StrongCryptoSettings2
https://fedoraproject.org/wiki/Changes/StrongCryptoSettings3

https://fedoraproject.org/wiki/Releases/37/ChangeSet#Strong_crypto_settings:_phase_3,_forewarning_1/2 specifically says F37 doesn't change any defaults, but that doesn't seem to be true since upgrading f36 to f37 broke this use case.