Abstract
Typical protocols for password-based authentication assume a single server which stores all the information (e.g.), the password necessary to authenticate a user. Unfortunately, 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, a number of schemes have been proposed in which a user’s password information is shared among multiple servers, and these servers cooperate in a threshold manner when the user wants to authenticate.
We show here a two-server protocol for this task assuming public parameters available to everyone in the system (as well as the adversary). Ours is the first provably-secure two-server protocol for the important 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.
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
Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated Key Exchange Secure Against Dictionary Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: Proc. 1st ACM Conference on Computer and Communications Security, pp. 62–73. ACM, New York (1993)
Bellare, M., Rogaway, P.: Entity Authentication and Key Distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)
Bellare, M., Rogaway, P.: Provably-Secure Session Key Distribution: the Three Party Case. In: 27th ACM Symposium on Theory of Computing (STOC), pp. 57–66. ACM, New York (1995)
Bellovin, S.M., Merritt, M.: Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks. In: IEEE Symposium on Research in Security and Privacy, pp. 72–84. IEEE, Los Alamitos (1992)
Bellovin, S.M., Merritt, M.: Augmented Encrypted Key Exchange: a Password- Based Protocol Secure Against Dictionary Attacks and Password File Compromise. In: 1st ACM Conf. on Computer and Comm. Security, pp. 244–250. ACM, New York (1993)
Boyarsky, M.: Public-Key Cryptography and Password Protocols: The Multi-User Case. In: 7th Ann. Conf. on Computer and Comm. Security, pp. 63–72. ACM, New York (1999)
Boyko, V., MacKenzie, P., Patel, S.: Provably-Secure Password-Authenticated Key Exchange Using Diffie-Hellman. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 156. Springer, Heidelberg (2000)
Brainard, J., Juels, A., Kaliski, B., Szydlo, M.: Nightingale: A New Two-Server Approach for Authentication with Short Secrets. In: 12th USENIX Security Symp., pp. 201–213 (2003)
Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited. J. ACM 51(4), 557–594 (2004)
Canetti, R., Halevi, S., Katz, J., Lindell, Y., MacKenzie, P.: Universally- Composable Password Authenticated Key Exchange. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 404–421. Springer, Heidelberg (2005)
Cramer, R.: Modular Design of Secure Yet Practical Cryptographic Protocols. PhD Thesis, CWI and University of Amsterdam (1996)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure Against Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 13. Springer, Heidelberg (1998)
Diffie, W., Hellman, M.: New Directions in Cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976)
Di Raimondo, M., Gennaro, R.: Provably Secure Threshold Password- Authenticated Key Exchange. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 507–523. Springer, Heidelberg (2003)
Dodis, Y., Krohn, M., Mazieres, D., Nicolosi, A.: Proactive Two-Party Signatures for User Authentication. In: NDSS 2003 (2003)
El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31, 469–472 (1985)
Ford, W., Kaliski, B.S.: Server-Assisted Generation of a Strong Secret from a Password. In: Proc. 5th IEEE Intl. Workshop on Enterprise Security (2000)
Gennaro, R., Lindell, Y.: A Framework for Password-Based Authenticated Key Exchange. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 524–543. Springer, Heidelberg (2003)
Gilboa, N.: Two-Party RSA Key Generation. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 116–129. Springer, Heidelberg (1999)
Goldreich, O., Lindell, Y.: Session-Key Generation Using Human Passwords Only. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 408–432. Springer, Heidelberg (2001)
Gong, L., Lomas, T.M.A., Needham, R.M., Saltzer, J.H.: Protecting Poorly- Chosen Secrets from Guessing Attacks. IEEE J. on Selected Areas in Communications 11(5), 648–656 (1993)
Halevi, S., Krawczyk, H.: Public-Key Cryptography and Password Protocols. ACM Trans. Information and System Security 2(3), 230–268 (1999)
Jablon, D.: Strong Password-Only Authenticated Key Exchange. ACM Computer Communications Review 26(5), 5–20 (1996)
Jablon, D.: Password Authentication Using Multiple Servers. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 344–360. Springer, Heidelberg (2001)
Jiang, S., Gong, G.: Password Based Key Exchange With Mutual Authentication. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 267–279. Springer, Heidelberg (2004)
Katz, J., Ostrovsky, R., Yung, M.: Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 475–494. Springer, Heidelberg (2001)
Lomas, T.M.A., et al.: Reducing Risks from Poorly-Chosen Keys. ACM Operating Systems Review 23(5), 14–18 (1989)
Lucks, S.: Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys. In: Christianson, B., Lomas, M. (eds.) Security Protocols 1997. LNCS, vol. 1361, pp. 79–90. Springer, Heidelberg (1998)
MacKenzie, P., Patel, S., Swaminathan, R.: Password-Authenticated Key Exchange Based on RSA. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 599–613. Springer, Heidelberg (2000)
MacKenzie, P.: An Efficient Two-Party Public Key Cryptosystem Secure against Adaptive Chosen Ciphertext Attack. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 47–61. Springer, Heidelberg (2002)
MacKenzie, P., Reiter, M.: Networked Cryptographic Devices Resilient to Capture. IEEE Security and Privacy (2001)
MacKenzie, P., Reiter, M.: Two-Party Generation of DSA Signatures. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 137–154. Springer, Heidelberg (2001)
MacKenzie, P., Shrimpton, T., Jakobsson, M.: Threshold Password- Authenticated Key Exchange. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 385–400. Springer, Heidelberg (2002)
Shoup, V.: A Proposal for an ISO Standard for Public-Key Encryption, version 2.1. Draft (2001), Available at http://eprint.iacr.org/2001/112
Szydlo, M., Kaliski, B.: Proofs for Two-Server Password Authentication. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 227–244. Springer, Heidelberg (2005)
Wu, T.: The Secure Remote Password Protocol. In: Proc. Internet Society Symp. on Network and Distributed System Security, pp. 97–111 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Katz, J., MacKenzie, P., Taban, G., Gligor, V. (2005). Two-Server Password-Only Authenticated Key Exchange. In: Ioannidis, J., Keromytis, A., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2005. Lecture Notes in Computer Science, vol 3531. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496137_1
Download citation
DOI: https://doi.org/10.1007/11496137_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26223-7
Online ISBN: 978-3-540-31542-1
eBook Packages: Computer ScienceComputer Science (R0)