Strong password-only authenticated key exchange

ABSTRACT

A new simple password exponential key exchange method (SPEKE) is described. It belongs to an exclusive class of methods which provide authentication and key establishment over an insecure channel using only a small password, without risk of offline dictionary attack. SPEKE and the closely-related Diffie-Hellman Encrypted Key Exchange (DH-EKE) are examined in light of both known and new attacks, along with sufficient preventive constraints. Although SPEKE and DH-EKE are similar, the constraints are different. The class of strong password-only methods is compared to other authentication schemes. Benefits, limitations, and tradeoffs between efficiency and security are discussed. These methods are important for several uses, including replacement of obsolete systems, and building hybrid two-factor systems where independent password-only and key-based methods can survive a single event of either key theft or password compromise.

REFERENCES

• 1: [And94] R. J. Anderson and T. M. A. Lomas, "Fortifying Key Negotiation Schemes with Poorly Chosen Passwords", Electronics Letters, v. 30, n. 13, June 23, 1994, pp. 1040-1041.
• 2: [Bel96] S. M. Bellovin, private communication.
• 3: 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
• 4: [BM93] S. M. Bellovin and M. Merritt, "An Attack on the Interlock Protocol When Used for Authentication", I.E.E.E. Transactions on Information Theory, v. 40, n. 1, January 1994, pp. 273-275.
• 5: [BM94] S. M. Bellovin and M. Merritt, "Augmented Encrypted Key Exchange: a Password-Based Protocol Secure Against Dictionary Attacks and Password File Compromise", AT&T Bell Laboratories (c. 1994).
• 6: [DH79] W. Diffie and M. E. Hellman, "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the I.E.E.E., vol. 67, No. 3, pp. 397-427 (Mar. 1979).
• 7: 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]
• 8: Carl M. Ellison, Establishing identity without certification authorities, Proceedings of the 6th conference on USENIX Security Symposium, Focusing on Applications of Cryptography, p.7-7, July 22-25, 1996, San Jose, California
• 9: [GLNS93] L. Gong, M. Lomas, R. Needham, & J. Saltzer, "Protecting Poorly Chosen Secrets from Guessing Attacks", I.E.E.E. Journal on Selected Areas in Communications, Vol. 11, No. 5, June 1993, pp. 648-656.
• 10: Li Gong, Optimal authentication protocols resistant to password guessing attacks, Proceedings of the 8th IEEE workshop on Computer Security Foundations, p.24, March 13-15, 1995
• 11: Barry Jaspan, Dual-workfactor encrypted key exchange: efficiently preventing password chaining and dictionary attacks, Proceedings of the 6th conference on USENIX Security Symposium, Focusing on Applications of Cryptography, p.5-5, July 22-25, 1996, San Jose, California
• 12: [McC90] K. McCurley, "The Discrete Logarithm Problem", Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42, 1990, pp. 49-74.
• 13: [NIST94] National Institute of Standards and Technology, NIST FIPS PUB 186, "Digital Signature Standard", U.S. Department of Commerce, May 1994.
• 14: [PH78] Pohlig & Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", I.E.E.E. Transactions on Information Theory, pp. 106-110, January 1978.
• 15: [Sch96] B. Schneier, "Applied Cryptography Second Edition", John Wiley & Sons, 1996.
• 16: 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]
• 17: [TA91] J. Tardo & K. Alagappan, "SPX: Global authentication using public key certificates", Proceedings of I.E.E.E. Computer Society Symposium on Research in Security and Privacy, Oakland, pp. 232-244, May 1991.
• 18: [vOW96] P. C. van Oorschot, M. J. Wiener, "On Diffie-Hellman Key Agreement with Short Exponents", Proceedings of Eurocrypt '96, Springer-Verlag, May 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Design, Performance, Security, Theory