Re: [IPsec] DH keys calculation performance

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

> -----Original Message-----
> From: [e-mail] [mailto:[e-mail]] On Behalf
> Of Yoav Nir
> Sent: Tuesday, July 26, 2011 6:40 AM
> To: Prashant Batra (prbatra)
> Cc: [e-mail]
> Subject: Re: [IPsec] DH keys calculation performance
> 
> 
> On Jul 25, 2011, at 11:29 PM, Prashant Batra (prbatra) wrote:
> 
> > Hello,
> >
> > The DH exchange (Calculation of Public/Private key and the Secret)
in
> > IKEV2 Initial exchange
> > seems to be very expensive. This is slowing down the overall IKEv2
> > tunnel establishment.
> > Is there a way to optimize it?
> 
> Hi Prashant.
> 
> I know of three ways to optimize the D-H exchange.
> 
> First, note that each peer has to perform two operations:
> 
> Second, note that 2^73 mod p = ((2^64 mod p) * (2^8 mod p) * (2^1 mod
> p)) mod p If you're using a 2048-bit D-H group, you can pre-calculate
> 2^x mod p for 0<=x<=2048 and store these values.

Surely, you mean something like 0<=x<320 or so.  When you create a DH
shared secret for a MODP group, it is pointless to create a secret as
big as the prime.  Against DH, there are two known types of attacks:
	(A) Attacks that take time based on the modulus (and don't
depend on the value of the exponent at all)
	(B) Attacks that take time based on the exponent (and don't
depend that much on the value of the modulus)
What you want to do is pick your exponent just large enough that (B)
attacks take about as long as (A) attacks; making the exponent any
larger than that will make it more expensive for you without making it
any more secure (because an attacker can just go ahead with an (A)
attack); while making it smaller will make it less secure (because a (B)
attack becomes easier).

So, what's the size of such an exponent?  Well, that's a difficult
question; however, the RFC's do give guidance.  If you're using a 2048
bit exponent for 2048 bit MODP group, that's an obvious thing to fix.
If we look at RFC3526, we see that it suggests an exponent of length of
between 220 and 320 bits (it's a range because experts have different
estimates of how difficult type (A) attacks are).

Also, if you're doing groups 22-24, then it's easy; use an exponent of
the same size as 'q' (that'd be 160, 224 and 256 bits); a larger
exponent is pointless.
And, for completeness, for a ECDH group, it's also easy; use an exponent
of the same size as the curve (e.g. 256 bits for the P256 curve).