[JSch-users] DHGEX failing with 2048-bit key under Java 8, but succeeding with 1024-bit key

[Tim B. <tb...@al...>]

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.

Tim