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

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

Jeffrey Hutzelman <[e-mail]> writes:

> On Sat, 2015-11-07 at 03:33 +0000, denis bider wrote:
> 
> > It is a fairly substantial problem that most dynamically generated
> > groups aren't usable with our FIPS module.
> 
> What's broken about the groups that don't work?

The root case is the selection of the generator g in RFC 4419 is not
sufficient to meet FIPS requirements.

Start here:

  http://dx.doi.org/10.6028/NIST.SP.800-56Ar2 

in section 5.6.2.3.1 "FFC Full Public-Key Validation Routine" you will
see the tests that must be run during DH negotiation. Given the public
value y sent from the client, validate 2 <= y <= p-2 and 1=y^q mod p. Of
course, if a generator g has been selected incorrectly, then the public
key y will not have the correct order and will therefore have the
incorrect subgroup. So, we really need to take a look at how g is to be
selected. This is specified in section 5.5.1.1 "FFC Domain Parameter
Generation" which in turn specified "FFC Domain parameters shall be
generated using a method specified in [FIPS 186]," and so we move to
the latest FIPS 186 here:

  http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

Read section A.2 and note that a simple test for g is

  2 <= g <= (p-1)
  g^q = 1 mod p

The above two tests are mandatory in FIPS approved diffie-hellman.

For non-FIPS users, a g which is not a valid generator means that
the g^(ab) operation may be leaking one bit of the key (ab).

You may wish to read the thread here:

  https://lists.mindrot.org/pipermail/openssh-unix-dev/2015-June/034060.html

For our implementation of the /etc/moduli file, 

 * find prime candidates p and q where q=(p-1)/2 

 * (because we are not sure if all RFC 4419 implementations will
   accept a generator g which is not either g=2 or g=5),
   check g=2 and g=5 using the steps in
   A.2.2 "Assurance of the Validity of the Generator g"
   - if g=2 or g=5 meets the PARTIALLY VALID test,
     then use Elliptic Curve Primality Proving to validate that both p
     and q are provably prime rather than just probably prime.
     (The use of ECPP is not required, but does not hurt.)
     else throw away p and q and start over.

   If we were guaranteed that all RFC 4419 implementations were able to
   accept any small prime for g, then we could walk up the list of
   primes until we found one that meets the PARTIALLY VALID test.
   However, that might also be very slow for some embedded ssh
   processors to implement, so choosing a g=2 is a good idea in any
   case.

 * an alternative would be to populate the /etc/moduli file for RFC 4419
   with the MODP groups that are well constructed for generating
   q=(p-1)/2 So, adding RFC 3526 group15 (3072-bit MODP Group) and/or
   group16 (4096-bit MODP Group)... I do not see a good reason to add
   group17 (6144-bit MODP Group), but do it if you wish.

Because the SSH server is the one who provides the g and p values, if it
is using valid RFC 4419 moduli, the client will just work.

If the SSH server is NOT FIPS-compliant, then if the SSH client
implements the older test like A.2 where the provided g^x=1 (mod p) test
which was in older of testing the 'random' value of x as being one that
lets the g^(xy) = 1 (mod p) have a 50% of being wrong as the y^q mod p
operation will return either 1 or p-1 and all of the p-1 values are
wrong for FIPS.

I hope that you find this information useful.

----------%<----------%<----------%<----------%<----------%<----------
From: "Roginsky, Allen" <allen.roginsky at nist.gov>
Subject: RE: Question on SP 800-56A rev2

The reason the y^q=1 (mod p) tests exists is to verify that y is in the
required subgroup. In general, for any y mutually prime with p, it is
true that y^(p-1) = 1 mod p. (The Fermat's Little Theorem.) Of course,
when taking an arbitrary y into the power smaller than (p-1) the above
equality does not necessarily hold. Suppose, however, that y is a
generator of a cyclic subgroup that has q elements. This is subgroup of
a larger group that has (p-1) elements; (p-1) is a multiple of q). The
way y was selected was by taking an arbitrary number w into the power of
(p-1)/q mod p (to be sure that it is in the subgroup of order q) and
checking that the result is not 1 (mod p) (otherwise, it is in the right
subgroup but is a unit element there - not a useful case.) Now, to test
that y is in a subgroup of order q one has to check that y^q = 1 mod p.
This would indeed hold if, as designed, y=w^(p-1)/q) mod p and
therefore, y^q = [w^(p-1)/q]^q ] = w^(p-1) = 1 mod p. This is why this
test (y^q = 1 mod p) exists in FIPS 186-4. \

My guess is that the value of 5 in your vendor's example, does not
satisfy this test, so it is not a generator of a subgroup of order q.
This value 5 could not have then been generated using w^[(p-1)q] (mod p)
method.

I do not know why some other standards appear to impose the additional
requirements on g. To find a generator of the entire cyclic group of the
order of (p-1) one usually has to make many tries, so some specific
methods or restrictions may apply there, but any g not equal to 1 and
such that g = w^[(p-1)q] (mod p) is good to be a generator of the
smaller subgroup (size q), as far as I can tell.

Please do not hesitate to call me or let your vendor call if they have
any additional questions.

Regards,
Allen
----------%<----------%<----------%<----------%<----------%<----------