DHGEX failing with 2048-bit key under Java 8, but

I'm using JSCH 0.1.53 to connect to a remote SSH server, which uses a 1024-bit RSA key. We are able to connect successfully to the remote server when we also use a 1024-bit RSA key, but when we generated stronger 2048-bit keys we stopped being able to connect. We got an error message that reads "prime size must be multiple of 64, and can only range from 512 to 2048" and that originates from a call to DHGEX.java (Diffie-Hellman Group EXchange).

We're running Java 1.8, and the error message correctly specifies a max bit size of 2048, so the problem is not the JCE key limitation of 1024 bits in Java 1.6 and 1.7. And we've confirmed that both our private and our public key are in fact 2048 bits, via openssl rsa -text -noout -in id_rsa and ssh-keygen -lf id_rsa.pub.

Since everything looked fine on our end, I started adding debugging lines to the JSCH code and recompiling the JAR, and I was eventually able to determine that the modulus being passed to us during the key exchange was in fact 2047 bits long. Now, 2047 bits in length doesn't inherently mean that you didn't generate a 2048-bit key or that it's any less strong than a key that actually contains 2048 bits, it just means that you happened to get two primes that multiplied together to something whose first bit was a 0. So it's expected behavior (some of the time) and the JCE check should probably be (n % 64 == 0 || n % 64 == 63). But JCE is a stickler on the point, so it rejects this key for not being of a length it considers valid.

Based on that, I thought I'd found the problem: the remote server had generated a 2048-bit key that only contained 2047 bits, so they just needed to generate a new one (and keep doing it till they got one that really was 2048 bits). But when I asked their administrators about it, they were insistent that they were using a 1024-bit key, and indeed that's what you get in the known_hosts file when you SSH over. So that doesn't appear to be the cause after all.

So I started logging the contents of the buffer that contained what they sent us and pulling out the p and g values (modulus and group), and I discovered that in just a few short periods of testing over a couple of days, there were 33 different modulus values, and all of them differed by only the last few characters when encoded in either base 64 or base 10. Modulii values were reused, sometimes only once and sometimes a dozen times, but there were lots of distinct values, so the keys are neither generated for one-time use nor generated once and reused forever.

Is this (having the server send many different keys that are very close numerically, with some reuse but many unique values) expected behavior under any conditions, and especially is this expected behavior when the client uses a 2048-bit key but the server uses a 1024-bit key? I know nothing about Diffie-Hellman group exchange besides what I've read since I started investigating last week, so maybe this is just how it works, but it seems strange to me.

Also, does the SSH standard specify anything about how keys should be generated in cases like these? I haven't yet found out what SSH server the far side is using (I suspect OpenSSH, but don't know for sure and don't know what version), but I'm hopeful that there might be some standard that forces the use of keys that are of the same size as was requested (between 1^(n-1) and 1^n - 1), and that the remote server might have an option to force this or that I can submit a bug against them to get them to change the behavior. I'll probably also submit a bug against the JDK to allow keys of n-1 bits, with 0-padding for the first bit.

Any guidance that anyone can give would be greatly appreciated.

I've also posted this question to the JSCH mailing list: https://sourceforge.net/p/jsch/mailman/message/35042955/

UPDATE:

After further reading, I believe that Diffie-Hellman's forward secrecy characteristic means that different primes (often from a pre-generated set stored somewhere like /etc/ssl/moduli) would be used for each session (source: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange#Forward_secrecy) and that the prime used is not actually the RSA key (source: https://stackoverflow.com/a/23346185/1247705), so the fact that many different p values are seen no longer seems like a concern. I'm still surprised that they're so close in value, but maybe that's expected as well.

The far side is using Solaris SSH 1.1.4 (which as I understand it is based on OpenSSH) as the SSH daemon. Is it expected that that daemon would pass 2047-bit primes as part of the Diffie-Hellman key exchange, and is there anything that can be done to get it to send 2048-bit primes instead?

回答1:

We fixed similar symptoms with:

Security.insertProviderAt(new BouncyCastleProvider(), 1)

we were using Jsch 0.1.54 and saw:

java.security.InvalidAlgorithmParameterException: DH key size must be multiple of 64, and can only range from 512 to 4096 (inclusive). The specific key size 2047 is not supported

possibly related is JDK-8164963: InvalidAlgorithmParameterException prime size issue after JDK upgrade with JSCH libraries

回答2:

I ended up working around this issue by disabling the key-exchange algorithms that used a variant of Diffie-Hellman Group key exchange. @Brian Low appears to have worked around it by using BouncyCastle instead of the JDK's built-in security provider.

I consider both of those to be workarounds that don't solve the underlying problem (which appears to be a bug in either the JDK for what key sizes they accept or in OpenSSH for what key sizes they generate), but neither I nor my project cared enough to spend time and money trying to force one or the other to take ownership of the issue.