[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
length of exponents
I was asked in a private mail to be more explicit about my recommendation
on mandating 160 bit minimal exponent lengths and recommending 256
(and, in any case, to discourage 128 bits).
As Photuris08 already explains 1024 bit DH has a current security of about 2^n
where n ranges between 86 and 98 (this depepends on the way you extrapolate
the already implemented attacks on shorter moduli).
If one uses 160 long exponents the security becomes at most 2^80 because
of Shanks/Pollard attacks that require roughly 2^{t/2} operations to find an
exponent whose length is t (this number is independent of the modulus
length). In general, one should consider 2^80 as hard enough. So, as far as
the best one can do for 160 bit exponents is to break them in the
above complexity we are fine. Less than that becomes the weakest link in the
security of the system and thus should be avoided. Let's remember that all
the point of going through a Diffie-Hellman computation is to achieve
PERFECT FORWARD SECRECY. That is to provide strong and *long-term* security.
The point that can be more controversial is that I recommend using even
longer than 160 bit exponents. The only reason I do that is to take some
"safety margin". Any improvement on the above 2^{t/2} attacks would
put at risk the security of using 160 bits.
(BTW, these 2^{t/2} attacks are off-line attacks, no need to interact with
the "victims").
We have seen in the past results that showed that short RSA exponents
are weaker than one can expect (M. Wiener, IEEE Trans IT Vol 36 No 3).
[These results do not apply to DH exponents, I am citing it as an example of
possibly unexpected weaknesses.]
More relevant, P. van Oorschot and M. Wiener have very recent results
on attacking short DH exponents. These attacks do not directly apply
to safe primes, as recommended by Photuris; they do apply to other classes
of primes (e.g., random primes). Mostly importantly,
these results are a timely reminder of the caution with which one needs
to design protocols that are intended to keep secret information for
long time (which, as said, is the whole idea of providing perfect forward
secrecy).
Another point that was raised in this private mail is why not going beyond
1024. Of course, that is possible, but the computation penalty is bigger.
Just notice that a linear increase in exponent length translates into
a linear increase in DH computation.
On the other hand, the effect of an increase in modulus length is between
quadratic to cubic (depeneding on implementation).
(And, in any case, if one goes to longer moduli then using too short exponents
becomes an even weaker link for the security).
Bottom line: I recommend to mandate minimum 160 bit exponents so
I get (some) assurance that the product I buy gives me good security,
and even more importantly, the implementation that my partner to
communication is using gives *me* good security.
A recommendation about taking a safety margin and going beyong the 160 bits,
will also be, in my opinion, a good thing to do.
Hugo