Abstract
There have been many proposals in recent years for password-authenticated key exchange protocols.Man y of these have been shown to be insecure, and the only ones that seemed likely to be proven secure (against active adversaries who may attempt to perform off-line dictionary attacks against the password) were based on the Diffie-Hellman problem. In fact, some protocols based on Diffie-Hellman have been recently proven secure in the random-oracle model. We examine how to design a provably-secure password-authenticated key exchange protocol based on RSA.We first look at the OKE and protected-OKE protocols (both RSA-based) and show that they are insecure.Then we show how to modify the OKE protocol to obtain a password-authenticated key exchange protocol that can be proven secure (in the random oracle model). The resulting protocol is very practical; in fact the basic protocol requires about the same amount of computation as the Diffie-Hellman-based protocols or the well-known ssh protocol.
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
M. Bellare, R. Canetti, and H. Krawczyk. A modular approach to the design and analysis of authentication and key exchange protocols.In STOC’98 [STO98], pages 419–428.
Donald Beaver.S ecure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4(2):75–122, 1991.
S.M. Bellovin and M. Merritt. Encrypted key exchange: Password-based protocols secure against dictionary attacks. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 72–84, 1992.
S.M. Bellovin and M. Merritt. Augumented encrypted key exchange: A password-based protocol secure against dictionary attacks and password file compromise.In CCS’93 [CCS93], pages 244–250.
V. Boyko, P. MacKenzie, and S. Patel. Provably-secure password authentication and key exchange using Diffie-Hellman.In EUROCRYPT2000 [EUR00].
M. Boyarsky. Public-key cryptography and password protocols: The multiuser case.In CCS’99 [CCS99], pages 63–72.
M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key exchange secure against dictionary attacks.In EUROCRYPT2000 [EUR00].
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In CCS’93 [CCS93], pages 62–73.
M. Bellare and P. Rogaway. Entity authentication and key distribution. In CRYPTO’ 93, LNCS vol.773, pages 232–249. Springer-Verlag, August 1993.
Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In EUROCRYPT 94, LNCS vol.950, pages 92–111. Springer-Verlag, May 1994.
M. Bellare and P. Rogaway. The exact security of digital signatures-how to sign with RSA and Rabin.In EUROCRYPT 96, pages 399–416, 1996.
E. Bach and J. Shallit. Algorithmic Number Theory: Volume 1 Efficient Algorithms.The MIT Press, Cambridge, Massachusetts, 1996.
R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In STOC’98 [STO98], pages 209–218.
W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, 22(6):644–654, 1976.
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.
L. Gong. Optimal authentication protocols resistant to password guessing attacks.In Proc. 8th IEEE Computer Security Foundations Workshop, pages 24–29, 1995.
S. Halevi and H. Krawczyk. Public-key cryptography and password protocols. In Proceedings of the Fifth Annual Conference on Computer and Communications Security, pages 122–131, 1998.
IEEE P1363 Annex D/Editorial Contribution 1c: Standard specifications for public-key cryptography, June 1998.
D. Jablon.Integrity sciences web site.http://www.IntegritySciences.com.
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.
H.W. Lenstra. Divisors in residue classes. Mathematics of Computation, 42:331–340, 1984.
Stephan Lucks.Open key exchange: How to defeat dictionary attacks without encrypting public keys.In Proc. Workshop on Security Protocols, 1997.
P. MacKenzie, S. Patel, and R. Swaminathan. Password-authenticated key exchange based on rsa. full version.
S. Patel.Number theoretic attacks on secure password schemes.I n Proc. IEEE Symposium on Research in Security and Privacy, pages 236–247, 1997.
M. Roe, B. Christianson, and D. Wheeler. Secure sessions from weak secrets. Technical report, Univ. of Cambridge and Univ. of Hertfordshire, 1998.
R. Rivest, A. Shamir and L. Adleman. A method for obtaining digital signature and public key cryptosystems. Comm. of the ACM, 21:120–126, 1978.
V. Shoup. On formal models for secure key exchange. IBM Research Report RZ 3121, 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 Proc. 1998 Internet Society Network and Distributed System Security Symposium, pages 97–111, 1998.
T. Wu. A real world analysis of kerberos password security. In 1999 Internet Society Network and Distributed System Security Symposium, 1999.
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
MacKenzie, P., Patel, S., Swaminathan, R. (2000). Password-Authenticated Key Exchange Based on RSA. In: Okamoto, T. (eds) Advances in Cryptology — ASIACRYPT 2000. ASIACRYPT 2000. Lecture Notes in Computer Science, vol 1976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44448-3_46
Download citation
DOI: https://doi.org/10.1007/3-540-44448-3_46
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41404-9
Online ISBN: 978-3-540-44448-0
eBook Packages: Springer Book Archive