Subject: Avoiding Small Subgroup Attack in X9.42 Diffie-Hellman

From: Russ Housley <[email-masked]>
Date: Thu, 14 Jan 1999 16:52:12 -0500

I am forwarding the following message from Robert Zuccherato.

Russ

= = = = = = = = = =

In the x942 draft we presently specify that in some instances of
ephemeral-static Diffie-Hellman, public key validation does not need to be
performed; but for static-static Diffie-Hellman, public key validation is
needed.  I would like to call to the group's attention another option.  If
the prime p is chosen so that p-1=2*q*r where r is a product of large
(greater than 160 bits) primes then the "small subgroup" attacks are not a
concern here (except for the possible loss of 1 bit of the private key).
Perhaps we could specify this as another option for those situations that
require resistance to these attacks.  

I believe that the situations where resistance to these attacks is required
will remain the same.  However, we could allow the option of choosing the
prime p to have this form.  This may be a desirable option, as it appears
that performing public key validation may be encumbered.  However, it is
not clear that this should be the only option because even with this, one
bit of the key could be leaked, which may not be acceptable in some
situations.  Also, parameter generation will become more complicated.

If we did decide to allow this option, we would then have to specify how to
choose the prime to be of this form.  We could either change the prime
generation algorithm, or we could specify that the prime generation
algorithm should be run enough number of times until this condition is met.

Thank you,

	Robert Zuccherato

---

From: [email-masked] (Peter Gutmann)
Date: Sun, 24 Jan 1999 17:16:39 (NZDT)

>generation algorithm, or we could specify that the prime generation algorithm 
>should be run enough number of times until this condition is met.
 
This is just them Lim-Lee algorithm, which is already defined fairly clearly, 
so it wouldn't be hard to include it.  I'd be quite keen on this option since 
it avoids using the (unnecessarily complex) FIPS 186 kosherizer, and has, as 
you point out, some useful properties (it may also be faster, has anyone 
compared it to the kosherizer for speed?).  One possible downside is that it's 
not so easy to generate a prime of exactly n bits, but I can't see why this 
would be a drawback.
 
Peter.