Failed connection with SSH servers and clients that do not support the 'server-sig-algs' extension

Solution Verified - Updated 13 Jun 2024

Environment

Red Hat Enterprise Linux

Issue

Red Hat Enterprise Linux 9 clients can’t connect to SSH servers that don’t support the server-sig-algs extension nor ECDSA hostkeys. (a, b)
Legacy SSH clients not supporting server-sig-algs extension can not connect to Red Hat Enterprise Linux 9 servers using RSA authentication keys (c, d)

a) The Red Hat Enterprise Linux 9 client connecting to Legacy server supporting only ssh-rsa signature algorithm with SHA1 and providing only RSA hostkey:

$ ssh user@example.com
The authenticity of host 'example.com (1.2.3.4)' can't be established.
RSA key fingerprint is SHA256:ycznxddL1KwSN1Wbih1 UDfPntj5pM1a/kpPKLGgPzEI.
This key is not known by any other names
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added 'example.com' (RSA) to the list of known hosts.
ssh_dispatch_run_fatal: Connection to 5.6.7.8 port 22: error in libcrypto

b) The Red Hat Enterprise Linux 9 client connects to a Legacy server supporting only the ssh-rsa signature algorithm, but provides different hostkeys. The client tries to authenticate with RSA key:

$ ssh -vvv user@example.com
[...]
debug1: Next authentication method: publickey
debug1: Offering public key: /root/.ssh/id_rsa RSA SHA256:+z5NN8Z6RfNykL5l6Ht2Cbjj16xGp76TjILrQ4Cftqk
debug1: send_pubkey_test: no mutual signature algorithm
[...]
debug1: No more authentication methods to try.
user@example.com: Permission denied (publickey).

c) The Red Hat Enterprise Linux 9 server can not provide SHA1 signature for the connecting legacy clients (example RHEL6) that negotiate RSA hostkey verification:

$ ssh -vvv example.com
[...]
debug2: kex_parse_kexinit: ssh-rsa-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-dss-cert-v00@openssh.com,ssh-rsa,ssh-dss
[...]
debug2: kex_parse_kexinit: rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519
[...]
debug1: kex: server->client aes128-ctr hmac-sha1 none
debug2: mac_setup: found hmac-sha1
debug1: kex: client->server aes128-ctr hmac-sha1 none
no hostkey alg

d) The legacy client authenticates to Red Hat Enterprise Linux 9 using RSA authentication key.

$ ssh -vvv example.com
[...]
debug2: kex_parse_kexinit: hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96
[...]
debug2: kex_parse_kexinit: hmac-sha2-256-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha2-256,hmac-sha1,umac-128@openssh.com,hmac-sha2-512
[...]
debug2: mac_setup: found hmac-sha1
debug1: kex: server->client aes128-ctr hmac-sha1 none
debug2: mac_setup: found hmac-sha1
debug1: kex: client->server aes128-ctr hmac-sha1 none
no hostkey alg

Resolution

If the legacy server supports ECDSA keys, providing a new ECDSA hostkey instead of RSA will use SHA2 signatures and the RHEL9 clients will be able to verify its hostkey signatures. Legacy clients can also configure ECDSA authentication keys to access the RHEL9 servers.

As a last resort, on RHEL 9 systems, activate the SHA1 crypto-policy on top of the DEFAULT policy and reboot:

# update-crypto-policies --set DEFAULT:SHA1

Alternatively, you can switch the system-wide crypto policies to the LEGACY policy. The LEGACY crypto-policy also re-enables the SHA1 algorithm among other, no longer recommended, algorithms. This option is not recommended by Red Hat and should only be used as a workaround in cases where the SSH server configuration can't be changed.

Root Cause

The SHA-1 message digest has been deprecated in Red Hat Enterprise Linux 9. The digest produced by SHA-1 is not considered secure because of many documented successful attacks based on finding hash collisions. The RHEL core crypto components no longer allow creating and verifying SHA-1 signatures by default. Applications in RHEL 9 have been updated to avoid using SHA-1 in security-relevant use cases.

Red Hat Enterprise Linux 9 clients trying to authenticate using RSA keys against a server that does not implement the server-sig-algs extension will default to an ssh-rsa algorithm (using SHA-1 signature) to avoid connection failures and to be inline with Content from www.ietf.org is not included.RFC 8332. The RHEL9 client is also not able to verify the legacy server identity when the server provides a SHA-1 signature.

The similar problem demonstrates when legacy clients not supporting the server-sig-algs extension (RHEL6 and older) try to connect to RHEL9 servers. There is no mutual hostkey algorithm when using RSA host keys.

Diagnostic Steps

The tool ssh-keyscan from the openssh-clients package can be used to determine which keys are available on the SSH-Server side. For example the gitlab provides three keys, RSA, ECDSA and Ed25519. SHA2 with ECDSA keys are preferred over SHA1 with RSA and Ed25519 keys. The latter ones also do not work well together with older systems or are not allowed in FIPS mode:

$ ssh-keyscan gitlab.com
# gitlab.com:22 SSH-2.0-OpenSSH_8.4p1 Debian-5
gitlab.com ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCsj2bNKTBSpIYDEGk9KxsGh3mySTRgMtXL583qmBpzeQ+jqCMRgBqB98u3z++J1sKlXHWfM9dyhSevkMwSbhoR8XIq/U0tCNyokEi/ueaBMCvbcTHhO7FcwzY92WK4Yt0aGROY5qX2UKSeOvuP4D6TPqKF1onrSzH9bx9XUf2lEdWT/ia1NEKjunUqu1xOB/StKDHMoX4/OKyIzuS0q/T1zOATthvasJFoPrAjkohTyaDUz2LN5JoH839hViyEG82yB+MjcFV5MU3N1l1QL3cVUCh93xSaua1N85qivl+siMkPGbO5xR/En4iEY6K2XPASUEMaieWVNTRCtJ4S8H+9
# gitlab.com:22 SSH-2.0-OpenSSH_8.4p1 Debian-5
gitlab.com ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBFSMqzJeV9rUzU4kWitGjeR4PWSa29SPqJ1fVkhtj3Hw9xjLVXVYrU9QlYWrOLXBpQ6KWjbjTDTdDkoohFzgbEY=
# gitlab.com:22 SSH-2.0-OpenSSH_8.4p1 Debian-5
gitlab.com ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIAfuCHKVTjquxvt6CM6tdG4SLp1Btn/nOeHHE5UOzRdf
# gitlab.com:22 SSH-2.0-OpenSSH_8.4p1 Debian-5
# gitlab.com:22 SSH-2.0-OpenSSH_8.4p1 Debian-5

The SSH debug output shows that the server supports the server-sig-algs extension to send a list of public key algorithms that the server is able to process as part of a "publickey" authentication request.

$ ssh -v example.com
[...]
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,sk-ssh-ed25519@openssh.com,ssh-rsa,rsa-sha2-256,rsa-sha2-     512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,sk-ecdsa-sha2-nistp256@openssh.com,webauthn-sk-ecdsa-sha2-nistp256@openssh.com>

When this extension is not available, clients will negotiate ssh-rsa (RSA/SHA-1) signature algorithm to avoid connection failures but since SHA-1 is not allowed in the DEFAULT crypto policy the connection to the server can’t be established.

This solution is part of Red Hat’s fast-track publication program, providing a huge library of solutions that Red Hat engineers have created while supporting our customers. To give you the knowledge you need the instant it becomes available, these articles may be presented in a raw and unedited form.