I am coming late to this thread. mancha <mancha1@xxxxxxxx> 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@xxxxxxxx> 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 _______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
