Ubuntu FIPS libssl1.1 update breaks diffie-hellman-group-exchange-sha256 key exchange

Cannot reproduce this on any environment I have. Both multipass and QEMU/KVM installed from the Ubuntu ISO works with no problem.

I'm attaching my own log from the multipass machine here.

Log to multipass-based machine using the same command-line.

It's strange, are you sure you have the latest version of the package installed?
This is the logs I see from the client side:

debug1: kex: algorithm: diffie-hellman-group-exchange-sha256
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: aes128-ctr MAC: <email address hidden> compression: none
debug1: kex: client->server cipher: aes128-ctr MAC: <email address hidden> compression: none
debug3: send packet: type 34
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(2048<8192<8192) sent
Connection closed by 10.99.208.71 port 22

and on the server

Nov 18 13:13:58 bionic-fips sshd[3891]: debug1: SSH2_MSG_KEX_DH_GEX_REQUEST received [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_request_send entering: type 0 [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_choose_dh: waiting for MONITOR_ANS_MODULI [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_request_receive_expect entering: type 1 [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_request_receive entering [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_request_receive entering
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: monitor_read: checking request 0
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_answer_moduli: got parameters: 2048 8192 8192
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_request_send entering: type 1
Nov 18 13:13:58 bionic-fips sshd[3891]: debug2: monitor_read: 0 used once, disabling now
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: mm_choose_dh: remaining 0 [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug1: SSH2_MSG_KEX_DH_GEX_GROUP sent [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: debug3: send packet: type 31 [preauth]
Nov 18 13:13:58 bionic-fips sshd[3891]: ssh_dispatch_run_fatal: Connection from 10.99.208.1 port 58396: error in libcrypto [preauth]

The server receives the SSH2_MSG_KEX_DH_GEX_REQUEST and tries to send SSH2_MSG_KEX_DH_GEX_GROUP but something goes wrong apparently.

I will also attach the full logs for a complete session.

So, I debugged the server to see what is going on. Essentially the server is - for some reason - generating the P and (sometimes) G parameters of the Diffie-Hellman exchange wrongly. When the server tries to pinpoint the correct group, it always fail, because the group decision depends on correct P and G.

If you're willing to check it out, the function which decides the match group is dh_match_group, in the OpenSSL source, crypto/dh/dh_rfc7919.c

Note, however, that the Diffie Hellman parameters are already wrong at that point.

The relevant bt stack is this one:
(gdb) bt
#0 dh_match_group (dh=0x555555870fd0, qout=0x0, lout=0x555555870fe8) at ../crypto/dh/dh_rfc7919.c:74
#1 0x00007ffff6ea03e3 in dh_cache_nid (dh=0x555555870fd0) at ../crypto/dh/dh_rfc7919.c:149
#2 0x00007ffff6e9e58d in DH_set0_pqg (dh=0x555555870fd0, p=0x5555558721a0, q=0x0, g=0x555555872f00) at ../crypto/dh/dh_lib.c:212
#3 0x00005555555d69bd in dh_new_group (gen=0x555555872f00, modulus=0x5555558721a0) at ../../dh.c:331
#4 0x000055555558d96f in mm_choose_dh (min=2048, nbits=8192, max=8192) at ../../monitor_wrap.c:216
#5 0x00005555555e0e22 in input_kex_dh_gex_request (type=34, seq=1, ssh=0x555555874b40) at ../../kexgexs.c:100
#6 0x00005555555ce4de in ssh_dispatch_run (ssh=0x555555874b40, mode=0, done=0x555555878080) at ../../dispatch.c:113
#7 0x00005555555ce583 in ssh_dispatch_run_fatal (ssh=0x555555874b40, mode=0, done=0x555555878080) at ../../dispatch.c:133
#8 0x000055555556716d in do_ssh2_kex () at ../../sshd.c:2536
#9 0x00005555555669d9 in main (ac=7, av=0x55555584f820) at ../../sshd.c:2316

On the mm_choose_dh function of OpenSSH, the parameters are collected by using mm_request_receive_expect and extracted by using sshbuf_get_bignum2.

Here is the conclusion after some investigation:

Essentially, The openssh-fips is based on a openssh version newer than openssh. To the point where the former depends on openssl 1.1 and the latter on openssl 1.0;

That leads to the following situation: both openssh-server packages uses the /etc/ssh/moduli to get the P and G parameters for the Diffie-Hellman algorithm, but openssh-server-fips fetch them and uses libssl1.1 to check if the Diffie-Hellman group is valid. In many cases, the fetched G parameter from /etc/ssh/moduli is number 5, which isn't valid according to the criteria used by libssl1.1, so the libssl1.1 operation to get a group fails, then the openssh-server-fips operation fails as a consequence.

On the other hand, the archive openssh doesn't use libssl to check the P and G parameters, so no failures.

Unfortunately, this leads to a situation where a simple patch to bypass the check isn't possible.

For FOcal, the patch which changed the OpenSSL lib, adding the behavior to check big numbers in dh_cache_need is openssl-1.1.1-fips-dh.patch.

One proposal is to change the openssh code to select the parameters for DH from the dh modules of OpenSSL.

Hi, Atsec found a really neat solution for us:

Delete the /etc/moduli file.

The connection should proceed normally.

A fix for this issue was released for Bionic in OpenSSH 1:7.9p1-10~ubuntu18.04.fips.0.3.
Please let us know whether you have any questions or issues!

A fix for this issue was also released for Focal in OpenSSH 1:8.2p1-4ubuntu0.fips.0.4.0 today.

For Azure, a fix was implemented directly in the FIPS images because this issue was blocking the image publication process.