A framework for password-based authenticated key exchange1

ABSTRACT

In this paper, we present a general framework for password-based authenticated key exchange protocols, in the common reference string model. Our protocol is actually an abstraction of the key exchange protocol of Katz et al. and is based on the recently introduced notion of smooth projective hashing by Cramer and Shoup. We gain a number of benefits from this abstraction. First, we obtain a modular protocol that can be described using just three high-level cryptographic tools. This allows a simple and intuitive understanding of its security. Second, our proof of security is significantly simpler and more modular. Third, we are able to derive analogs to the Katz et al. protocol under additional cryptographic assumptions. Specifically, in addition to the DDH assumption used by Katz et al., we obtain protocols under both the quadratic and N-residuosity assumptions. In order to achieve this, we construct new smooth projective hash functions.

REFERENCES

• 1: 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]
• 2: Mihir Bellare , Phillip Rogaway, Entity authentication and key distribution, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.232-249, January 1994, Santa Barbara, California, United States
• 3: Bellare, M., Pointcheval, D., and Rogaway, P. 2000. Authenticated key exchange secure against dictionary attacks. In Eurocrypt 2000, Springer-Verlag (LNCS 1807), New York. 139--155.
• 4: 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
• 5: 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]
• 6: Boyko, V., MacKenzie, P., and Patel, S. 2000. Provably secure password-authenticated key exchange using Diffie--Hellman. In Eurocrypt 2000, Springer-Verlag (LNCS 1807), New York. 156--171.
• 7: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited, Journal of the ACM (JACM), v.51 n.4, p.557-594, July 2004 [doi>10.1145/1008731.1008734]
• 8: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 9: Camenisch, J. and Shoup, V. 2003. Practical verifiable encryption and decryption of discrete logarithms. In CRYPTO'03, Springer-Verlag (LNCS 2729), New York. 126--144.
• 10: 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
• 11: Ronald Cramer , Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.45-64, May 02, 2002
• 12: Ronald Cramer , Victor Shoup, Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack, SIAM Journal on Computing, v.33 n.1, p.167-226, 2004 [doi>10.1137/S0097539702403773]
• 13: Ivan Damgard , Jens Groth, Non-interactive and reusable non-malleable commitment schemes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780605]
• 14: Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276722]
• 15: Giovanni Di Crescenzo , Jonathan Katz , Rafail Ostrovsky , Adam Smith, Efficient and Non-interactive Non-malleable Commitment, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.40-59, May 06-10, 2001
• 16: Diffie, W. and Hellman, M. E. 1976. New directions in cryptography. IEEE Trans. on Inf. Theory, IT-22. 644--654.
• 17: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 18: Dwork, C. 1999. The Non-malleability lectures. Course notes for CS 359, Stanford University, Spring. Available at: theory.stanford.edu/~gdurf/cs359-s99.
• 19: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 20: 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
• 21: Shai Halevi , Hugo Krawczyk, Public-key cryptography and password protocols, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.230-268, Aug. 1999 [doi>10.1145/322510.322514]
• 22: 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]
• 23: Jonathan Katz , Zvi Galil, Efficient cryptographic protocols preventing "man-in-the-middle" attacks, 2002
• 24: 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
• 25: Stefan Lucks, Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys, Proceedings of the 5th International Workshop on Security Protocols, p.79-90, April 07-09, 1997
• 26: MacKenzie, P. and Yang, K. 2004. On Simulation-Sound Commitments. Proc. of EUROCRYPT'04, Springer LNCS 3027, New York. 382--400.
• 27: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 28: Pascal Paillier, Low-Cost Double-Size Modular Exponentiation or How to Stretch Your Cryptoprocessor, Proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography, p.223-234, March 01-03, 1999
• 29: S. Patel, Number theoretic attacks on secure password schemes, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.236, May 04-07, 1997
• 30: Michael Steiner , Gene Tsudik , Michael Waidner, Refinement and extension of encrypted key exchange, ACM SIGOPS Operating Systems Review, v.29 n.3, p.22-30, July 1995 [doi>10.1145/206826.206834]
• 31: Wu, T. 1998. The secure remote password protocol. In 1998 Internet Society Symposium on Network and Distributed System Security. 97--111.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security, Theory

Keywords:
Passwords, authentication, dictionary attack, projective hash functions