Security proofs for an efficient password-based key exchange

ABSTRACT

Password-based key exchange schemes are designed to provide entities communicating over a public network, and sharing a (short) password only, with a session key (e.g, the key is used for data integrity and/or confidentiality). The focus of the present paper is on the analysis of very efficient schemes that have been proposed to the IEEE P1363 Standard working group on password-based authenticated key-exchange methods, but which actual security was an open problem. We analyze the AuthA key exchange scheme and give a complete proof of its security. Our analysis shows that the AuthA protocol and its multiple modes of operations are provably secure under the computational Diffie-Hellman intractability assumption, in both the random-oracle and the ideal-ciphers models.

REFERENCES

• 1: Mihir Bellare , Alexandra Boldyreva , Anand Desai , David Pointcheval, Key-Privacy in Public-Key Encryption, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.566-582, December 09-13, 2001
• 2: Mihir Bellare , Tadayoshi Kohno , Chanathip Namprempre, Authenticated encryption in SSH: provably fixing the SSH binary packet protocol, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586112]
• 3: M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated Key Exchange Secure Against Dictionary Attacks. In Eurocrypt '00, LNCS 1807, pages 139--155. Springer-Verlag, Berlin, 2000.
• 4: M. Bellare and P. Rogaway. The AuthA Protocol for Password-Based Authenticated Key Exchange. Contributions to IEEE P1363. March 2000. Available from http://grouper.ieee.org/groups/1363/.
• 5: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 6: Steven M. Bellovin , Michael Merritt, Encrypted Key Exchange: Password-Based Protocols SecureAgainst Dictionary Attacks, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.72, May 04-06, 1992
• 7: Steven M. Bellovin , Michael Merritt, Augmented encrypted key exchange: a password-based protocol secure against dictionary attacks and password file compromise, Proceedings of the 1st ACM conference on Computer and communications security, p.244-250, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168618]
• 8: S. Blake-Wilson, V. Gupta, C. Hawk, and B. Moeller. ECC Cipher Suites for TLS, February 2002. IEEE RFC 20296.
• 9: Nikita Borisov , Ian Goldberg , David Wagner, Intercepting mobile communications: the insecurity of 802.11, Proceedings of the 7th annual international conference on Mobile computing and networking, p.180-189, July 2001, Rome, Italy [doi>10.1145/381677.381695]
• 10: Colin Boyd , Paul Montague , Khanh Quoc Nguyen, Elliptic Curve Based Password Authenticated Key Exchange Protocols, Proceedings of the 6th Australasian Conference on Information Security and Privacy, p.487-501, July 11-13, 2001
• 11: V. Boyko, P. MacKenzie, and S. Patel. Provably Secure Password Authenticated Key Exchange Using Diffie-Hellman. In Eurocrypt '00, LNCS 1807, pages 156--171. Springer-Verlag, Berlin, 2000.
• 12: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Group Diffie-Hellman Key Exchange Secure against Dictionary Attacks, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.497-514, December 01-05, 2002
• 13: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Security proofs for an efficient password-based key exchange, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948142]
• 14: E. Bresson, O. Chevassut, and D. Pointcheval. Encrypted Key Exchange using Mask Generation Function. Work in progress.
• 15: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 16: Oded Goldreich , Yehuda Lindell, Session-Key Generation Using Human Passwords Only, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.408-432, August 19-23, 2001
• 17: Jonathan Katz , Rafail Ostrovsky , Moti Yung, Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.475-494, May 06-10, 2001
• 18: J. Katz, R. Ostrovsky, and M. Yung. Forward Secrecy in Password-only Key Exchange Protocols. In Proc. of SCN '02, 2002.
• 19: Secure password-based cipher suite for TLS, ACM Transactions on Information and System Security (TISSEC), v.4 n.2, p.134-157, May 2001 [doi>10.1145/501963.501965]
• 20: D. Taylor. Using SRP for TLS Authentication, november 2002. Internet Draft.
• 21: IEEE Standard 1363--2000. Standard Specifications for Public Key Cryptography. IEEE. Available from http://grouper.ieee.org/groups/1363, August 2000.
• 22: IEEE Standard 1363.2 Study Group. Password-Based Public-Key Cryptography. Available from http://grouper.ieee.org/groups/1363/passwdPK.
• 23: Wireless Application Protocol. Wireless Transport Layer Security Specification, February 2000. WAP TLS, WAP-199 WTLS.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

General Terms:
Algorithms, Design, Security, Standardization

Keywords:
key exchange, password-based authentication