[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

[mancha]

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>