zbMATH — the first resource for mathematics

Two-server password-only authenticated key exchange. (English) Zbl 1277.94059
Summary: Typical protocols for password-based authentication assume a single server that stores all the information (e.g., the password) necessary to authenticate a user. An inherent limitation of this approach, assuming low-entropy passwords are used, is that the user’s password is exposed if this server is ever compromised. To address this issue, it has been suggested to share a user’s password information among multiple servers, and to have these servers cooperate (possibly in a threshold manner) when the user wants to authenticate. We show here a two-server version of the password-only key-exchange protocol of Katz, Ostrovsky, and Yung (the KOY protocol). Our work gives the first secure two-server protocol for the password-only setting (in which the user need remember only a password, and not the servers’ public keys), and is the first two-server protocol (in any setting) with a proof of security in the standard model. Our work thus fills a gap left by the work of the second author et al. [J. Cryptology 19, No. 1, 27–66 (2006; Zbl 1096.94032)] and M. Di Raimondo and R. Gennaro [J. Comput. Syst. Sci. 72, No. 6, 978–1001 (2006; Zbl 1100.68571)]. As an additional benefit of our work, we show modifications that improve the efficiency of the original KOY protocol.

94A62 Authentication, digital signatures and secret sharing
Full Text: DOI
[1] Bellare, M.; Pointcheval, D.; Rogaway, P., Authenticated key exchange secure against dictionary attacks, (), 139-155 · Zbl 1082.94533
[2] Bellare, M.; Rogaway, P., Random oracles are practical: A paradigm for designing efficient protocols, (), 62-73
[3] Bellare, M.; Rogaway, P., Entity authentication and key distribution, (), 232-249 · Zbl 0870.94019
[4] Bellare, M.; Rogaway, P., Provably secure session key distribution: the three party case, (), 57-66 · Zbl 0916.94006
[5] Bellovin, S.M.; Merritt, M., Encrypted key exchange: password-based protocols secure against dictionary attacks, (), 72-84
[6] Bellovin, S.M.; Merritt, M., Augmented encrypted key exchange: A password-based protocol secure against dictionary attacks and password file compromise, (), 244-250
[7] Boyarsky, M., Public-key cryptography and password protocols: the multi-user case, (), 63-72
[8] Boyko, V.; MacKenzie, P.; Patel, S., Provably secure password-authenticated key exchange using diffie-hellman, (), 156-171 · Zbl 1082.94535
[9] J. Brainard, A. Juels, B. Kaliski, M. Szydlo, Nightingale: A new two-server approach for authentication with short secrets, in: 12th USENIX Security Symp., 2003, pp. 201-213.
[10] Canetti, R.; Goldreich, O.; Halevi, S., The random oracle methodology, revisited, J. ACM, 51, 4, 557-594, (2004) · Zbl 1204.94063
[11] Canetti, R.; Halevi, S.; Katz, J.; Lindell, Y.; MacKenzie, P., Universally-composable password authenticated key exchange, (), 404-421 · Zbl 1137.94367
[12] R. Cramer, Modular design of secure yet practical cryptographic protocols, PhD thesis, CWI and University of Amsterdam, 1996. · Zbl 0903.94025
[13] Cramer, R.; Damgård, I.; Schoenmakers, B., Proofs of partial knowledge and simplified design of witness hiding protocols, (), 174-187 · Zbl 0939.94546
[14] Cramer, R.; Shoup, V., Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM J. comput., 33, 1, 167-226, (2003) · Zbl 1045.94013
[15] Diffie, W.; Hellman, M., New directions in cryptography, IEEE trans. inform. theory, 22, 6, 644-654, (1976) · Zbl 0435.94018
[16] Di Raimondo, M.; Gennaro, R., Provably secure threshold password-authenticated key exchange, J. comput. system sci., 72, 6, 978-1001, (2006) · Zbl 1100.68571
[17] El Gamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE trans. inform. theory, 31, 469-472, (1985) · Zbl 0571.94014
[18] W. Ford, B.S. Kaliski, Server-assisted generation of a strong secret from a password, in: Proc. 5th IEEE Intl. Workshop on Enterprise Security, 2000.
[19] Gennaro, R.; Lindell, Y., A framework for password-based authenticated key exchange, ACM trans. inf. syst. secur., 9, 2, 181-234, (2006)
[20] Goldreich, O.; Lindell, Y., Session-key generation using human passwords only, J. cryptology, 19, 3, 241-340, (2006), preliminary version in Crypto 2001 · Zbl 1103.68513
[21] Gong, L.; Lomas, T.M.A.; Needham, R.M.; Saltzer, J.H., Protecting poorly-chosen secrets from guessing attacks, IEEE J. sel. areas commun., 11, 5, 648-656, (1993)
[22] Halevi, S.; Krawczyk, H., Public-key cryptography and password protocols, ACM trans. inf. syst. secur., 2, 3, 230-268, (1999)
[23] Jablon, D., Strong password-only authenticated key exchange, ACM comput. commun. rev., 26, 5, 5-20, (1996)
[24] Jablon, D., Password authentication using multiple servers, (), 344-360 · Zbl 0968.68048
[25] S. Jiang, G. Gong, Password based key exchange with mutual authentication, Workshop on Selected Areas of Cryptography (SAC), 2004.
[26] Katz, J.; Ostrovsky, R.; Yung, M., Efficient password-authenticated key exchange using human-memorable passwords, J. ACM, 57, 1, 78-116, (2009)
[27] Lomas, T.M.A.; Gong, L.; Saltzer, J.H.; Needham, R.M., Reducing risks from poorly-chosen keys, ACM oper. syst. rev., 23, 5, 14-18, (1989)
[28] Lucks, S., Open key exchange: how to defeat dictionary attacks without encrypting public keys, (), 79-90 · Zbl 0903.94040
[29] MacKenzie, P., An efficient two-party public-key cryptosystem secure against adaptive chosen-ciphertext attack, (), 47-61 · Zbl 1033.94533
[30] MacKenzie, P.; Patel, S.; Swaminathan, R., Password-authenticated key exchange based on RSA, Intl. J. information security, 9, 6, 387-410, (2010)
[31] MacKenzie, P.; Shrimpton, T.; Jakobsson, M., Threshold password-authenticated key exchange, J. cryptology, 19, 1, 27-66, (2006) · Zbl 1096.94032
[32] Szydlo, M.; Kaliski, B., Proofs for two-server password authentication, (), 227-244 · Zbl 1079.94574
[33] T. Wu, The secure remote password protocol, in: Proc. Internet Society Symp. on Network and Distributed System Security, 1998, pp. 97-111.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.