05250346

a

05250346 Krawczyk, Hugo HMQV: A high-performance secure Diffie-Hellman protocol. (Extended abstract). Shoup, Victor (ed.), Advances in cryptology -- CRYPTO 2005. 25th annual international cryptology conference, Santa Barbara, CA, USA, August 14--18, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28114-2/pbk). Lecture Notes in Computer Science 3621, 546-566 (2005). 2005 Berlin: Springer EN Zbl 1016.94025 Zbl 0981.94032

doi:10.1007/11535218_33

Summary: The MQV protocol of [{\it L. Law}, {\it A. Menezes}, {\it M. Qu}, {\it J. Solinas} and {\it S. Vanstone}, ``An efficient protocol for authenticated key agreement", Des. Codes Cryptography 28, No. 2, 119--134 (2003; Zbl 1016.94025)] possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication. In addition to great performance, the protocol has been designed to achieve a remarkable list of security properties. As a result MQV has been widely standardized, and has recently been chosen by the NSA as the key exchange mechanism underlying ``the next generation cryptography to protect US government information''. One question that has not been settled so far is whether the protocol can be proven secure in a rigorous model of key-exchange security. In order to provide an answer to this question we analyze the MQV protocol in the Canetti-Krawczyk model [{\it R. Canetti} and {\it H. Krawczyk}, ``Analysis of key-exchange protocols and their use for building secure channels", Lect. Notes Comput. Sci. 2045, 453--474 (2001; Zbl 0981.94032)] of key exchange. Unfortunately, we show that MQV fails to a variety of attacks in this model that invalidate its basic security as well as many of its stated security goals. On the basis of these findings, we present HMQV, a carefully designed variant of MQV, that provides the same superb performance and functionality of the original protocol but for which all the MQV's security goals can be formally proved to hold in the random oracle model under the computational Diffie-Hellman assumption. We base the design and proof of HMQV on a new form of ``challenge-response signatures'', derived from the Schnorr identification scheme, that have the property that both the challenger and signer can compute the same signature; the former by having chosen the challenge and the latter by knowing the private signature key.