Description of problem:
A FIPS-enabled client communicating with a FIPS-enabled server may negotiate non-FIPS algorithms and then fail to connect under default configurations.

Version-Release number of selected component (if applicable):
8.7p1-34.el9

How reproducible:
100% reproducible

Steps to Reproduce:
1. (On a FIPS-enabled host) docker run --rm -it quay.io/centos/centos:stream9
2. dnf install openssh-clients
3. ssh fips-host.domain.tld

Actual results:
kex_gen_client: Key exchange type c25519 is not allowed in FIPS mode
ssh_dispatch_run_fatal: Connection to 1.2.3.4 port 22: invalid argument

Expected results:
The SSH connection should complete. Both client and server share approved kex algorithms; the check just happens too late in the process after a disallowed algorithm has been chosen. If you run ssh -o KexAlgorithms=ecdh-sha2-nistp384 fibs-host.domain.tld, the connection does complete as expected.


Additional info:
The issue reproduces on Fedora Rawhide.

Select output from the -vv level:
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: local client KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256,curve25519-sha256,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,ext-info-c
debug2: host key algorithms: ecdsa-sha2-nistp256-cert-v01,ecdsa-sha2-nistp384-cert-v01,ecdsa-sha2-nistp521-cert-v01,sk-ecdsa-sha2-nistp256-cert-v01,rsa-sha2-512-cert-v01,rsa-sha2-256-cert-v01,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,sk-ecdsa-sha2-nistp256,rsa-sha2-512,rsa-sha2-256
debug2: ciphers ctos: aes256-gcm,chacha20-poly1305,aes256-ctr,aes128-gcm,aes128-ctr
debug2: ciphers stoc: aes256-gcm,chacha20-poly1305,aes256-ctr,aes128-gcm,aes128-ctr
debug2: MACs ctos: hmac-sha2-256-etm,hmac-sha1-etm,umac-128-etm,hmac-sha2-512-etm,hmac-sha2-256,hmac-sha1,umac-128,hmac-sha2-512
debug2: MACs stoc: hmac-sha2-256-etm,hmac-sha1-etm,umac-128-etm,hmac-sha2-512-etm,hmac-sha2-256,hmac-sha1,umac-128,hmac-sha2-512
debug2: compression ctos: none,zlib,zlib
debug2: compression stoc: none,zlib,zlib
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: curve25519-sha256,curve25519-sha256,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256
debug2: host key algorithms: rsa-sha2-512,rsa-sha2-256,ssh-rsa,ecdsa-sha2-nistp256,ssh-ed25519
debug2: ciphers ctos: aes256-ctr,aes192-ctr,aes128-ctr
debug2: ciphers stoc: aes256-ctr,aes192-ctr,aes128-ctr
debug2: MACs ctos: hmac-sha2-512,hmac-sha2-256
debug2: MACs stoc: hmac-sha2-512,hmac-sha2-256
debug2: compression ctos: none,zlib
debug2: compression stoc: none,zlib
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug1: kex: algorithm: curve25519-sha256
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: aes256-ctr MAC: hmac-sha2-256 compression: none
debug1: kex: client->server cipher: aes256-ctr MAC: hmac-sha2-256 compression: none
debug1: kex: curve25519-sha256 need=32 dh_need=32
debug1: kex: curve25519-sha256 need=32 dh_need=32
kex_gen_client: Key exchange type c25519 is not allowed in FIPS mode