## Abstract

In this paper we present the first lattice attack on an authenticated
key agreement protocol, which does not use a digital signature algorithm
to produce the authentication.
We present a two stage attack on the elliptic curve variant of
MQV in which one party may recover
the other party's static private key from partial knowledge of the nonces
from several runs of the protocol.
The first stage reduces the attack to a hidden number problem which
is partially solved by considering a closest vector problem and using
Babai's algorithm.
This stage is closely related to the attack of Howgrave-Graham, Smart,
Nguyen and Shparlinski on DSA but is complicated by a non-uniform distribution
of multipliers.
The second stage recovers the rest of the key using the baby-step/giant-step
algorithm or Pollard's Lambda algorithm and runs in time $O(q^{1/4})$.
The attack has been proven to work with high probability and validated
experimentally.
We have thus reduced the security from $O(q^{1/2})$ down to $O(q^{1/4})$
when partial knowledge of the nonces is given.

Translated title of the contribution | Analysis of the insecurity of ECMQV with partially known nonces |
---|---|

Original language | English |

Title of host publication | Information Security Conference - ISC 2003 |

Publisher | Springer Berlin Heidelberg |

Pages | 240 - 251 |

Number of pages | 11 |

Volume | 2851 |

Publication status | Published - Aug 2003 |