Re: DH group exchange (Re: SSH key algorithm updates)

["Mark D. Baushke" <[e-mail]>]

Peter Gutmann <[e-mail]> writes:

> Mark D. Baushke <[e-mail]> writes:
> 
> >The root case is the selection of the generator g in RFC 4419 is not
> >sufficient to meet FIPS requirements.
> 
> Since RFC 4419 doesn't specify that q is included in the DH keying material,
> how do you even verify that it meets FIPS requirements? 
 
Perhaps I am misreading RFC 4419...

 
| 3.  Diffie-Hellman Group and Key Exchange
| 
|    The server keeps a list of safe primes and corresponding generators
|    that it can select from.  A prime p is safe if p = 2q + 1 and q is
|    prime.  New primes can be generated in the background.
| 
|    The generator g should be chosen such that the order of the generated
|    subgroup does not factor into small primes; that is, with p = 2q + 1,
|    the order has to be either q or p - 1.  If the order is p - 1, then
|    the exponents generate all possible public values, evenly distributed
|    throughout the range of the modulus p, without cycling through a
|    smaller subset.  Such a generator is called a "primitive root" (which
|    is trivial to find when p is "safe").
| ...
| 3.  C generates a random number x, where 1 < x < (p-1)/2.  It
|        computes e = g^x mod p, and sends "e" to S.

To me, the term '(p-1)/2' implies that we are calculating a value for
'q' ... in other words, I thought that q was a Sophie Germain prime and
an p was the safe prime.

Otherwise, I would have expected us to worry about 1 < x < (p-1)/r for
the case were p = qr + 1 ... and we have no way to make that calculation
without knowning either q or r in the first place.

> You can't actually perform the FIPS tests on it because one of the
> parameters is missing.

True, which also means that you would be unable to ensure that the
random number x is within the proper range for DH which wants 'p = rq +
1' and '1 < x < q' NOT '1 < x < rq' ... so, if the math in RFC 4419 is
using r=2, then we can calculae q as (p-1)/2 ...

> Oh, if anyone knows of any other commonly-used magic values I'm
> missing there, let me know.

I would also like this information.

> The real fix though would be to publish a quick update to '4419
> specifying a SSH_MSG_KEX_DH_GEX2_GROUP which includes the full set of
> DH parameters so that the DH values could be fully verified.

Sure. If you want to allow for things like group25 (RFC 5114), then
having all of the group parameters g,p,q would make it possible. I would
have no problems with that addition.

So far, we have FIPS certified our system with ssh a number of times
with RFC 4419 extensions being available, but assuming that q is derived
from (p-1)/2.

I still think that the update to RFC 4419 should deal with the selection
of the parameters and runtime validation checks per FIPS 186 and NIST SP
800-56A.

	Thanks,
	-- Mark