[Bug 2302] with DH-GEX, ssh (and sshd) should not fall back to unconfigured DH groups or at least document this behaviour and use a stronger group

[Mark D. Baushke]

I am coming late to this thread.

mancha <mancha1 at zoho.com> writes:

> On Wed, May 27, 2015 at 05:08:25PM -0400, Daniel Kahn Gillmor wrote:
> > On Tue 2015-05-26 15:39:49 -0400, Mark D. Baushke wrote:
> > > Hi Folks,
> > >
> > > The generator value of 5 does not lead to a q-ordered subgroup which
> > > is needed to pass tests in
> > >
> > > http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-2007.pdf
> > 
> > I pulled revision 2 of this document from here:
> > 
> > https://dx.doi.org/10.6028/nist.sp.800-56ar2
> > 
> > The "FFC Domain Parameter Generation" section does say:
> > 
> >     g is a generator of the cyclic subgroup of GF(p)* of order q,
> > 
> > But i don't see a recommendation of why this matters.  Surely we don't
> > want the subgroup of order 2, but what is wrong with using a subgroup
> > of order 2q = p-1?
> > 
> > There's clearly no strong security advantage to the 2q subgroup --
> > it's just one bit larger -- but is there an attack that works against
> > the 2q subgroup that doesn't work against the q subgroup?  If this is
> > a known concern, i'd be happy with just a pointer to a paper or web
> > page explaining the risks of the larger group.
> > 
> > otoh, if the goal is just to ensure we have word-for-word compliance
> > with SP800-56A, then it's clear that choosing a different generator is
> > the way to go (and without much of a security cost).  but i'd like to
> > know if there's a reason other than blind-spec-compliance.  Pointers?
> > 
> > Regards,
> > 
> >         --dkg
> 
> One reason the generator of the full (Z/pZ)* is avoided is because
> knowledge of g^a and g^b (both known to Mallory) leaks information about
> the shared secret g^(ab) via their legendre symbols.  This is
> particularly troublesome in the context of El Gamal.  
> 
> I don't have a reference to recommend off-hand but you might want to
> google for "decisional diffie hellman assumption".
> 
> --mancha

I have communicated with Allen Roginsky on this topic and I have been given permission to post his response.

In this message below, the 'vendor' was Darren Tucker's generated prime
that used a generator value of 5.

	-- Mark

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