Subject: Re: comments on ikev2 05 (cryptography)

From: "Andrew Krywaniuk" <[email-masked]>
Date: Fri, 07 Mar 2003 18:12:47 -0500

>    The strength of a key derived from a Diffie-Hellman exchange using
>    any of the groups defined here depends on the inherent strength of
>    the group, the size of the exponent used, and the entropy provided by
>    the random number generator used. Due to these inputs it is difficult
>    to determine the strength of a key for any of the defined groups.
>    Diffie-Hellman group number two when used with a strong random number
>    generator and an exponent no less than 160 bits is sufficient to use
>    for 3DES.  Groups three through five provide greater security. Group
>
>I do not agree that 160 bits are sufficient for use with 3DES given that
these
>exponents allow for a full break of the DH exchange in 2^80
>operations. I would
>suggest a minimum of 180 or even 200 bits.

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?

Andrew
--------------------------------------
The odd thing about fairness is when
we strive so hard to be equitable
that we forget to be correct.

_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*.  
http://join.msn.com/?page=features/featuredemail

---

From: [email-masked]
Date: Sun, 9 Mar 2003 21:42:14 -0500

> 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).

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 11 Mar 2003 02:41:28 +0200 (IST)

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