Analysis of the insecurity of ECMQV with partially known nonces

NP Smart, P Leadbitter

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

8 Citations (Scopus)

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 contributionAnalysis of the insecurity of ECMQV with partially known nonces
Original languageEnglish
Title of host publicationInformation Security Conference - ISC 2003
PublisherSpringer Berlin Heidelberg
Pages240 - 251
Number of pages11
Volume2851
Publication statusPublished - Aug 2003

Bibliographical note

Conference Proceedings/Title of Journal: Proceedings ISC 2003

Fingerprint Dive into the research topics of 'Analysis of the insecurity of ECMQV with partially known nonces'. Together they form a unique fingerprint.

Cite this