Re: [IPsec] DH keys calculation performance

[Hugo Krawczyk <[e-mail]>]

Regarding Dan's suggestion (*) of using g^x, g^{x+1}, etc as successive DH
values, I would like to note the following.

This would lead to situations where two parties exchange successive keys of
the form g^{xy} and g^{(x+1)(y+1)}=g^{xy}*g^x*g^y*g.
In this case, if an attacker learns the key g^{xy} it also learns the next
key, something that violates key-exchange security (i.e. security against
"known key attacks"). However, if one models the key derivation function
applied to g^{xy} as a random oracle then this usage is probably ok (I did
not prove it), assuming the attacker does not have access to g^{xy} before
hashing. This is a weaker security property than the one achieved by always
choosing x and y afresh (in which case we have proof of security without
resorting to random oracle assumptions and without assuming that the
attacker never gets to see g^{xy}).

In a performance-vs-security tradeoff one may choose to use this method, but
one should be aware that there is a trade-off here.

Hugo

(*) I am not blaming Dan. I actually suggested that trick in my 1995 SKEME
paper as a way to improve over the suggestion of re-using the same exponent
in multiple exchanges as proposed at the time in the Photuris protocol. It
indeed improved over Photuris but today I would be more careful about
suggesting that.

On Tue, Jul 26, 2011 at 10:55 AM, Dan Harkins <[e-mail]> wrote:

>
>  Hello,
>
> On Tue, July 26, 2011 6:03 am, Prashant Batra (prbatra) wrote:
> > Thanks Yoav and Yaron  for the suggestions.
> >
> > Even I was thinking and tried generating and storing the key pair  well
> > in the beginning,.  This helped to some extent.
> >
> >
> >
> > The secret calculation is also very expensive, but this has to be done
> > in midst of the exchange only.
>
>   You could pick one secret x and then for IKE exchanges do this:
>
> 0th exchange: y = g^x mod p
> 1st exchange: y = g^(x+1) mod p
> 2nd exchange: y = g^(x+2) mod p
> .
> .
> .
> nth exchange: y = g^(x+n) mod p
>
> Getting from exchange i to exchange i+1, then, is just a single modular
> multiply, which should be "cheaper" for you.
>
>  Knowing n, y, g and p and that y = g^(x+n) mod p does not really give
> an advantage (above the discrete logarithm problem) in finding x. That
> said, I still would not suggest doing many more than a few of these (and
> I am not qualified to quantify that statement) but for a few-- i.e. keep
> n small and after n choose a new x and repeat-- it should be OK.
>
>  Maybe this technique will allow you to "cheapen" your exchange a bit.
> I think throwing hardware at this problem is your best bet though.
>
>  regards,
>
>  Dan.
>
>
> _______________________________________________
> IPsec mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/ipsec
>