Abstract
When designing password-authenticated key exchange protocols (as opposed to key exchange protocols authenticated using crypto-graphically secure keys), one must not allow any information to be leaked that would allow verification of the password (a weak shared key), since an attacker who obtains this information may be able to run an off-line dictionary attack to determine the correct password. We present a new protocol called PAK which is the first Diffie-Hellman-based password-authenticated key exchange protocol to provide a formal proof of security (in the random oracle model) against both passive and active adversaries. In addition to the PAK protocol that provides mutual explicit authentication, we also show a more efficient protocol called PPK that is provably secure in the implicit-authentication model. We then extend PAK to a protocol called PAK-X, in which one side (the client) stores a plaintext version of the password, while the other side (the server) only stores a verifier for the password. We formally prove security of PAK-X, even when the server is compromised. Our formal model for password-authenticated key exchange is new, and may be of independent interest.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. J. of Cryptology, 4(2):75–122, 1991.
M. Bellare, R. Canetti, and H. Krawczyk. A modular approach to the design and analysis of authentication and key exchange protocols. In STOC’98, pages 419–428.
M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key exchange secure against dictionary attacks. In EUROCRYPT 2000, pages 139–155.
M. Bellare and P. Rogaway. Entity authentication and key distribution. In CRYPTO’93, pages 232–249.
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM Security (CCS’93), pages 62–73.
M. Bellare and P. Rogaway. Optimal asymmetric encryption. In EUROCRYPT’94, pages 92–111.
M. Bellare and P. Rogaway. Provably secure session key distribution—the three party case. In STOC’95, pages 57–66.
S. M. Bellovin and M. Merritt. Encrypted key exchange: Password-based protocols secure against dictionary attacks. In Proceedings of IEEE Security and Privacy, pages 72–84, 1992.
S. M. Bellovin and M. Merritt. Augmented encrypted key exchange: A password-based protocol secure against dictionary attacks and password file compromise. In ACM Security (CCS’93), pages 244–250.
S. Blake-Wilson, D. Johnson, and A. Menezes. Key agreement protocols and their security analysis. In Sixth IMA Intl. Conf. on Cryptography and Coding, 1997.
D. Boneh. The decision Diffie-Hellman problem. In Proceedings of the Third Algorithmic Number Theory Symposium, volume 1423 of Lecture Notes in Computer Science, pages 48–63. Springer-Verlag, 1998.
M. Boyarsky. Public-key cryptography and password protocols: The multi-user case. In ACM Security (CCS’99), pages 63–72.
V. Boyko, P. MacKenzie, and S. Patel. Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman (full version). http://www.bell-labs.com/user/philmac/research/pak.ps.gz
R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In STOC’98, pages 209–218.
W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, 22(6):644–654, 1976.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithm. IEEE Trans. Info. Theory, 31:469–472, 1985.
E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In CRYPTO’99, pages 537–554.
L. Gong. Optimal authentication protocols resistant to password guessing attacks. In 8th IEEE Computer Security Foundations Workshop, pages 24–29, 1995.
L. Gong, T. M. A. Lomas, R. M. Needham, and J. H. Saltzer. Protecting poorly chosen secrets from guessing attacks. IEEE Journal on Selected Areas in Communications, 11(5):648–656, June 1993.
S. Halevi and H. Krawczyk. Public-key cryptography and password protocols. In ACM Security (CCS’98), pages 122–131.
D. Jablon. Strong password-only authenticated key exchange. ACM Computer Communication Review, ACM SIGCOMM, 26(5):5–20, 1996.
D. Jablon. Extended password key exchange protocols immune to dictionary attack. In WETICE’97 Workshop on Enterprise Security, 1997.
T. M. A. Lomas, L. Gong, J. H. Saltzer, and R. M. Needham. Reducing risks from poorly chosen keys. ACM Operating Systems Review, 23(5):14–18, Dec. 1989. Proceedings of the 12th ACM Symposium on Operating System Principles.
S. Lucks. Open key exchange: How to defeat dictionary attacks without encrypting public keys. In Proceedings of the Workshop on Security Protocols, 1997.
P. MacKenzie and R. Swaminathan. Secure network authentication with password information. manuscript.
S. Patel. Number theoretic attacks on secure password schemes. In Proceedings of IEEE Security and Privacy, pages 236–247, 1997.
V. Shoup. On formal models for secure key exchange. IBM Research Report RZ 3120. April, 1999.
M. Steiner, G. Tsudik, and M. Waidner. Refinement and extension of encrypted key exchange. ACM Operating System Review, 29:22–30, 1995.
T. Wu. The secure remote password protocol. In NDSS’98, pages 97–111.
T. Wu. A real world analysis of Kerberos password security. In NDSS’99.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boyko, V., MacKenzie, P., Patel, S. (2000). Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_12
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67517-4
Online ISBN: 978-3-540-45539-4
eBook Packages: Springer Book Archive