Password authenticated key exchange using hidden smooth subgroups

ABSTRACT

Existing techniques for designing efficient password authenticated key exchange (PAKE) protocols all can be viewed as variations of a small number of fundamental paradigms, and all are based on either the Diffie-Hellman or RSA assumptions. In this paper we propose a new technique for the design of PAKE protocols that does not fall into any of those paradigms, and which is based on a different assumption. In our technique, the server uses the password to construct a multiplicative group with a (hidden) smooth order subgroup, where the group order depends on the password. The client uses its knowledge of the password to generate a root extraction problem instance in the server's group and a discrete logarithm problem instance in the (smooth order) subgroup. If the server constructed its group correctly based on the password, the server can use its knowledge of the group order to solve the root extraction problem, and can solve the discrete logarithm problem by leveraging the smoothness of the hidden subgroup.The resulting scheme is provably secure (in the random oracle model) under the "decision subgroup assumption." The scheme can be efficiently instantiated using composite modulus groups, in which case the client and server each perform the equivalent of a small number of modular exponentiations, and the security reduces to a simple variant of the "Φ-hiding" assumption. We provide preliminary implementation results of this instantiation.

REFERENCES

• 1: M. Abdalla and D. Pointcheval. Simple password-based encrypted key exchange protocols. In Proc. of CT-RSA 2005, LNCS 3376, pp. 191--208. Springer, 2005.
• 2: M. Bellare, D. Pointcheval and P. Rogaway. Authenticated key exchange secure against dictionary attacks. In Proc. of Eurocrypt 2000, LNCS 1807, pp. 139--155. Springer, 2000.
• 3: 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]
• 4: Mihir Bellare , Phillip Rogaway, Entity Authentication and Key Distribution, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.232-249, August 22-26, 1993
• 5: 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]
• 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: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 9: R. C. Bose and D. K. Ray-Chaudhuri. On a class of error correcting binary group codes. Inf. Control, 3, pp. 68--79, 1960.
• 10: V. Boyko, P. MacKenzie and S. Patel. Provably secure password authentication and key exchange using Diffie-Hellman. In Proc. of Eurocrypt 2000, LNCS 1807, pp. 156--171. Springer, 2000.
• 11: C. Cachin, S. Micali, M. Stadler, Computational private information retrieval with polylogarithmic communication. In Proc. of Eurocrypt 1999, LNCS 1592, pp. 402--414, Springer, 1999.
• 12: 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]
• 13: Universally-composable password-based key exchange. In Proc. of Eurocrypt 2005, LNCS 3494, pp. 404--421. Springer, 2005.
• 14: D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known. In Proc. of Eurocrypt 1996, LNCS 1070, pp. 178--189. Springer, 1996.
• 15: D. Coppersmith, Finding a small root of a univariate modular equation. In Proc. of Eurocrypt 1996, LNCS 1070, pp. 155--165. Springer, 1996.
• 16: 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
• 17: 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
• 18: Ivan Damgård , Maciej Koprowski, Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.256-271, May 02, 2002
• 19: W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, 22(6): 644--654, 1976.
• 20: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 21: R. Gennaro and Y. Lindell. A framework for password-based authenticated key exchange. In Proc. of Eurocrypt 2003, LNCS 2656, pp. 524--543. Springer, 2003.
• 22: C. Gentry and Z. Ramzan. Single-database private information retrieval with constant communication rate. In Proc. of ICALP 2005, pp. 803--814. Springer, 2005.
• 23: 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
• 24: Li Gong, Optimal authentication protocols resistant to password guessing attacks, Proceedings of the The Eighth IEEE Computer Security Foundations Workshop (CSFW '95), p.24, March 13-15, 1995
• 25: L. Gong, T. M. A. Lomas, R. M. Needham and J. H. Saltzer. Protecting poorly chosen secrets from guessing attacks. In IEEE Journal on Selected Areas in Communications, 11(5): 648--656, June 1993.
• 26: A. Hocquenghem. Codes corecteurs d'erreurs. Chiffres, 2, pp. 147--156, 1959.
• 27: IEEE Standard 1363-2000, Standard specifications for public key cryptography, 2000.
• 28: 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]
• 29: David P. Jablon, Extended Password Key Exchange Protocols Immune to Dictionary Attacks, Proceedings of the 6th Workshop on Enabling Technologies on Infrastructure for Collaborative Enterprises, p.248-255, June 18-20, 1997
• 30: S. Jiang and G. Gong. Password based key exchange with mutual authentication. In Proc. of SAC 2004, LNCS 3357, pp. 267--279. Springer, 2004.
• 31: J. Katz, R. Ostrovsky and M. Yung. Practical password-authenticated key exchange provably secure under standard assumptions. In Proc. of Eurocrypt 2001, LNCS 2045, pp. 475--494. Springer, 2001.
• 32: C. Kaufmann and R. Perlman. PDM: a new strong password-based protocol. In Usenix Security Symposium, 2001.
• 33: T. Kwon. Authentication and key agreement via memorable passwords. In Proc. of NDSS 2001. ISOC, 2001.
• 34: A. Lenstra and E. Verheul. Selecting cryptographic key sizes. In Journal of Cryptology, 14(4): 255--293, 2001.
• 35: Shu Lin , Daniel J. Costello, Error Control Coding, Second Edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 2004
• 36: 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
• 37: Philip D. MacKenzie , Sarvar Patel , Ram Swaminathan, Password-Authenticated Key Exchange Based on RSA, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.599-613, December 03-07, 2000
• 38: A. May. A tool kit for finding small roots of bivariate polynomials over the integers. In Proc. of Eurocrypt 2005, LNCS 3494, pp. 251--267. Springer, 2005.
• 39: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 40: National Institute of Standards and Technology (NIST). Announcing the Secure Hash Standard, FIPS 180-1, U.S. Department of Commerce, April, 1995.
• 41: 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
• 42: M. O. Rabin. How to exchange secrets by oblivious transfer. Unpublished manuscript, 1981.
• 43: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 44: 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]
• 45: T. Wu. The secure remote password protocol. In Proc. of NDSS 1998, pp. 97--111. ISOC, 1998.
• 46: T. Wu. A real-world analysis of Kerberos password security. In Proc. of NDSS 1999, ISOC, 1999.
• 47: M. Zhang. New approaches to password authenticated key exchange based on RSA. In Proc. of Asiacrypt 2004, LNCS 3329, pp. 230--244. Springer, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

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

General Terms:
Security

Keywords:
authentication, cryptography, key exchange, password