Re: Why is top bit forcibly set in DH secret exponent?

[David Martin]

I don't think setting a lower bound on x is worth the 
effort based on this explanation.  Any attacker can 
make a table of millions of x / lg x pairs --- far more 
than you are concerned about protecting --- using only 
public information.  If I wanted to attack your scheme 
in the way you are trying to protect against, I would 
just make the table of interesting values outside of 
your mandatory lower bounds for x and y.  The real 
protection here is that the probability that an earnest 
DH participant chooses values in an attacker's table is 
negligible, not that some x / lg x pairs are 
intrinsically easier than others.

To guard against implementation errors I can see why 
you might look at the sequence of exponents chosen over 
time and make sure that there's high entropy there or 
something.  But that's a different type of protection.

David
Jim Schneider wrote:
Ben Laurie wrote:

Jim Schneider wrote:
Sorry, I goofed - I thought we were talking
about generating the prime for DH, not the
subsequent operations.  In the case of the
secret exponents, there's no real justification
for it (x just needs to be larger than
C*ln(p)/ln(g), where g is the DH generator, p is
the DH prime, and C is a "big enough" constant
to prevent brute force attacks).
No, it doesn't. Why single out that part of the
search space for protection?
Cheers,
Ben.

x and y both need to be larger than ln(p)/ln(g) to
avoid a simple table lookup attack - if either one
is less than ln(p)/ln(g), the resulting g ** x or g
** y will be less than p.  If g is equal to two
(which I gather is a pretty common occurance, since
it makes the arithmetic a lot easier), the resulting
X or Y value has a single set bit.  Since g
generates a group of order p, there's a one to one
correspondence between X and Y (there has to be, or
DH doesn't work at all), so an X or Y with a single
set bit is trivial to break.
When g is greater than two, there are still
detectable patterns.  I added the factor of C
because I don't know how far the patterns extend
before they're swamped in the noise (and it makes a
sequential-from-zero brute force search pointless).
If you want a numerical value to put on
C*ln(p)/ln(g), let g equal two.  This reduces the
expression to C*lg(p), or C times the number of bits
in p.  Increasing g reduces the value of the
expression, so assuming that g is two is
conservative.  With a C of 128, and a 4096 bit p, we
limit ourselves to x and y values greater than
524288, a miniscule piece of the entire 4096 bit
range for x and y. 
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [EMAIL PROTECTED]
Automated List Manager                           [EMAIL PROTECTED]