openssh unix dev - May 2015 - [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

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150527/eab16e75/attachment.bin>

On Wed 2015-05-27 18:02:40 -0400, mancha wrote:
> 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.
Their Legendre symbol of g^(ab) is 1 bit; but the full |2q| group is 1
bit larger than the |q| subgroup.  Either way, we're not talking about a
radical change in cryptographic strength, right?  Or is there some way
to parlay knowledge of the Legendre symbol of g^(ab) into a larger attack?

   --dkg

On Wed, May 27, 2015 at 07:28:09PM -0400, Daniel Kahn Gillmor
wrote:
> On Wed 2015-05-27 18:02:40 -0400, mancha wrote:
> > 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.
> 
> Their Legendre symbol of g^(ab) is 1 bit; but the full |2q| group is 1
> bit larger than the |q| subgroup.  Either way, we're not talking about
> a radical change in cryptographic strength, right?  Or is there some
> way to parlay knowledge of the Legendre symbol of g^(ab) into a larger
> attack?
Your intuition is correct. Using a generator of the full (Z/pZ)* is of
more concern for El Gamal because of the compromised semantic security
(being able to derive the cleartext's Legendre symbol can be potentially
very bad).

I brought it up in this thread to offer a possible explanation for the
NIST recommendations you were discussing.

That said, we should be much more concerned that p be a "safe prime"
so
we're assured the g we end up using generates a large group (order q or
2q assuming we don't pick g=1 or g=p-1).

On Mark's report, g=5 indeed generates the full (Z/pZ)* for the prime(*)
initially recommended in bug 2302's fix. But, that's no different
from generators in the full moduli file. My quick test shows all 274
generate the associated full groups.  

That's moot now because the fallback is a 4096-bit prime taken from RFC
3526 [1]. According to my tests, that p is a safe prime(**) and the
recommended generator g=2 generates the subgroup order q.

--mancha

[1] https://tools.ietf.org/html/rfc3526#page-5

(*)  Certified with PRIMO: https://tinyurl.com/nrqrrcg
(**) Certified with PRIMO: https://tinyurl.com/nwvezog &
https://tinyurl.com/o2cxju7
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150528/32c18e92/attachment.bin>

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

On Fri 2015-06-12 01:52:54 -0400, Mark D. Baushke wrote:
> 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.
I think this answer "begs the question" -- yes, the mathematical test
verifies that y generates a subgroup of size q.  But the question we
were discussing is why does the subgroup need to be of size q instead of
size p-1?  

     --dkg