Re: comments on ikev2 05 (cryptography)

[Hugo Krawczyk <hugo@ee.technion.ac.il>]

In answer to your discussion below:

The exponent was set to 160 bits since the best attacks that are known 
against DH keys that use exponents of length t bits (and when the order of
the DH group is a Sophie-Germain prime, i.e. a prime of
the form 2q+1 for prime q)  are of complexity 2^(t/2).
Since Oakley (and then IKEv1 and now IKEv2) specifies groups of
Sophie-Germain prime order, then an exponent of 160 bits will give you
security of (at most) 2^80. This was considered sufficient at the time of
publishing the ikev1 rfc.

Now people seem concerned with strengths of 2^128, and there is a
popular belief that you should not do anything that allows attacks under
2^90 operations. If so, 160 bits (or attack complexity of 2^80 or
less) are not sufficent.

Moreover, the use of 160 bits assumes that no (even small) improvement on
cryptanalytical methods will happen. And there is the (implicit)
assumption that all implementations will use the standard groups, or
non-standard groups of Sophie-Germain prime order (an assumption that is
not specified anywhere in IKE v1/v2).  Note that if one uses regular
primes, say a random prime of the required length, then we ALREADY know of
attacks better than the 2^(t/2) bound (i.e better than 2^80 with exponents
of length 160) [van Oorschot-Wiener, ca 1995].

Moreover, the "square root attacks" (such as lambda or shanks)
are parallelizable, making their 2^80 complexity not immediately practical
but certainly weaker than anything people are advocating for ikev2/ipsec.

Hugo

On Sun, 9 Mar 2003 Charlie_Kaufman@notesdev.ibm.com wrote:

> 
> 
> 
> 
> "Andrew Krywaniuk" <askrywan@hotmail.com> wrote:
> > I seem to remember from Hillarie's earlier paper on key sizes that the
> size
> > of the exponent is not the dominant factor that contributes to the
> strength
> > of the DH exchange. When you increase the modulus from 1024 bits to 2048
> > bits, you now have to do 2048 bit multiplies instead of 1024 bit
> multiples
> > and that also involves a lot more memory reads. The order of this effect
> is
> > sub-exponential, but still very significant.
> >
> > Could this be why the exponent size was set to 160?
> 
> Yes.
> 
> Generally, when doing Diffie-Hellman exchanges, the exponent size can be
> substantially smaller than the modulus size without losing security. There
> is a substantial performance gain by doing so. The only question is what
> the appropriate size exponent is to match a 1024 bit modulus. The text said
> 160, but Hugo suggested that 180 or 200 would be more appropriate. I'm
> certainly willing to take his word for it. For a 2048 bit modulus, the
> exponent size would be bigger, but no where near double. There's probably a
> table in some cryptographer's handbook somewhere.
> 
>           --Charlie
> 
> Opinions expressed may not even be mine by the time you read them, and
> certainly don't reflect those of any other entity (legal or otherwise).
> 
>