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
Attachment:
pgpp2wT6A0VLj.pgp
Description: PGP signature
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev