Diffie-Hellman implementation causes key exchange to hang and consume CPU

[mzhurovich]

Hi,

We've recently faced an issue when our JRuby app started hanging and consuming CPU while trying to connect to SFTP server and exchange keys using diffie-hellman-group-exchange-sha256 algorithm. Here is the backtrace:

   java.lang.Thread.State: RUNNABLE
    at java.math.MutableBigInteger.divideKnuth(MutableBigInteger.java:1227)
    at java.math.MutableBigInteger.divideKnuth(MutableBigInteger.java:1163)
    at java.math.MutableBigInteger.divide2n1n(MutableBigInteger.java:1316)
    at java.math.MutableBigInteger.divide3n2n(MutableBigInteger.java:1362)
    at java.math.MutableBigInteger.divide2n1n(MutableBigInteger.java:1330)
    at java.math.MutableBigInteger.divide3n2n(MutableBigInteger.java:1362)
    at java.math.MutableBigInteger.divide2n1n(MutableBigInteger.java:1326)
    at java.math.MutableBigInteger.divideAndRemainderBurnikelZiegler(MutableBigInteger.java:1293)
    at java.math.BigInteger.divideAndRemainderBurnikelZiegler(BigInteger.java:2293)
    at java.math.BigInteger.remainderBurnikelZiegler(BigInteger.java:2282)
    at java.math.BigInteger.remainder(BigInteger.java:2254)
    at java.math.BigInteger.mod(BigInteger.java:2561)
    at java.math.BigInteger.lucasLehmerSequence(BigInteger.java:982)
    at java.math.BigInteger.passesLucasLehmer(BigInteger.java:912)
    at java.math.BigInteger.primeToCertainty(BigInteger.java:892)
    at java.math.BitSieve.retrieve(BitSieve.java:203)
    at java.math.BigInteger.largePrime(BigInteger.java:761)
    at java.math.BigInteger.<init>(BigInteger.java:667)
    at org.jruby.ext.openssl.PKeyDH.generateX(PKeyDH.java:220)
    at org.jruby.ext.openssl.PKeyDH.generateX(PKeyDH.java:228)
    at org.jruby.ext.openssl.PKeyDH.generate_key(PKeyDH.java:246)

IIUC, it happens because current implementation tries to generate not just a random number, but a prime random number:

        // adapting algorithm from org.bouncycastle.crypto.generators.DHKeyGeneratorHelper,
        // which seems a little stronger (?) than OpenSSL's (OSSL just generates a random,
        // while BC generates a random potential prime [for limit > 0], though it's not
        // subject to Miller-Rabin [certainty = 0], but is subject to other constraints)
        // see also [ossl]/crypto/dh/dh_key.c #generate_key

I'm not a cryptography expert, but maybe it's worth to make it closer to OSSL implementation and not try generating prime here?

[kares]

interesting, thanks for the report. how long are those hangs approximately, do they eventually finish?

would compare this with BC and recent OSSL but it seems to have worked so far (for a long time).

one improvement I see immediately is that we're using the default SecureRandom here, which is fine and should use /dev/urandom but it might not depending on how your setup is (Java version and JOPTS). you could try forcing SHA1PRNG if you're on Open/Oracle JRE, if it resolves the hangs ...

[mzhurovich]

@kares It may hang for dozens of minutes and when it eventually finishes the socket is already closed by timeout. I think the time required to generate the number is proportional to the key length, and usually is negligible, that's why it worked so far. However, looks like in our case the server is configured so that the required length is significantly larger. Here's the debug output from JRuby:

I, [2019-10-31T17:39:27.363308 #514145]  INFO -- net.ssh.transport.algorithms[816]: sending KEXINIT
D, [2019-10-31T17:39:27.368308 #514145] DEBUG -- socket[818]: queueing packet nr 0 type 20 len 1156
D, [2019-10-31T17:39:27.369769 #514145] DEBUG -- socket[818]: sent 1160 bytes
D, [2019-10-31T17:39:27.376016 #514145] DEBUG -- socket[818]: read 336 bytes
D, [2019-10-31T17:39:27.378375 #514145] DEBUG -- socket[818]: received packet nr 0 type 20 len 332
I, [2019-10-31T17:39:27.380145 #514145]  INFO -- net.ssh.transport.algorithms[816]: got KEXINIT from server
I, [2019-10-31T17:39:27.381418 #514145]  INFO -- net.ssh.transport.algorithms[816]: negotiating algorithms
D, [2019-10-31T17:39:27.385910 #514145] DEBUG -- net.ssh.transport.algorithms[816]: negotiated:
* kex: diffie-hellman-group-exchange-sha256
* host_key: ssh-rsa
* encryption_server: aes128-cbc
* encryption_client: aes128-cbc
* hmac_client: hmac-sha2-256
* hmac_server: hmac-sha2-256
* compression_client: none
* compression_server: none
* language_client:
* language_server:
D, [2019-10-31T17:39:27.388627 #514145] DEBUG -- net.ssh.transport.algorithms[816]: exchanging keys
D, [2019-10-31T17:39:28.076169 #514145] DEBUG -- socket[818]: queueing packet nr 1 type 34 len 20
D, [2019-10-31T17:39:28.077273 #514145] DEBUG -- socket[818]: sent 24 bytes
D, [2019-10-31T17:39:28.222214 #514145] DEBUG -- socket[818]: read 1048 bytes
D, [2019-10-31T17:39:28.224078 #514145] DEBUG -- socket[818]: received packet nr 1 type 31 len 1044
--> Hangs here, see backtrace in the issue description
D, [2019-10-31T18:13:41.699189 #514145] DEBUG -- socket[818]: sent 1040 bytes
D, [2019-10-31T18:13:41.700453 #514145] DEBUG -- socket[818]: read 24 bytes
D, [2019-10-31T18:13:41.701360 #514145] DEBUG -- socket[818]: received packet nr 2 type 1 len 20
Net::SSH::Disconnect: disconnected:  (11)

And the output of successful sftp -vvv to the same server for comparison:

debug1: kex: algorithm: diffie-hellman-group-exchange-sha256
debug1: kex: host key algorithm: ssh-rsa
debug1: kex: server->client cipher: aes128-ctr MAC: hmac-sha2-256 compression: none
debug1: kex: client->server cipher: aes128-ctr MAC: hmac-sha2-256 compression: none
debug3: send packet: type 34
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(2048<8192<8192) sent
debug3: receive packet: type 31
debug1: got SSH2_MSG_KEX_DH_GEX_GROUP
debug2: bits set: 4169/8192
debug3: send packet: type 32
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug3: receive packet: type 33
debug1: got SSH2_MSG_KEX_DH_GEX_REPLY

I don't think that switching to another RNG could help, since the issue is in prime number generation.

[silkPK]

i tried with jruby 9.4.2.0 but the result is the same.
From the SSH server logs:
"Using arbitrary primes is not allowed in FIPS mode. Falling back to known groups."
It seems that the problem is always the generation of primes as reported in #272

[kares]

please bundle update jruby-openssl to >= 0.14.1 - it's not yet part of any released JRuby artifact, yet

[silkPK]

Thank you! Patching jruby-complete with jruby-openssl 0.14.1 solve my problem.
https://github.com/jruby/jruby/issues/7353

[mzhurovich]

👏