An unknown key-share attack on the MQV key agreement protocol

ABSTRACT

The MQV key agreement protocol, a technique included in recent standards, is shown in its basic form to be vulnerable to an unknown key-share attack. Although the attack's practical impact on security is minimal---a key confirmation step easily prevents it---the attack is noteworthy in the principles it illustrates about protocol design. First, minor "e;efficiency improvements"e; can significantly alter the security properties of a protocol. Second, protocol analysis must consider potential interactions with all parties, not just those that are normally online. Finally, attacks must be assessed in terms of system requirements, not just in isolation.

REFERENCES

• 1: Martín Abadi , Roger Needham, Prudent Engineering Practice for Cryptographic Protocols, IEEE Transactions on Software Engineering, v.22 n.1, p.6-15, January 1996 [doi>10.1109/32.481513]
• 2: ADAMS,C.AND FARRELL, S. 1999. Internet X.509 public key infrastructure certificate management protocols. IETF RFC 2510.
• 3: Ross J. Anderson , Roger M. Needham, Robustness Principles for Public Key Protocols, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.236-247, August 27-31, 1995
• 4: ANSI. 2000. ANSI X9.63, Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. ANSI. Working draft. June 15, 2001.
• 5: BAEK,J.AND KIM, K. 2000. Remarks on the unknown key-share attacks. IEICE Trans. Fund. E83-A, 12 (Dec.), 2766-2769.
• 6: BELLARE,M.AND ROGAWAY, P. 1995a. Optimal asymmetric encryption-How to encrypt with RSA. In Advances in Cryptology-EUROCRYPT '94 Proceedings, A. D. Santis, Ed., vol. 950, Lecture Notes in Computer Science, Springer-Verlag, New York, 92-111.
• 7: Mihir Bellare , Phillip Rogaway, Provably secure session key distribution: the three party case, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.57-66, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225084]
• 8: BELLARE,M.AND ROGAWAY, P. 1996. The exact security of digital signatures: How to sign with RSA and Rabin. In Advances in Cryptology-EUROCRYPT '96 Proceedings, U. M. Maurer, Ed., vol. 1070, Lecture Notes in Computer Science, Springer-Verlag, New York, 399-416.
• 9: BELLARE, M., BOLDYREVA, A., AND MICALI, S. 2000. Public-key encryption in a multi-user setting: Security proofs and improvements. In Advances in Cryptology-EUROCRYPT 2000 Proceedings, B. Preneel, Ed., vol. 1807, Springer-Verlag, New York, 259-274.
• 10: Simon Blake-Wilson , Alfred Menezes, Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol, Proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography, p.154-170, March 01-03, 1999
• 11: Simon Blake-Wilson , Don Johnson , Alfred Menezes, Key Agreement Protocols and Their Security Analysis, Proceedings of the 6th IMA International Conference on Cryptography and Coding, p.30-45, December 17-19, 1997
• 12: BONEH, D. 1999. Twenty years of attacks on the RSA cryptosystem. Not. Am. Math. Soc. (AMS) 46, 2, 203-213.
• 13: CORELLA, F. 2000. Structured certificates and their applications to distributed systems security. Presented at RSA Conference 2000 (San Jose, Calif., Jan. 16-20).
• 14: DIFFIE,W.AND HELLMAN, M. 1976a. Multiuser cryptographic techniques. In Proceedings of AFIPS National Computer Conference, 109-112.
• 15: DIFFIE,W.AND HELLMAN, M. 1976b. New directions in cryptography. IEEE Trans. Info. Theor. 22,6 (Nov.), 644-654.
• 16: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 17: EL GAMAL, T. 1985. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theor. 31, 469-472.
• 18: ELLISON, C., FRANTZ, B., LAMPSON, B., RIVEST, R., THOMAS,B.,AND YLONEN, T. 1999. SPKI certificate theory. IETF RFC 2693.
• 19: GOSS, K. 1990. Cryptographic method and apparatus for public key exchange with authentication. U.S. Patent No. 4,956,865.
• 20: Shouichi Hirose , Susumu Yoshida, An Authenticated Diffie-Hellman Key Agreement Protocol Secure Against Active Attacks, Proceedings of the First International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.135-148, February 05-06, 1998
• 21: IEEE. 2000. IEEE Std 1363-2000: Standard Specifications for Public Key Cryptography. IEEE.
• 22: IEEE P1363 Working Group. 2001. IEEE P1363a D10 (Draft Version 10):Standard Specifications for Public Key Cryptography: Additional Techniques. IEEE P1363 Working Group. Working draft. Available from http://grouper.ieee.org/groups/1363/.
• 23: David P. Jablon, Strong password-only authenticated key exchange, ACM SIGCOMM Computer Communication Review, v.26 n.5, p.5-26, Oct. 1996 [doi>10.1145/242896.242897]
• 24: KALISKI,JR., B. S. 1998. Compatible cofactor multiplication for Diffie-Hellman primitives. Electron. Lett. 34, 25 (Dec. 10), 2396-2397.
• 25: LAW, L., MENEZES, A., QU, M., SOLINAS,J.,AND VANSTONE, S. 1998. An efficient protocol for authenticated key agreement. Tech. Rep. CORR 98-05, Department of C&O, University of Waterloo. Also available from http://grouper.ieee.org/groups/1363/.
• 26: Chae Hoon Lim , Pil Joong Lee, A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroupp, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.249-263, August 17-21, 1997
• 27: MATSUMOTO, T., TAKASHIMA,Y.,AND IMAI, H. 1986. On seeking smart public-key distribution systems. Trans. IECE Japan E69, 99-106.
• 28: MENEZES, A., QU, M., AND VANSTONE, S. 1995a. Key agreement and the need for authentication. Presented at Public Key Solutions '95 (Toronto, Nov.).
• 29: MENEZES, A., QU, M., AND VANSTONE, S. 1995b. Some new key agreement protocols providing mutual implicit authentication. In Proceedings of the Second Workshop on Selected Areas in Cryptography (SAC '95, Ottawa, May 18-19), 22-32.
• 30: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 31: MENEZES,A.J.,QU, M., AND VANSTONE, S. A. 1995c. Some new key agreement protocols providing implicit authentication. Manuscript.
• 32: MYERS, M., ANKNEY, R., MALPANI, A., GALPERIN,S.,AND ADAMS, C. 1999. X.509 Internet public key infrastructure online certificate status protocol-OCSP. IETF RFC 2560.
• 33: SHOUP, V. 1999. On formal models for secure key exchange. Tech. Rep. RZ 3120, April, IBM Research Report. Revised version available from http://www.shoup.net/papers/.
• 34: VAN OORSCHOT,P.AND WIENER, M. 1996. On Diffie-Hellman key agreement with short exponents. In Advances in Cryptology-EUROCRYPT '96 Proceedings, U. M. Maurer, Ed., Lecture Notes in Computer Science, vol. 1070, Springer-Verlag, New York, 332-343.
• 35: VANSTONE, S., MENEZES,A.J.,AND QU, M. 1998. Key agreement and transport protocol with implicit signatures. U.S. Patent No. 5,761,305.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Standards (e.g., DES, PGP, RSA)

General Terms:
Algorithms, Security

Keywords:
Key agreement, MQV, protocol design, unknown key-share attack