Paper 2002/145

Cryptanalysis of MQV with partially known nonces

P. J. Leadbitter and N. P. Smart

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

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
MQV Lattices
Contact author(s)
nigel @ cs bris ac uk
History
2002-09-26: received
Short URL
https://ia.cr/2002/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/145,
      author = {P. J.  Leadbitter and N. P.  Smart},
      title = {Cryptanalysis of MQV with partially known nonces},
      howpublished = {Cryptology ePrint Archive, Paper 2002/145},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/145}},
      url = {https://eprint.iacr.org/2002/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.