Shai Halevi
Abstract
We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses ~a pair of private and public keys while the client has only a weak human-memorizable password as its authentication key. We present and analyze several simple password authentication protocols in this scenario, and show that the security of these protocols can be formally proven based on standard cryptographic assumptions. Remarkably, our analysis shows optimal resistance to off-line password guessing attacks under the choice of suitable public key encryption functions. In addition to user authentication, we describe ways to enhance these protocols to provide two-way authentication, authenticated key exchange, defense against server's compromise, and user anonymity. We complement these results with a proof that strongly indicates that public key techniques are unavoidable for password protocols that resist off-line guessing attacks.
As a further contribution, we introduce the notion of public passwords that enables the use of the above protocols in situations where the client's machine does not have the means to validate the server's public key. Public passwords serve as "hand-held certificates" that the user can carry without the need for specal computing devices.
- ABADI, M., LOMAS, T. M., AND NEEDHAM, R. 1997. Strengthening passwords. Tech. Note 033. SRC..]]Google Scholar
- BELLARE, M., CANETTI, R., AND K_RAWCZYK, H. 1998. A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract). In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC '98, Dallas, TX, May 23-26, 1998), J. Vitter, Ed. ACM Press, New York, NY, 419-428.]] Google Scholar
- BELLARE, M., DESAI, A., POINTCHEVAL, D., AND ROGAWAY, P. 1998. Relations among notions of security for public-key encryption schemes. In Advances in Cryptology--CRYPTO '98, H. Krawczyk, Ed. Springer-Verlag, New York, 26-45.]] Google Scholar
- BELLARE, M. AND ROGAWAY, P. 1995. Optimal asymmetric encryption--how to encrypt with rsa. In Advances in Cryptology--EUROCRYPT'94, A. D. Santis, Ed. Springer-Verlag, New York, 92-111.]]Google Scholar
- BELLOVIN, S. M. AND MERRITT, M. 1992. Encrypted key exchange: Password- based protocols secure against dictionary attacks. In Proceedings of the ACM/IEEE Symposium on Research in Security and Privacy (Oakland, CA, May). 72-84.]] Google Scholar
- BELLOVIN, S. M. AND MERRITT, M. 1993. Augmented encrypted key exchange: A passwordbased protocol secure against dictionary attacks and password file compromise. In Proceedings of the First ACM Conference on Computer and Communications Security (Fairfax, VA, Nov. 3-5, 1993), D. Denning, R. Pyle, R. Ganesan, R. Sandhu, and V. Ashby, Eds. ACM Press, New York, NY, 244-250.]] Google Scholar
- CANETTI, R., FEIGE, U., GOLDREICH, O., AND NAOR, M. 1996. Adaptively secure multi-party computation. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96, Philadelphia, PA, May 22-24 1996), G. L. Miller, Ed. ACM Press, New York, NY, 639-648.]] Google Scholar
- CRAMER, R. AND SHOUP, V. 1998. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Advances in Cryptology--CRYPTO '98, H. Krawczyk, Ed. Springer-Verlag, New York, 13-25.]] Google Scholar
- DIERKS, T. AND ALLEN, C. 1999. The TLS protocol: Version 1.0. Request for Comments: 2246. ftp ://ftp.isi. edu/in-notes/rfc2246.txt.]] Google Scholar
- DIFFIE, W., VAN OORSCHOT, P. C., AND WIENER, M.J. 1992. Authentication and authenticated key exchanges. Des. Codes Cryptography 2, 2 (June 1992), 107-125.]] Google Scholar
- DOLEV, D., DWORK, C., AND NAOR, M. 1991. Non-malleable cryptography (extended abstract). In Proceedings of the 23rd Annual ACM Symposium on Authentication and Authenticated Key Exchanges (New Orleans, LA, May). ACM Press, New York, NY, 542-552.]] Google Scholar
- EL GAMAL, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theor. 31,469-472.]]Google Scholar
- FREIER, A. O., KARLTON, P., AND KOCHER, P. C. 1996. The SSL protocol version 3.0. Internet-draft draft-freier-ssl-version3-02.txt]]Google Scholar
- GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. 1986. How to construct random functions. J. ACM 33, 4 (Oct. 1986), 792-807.]] Google Scholar
- GOLDWASSER, S. AND MICALI, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (Apr.), 270-299.]]Google Scholar
- GONG, L. A., LOMAS, T. M., NEEDHAM, R., AND SALTZER, J. 1993. Protecting poorly chosen secrets from guessing attacks. IEEE J. Sel. Areas Commun. 11, 5 (June), 648-656.]]Google Scholar
- HALLER, N. 1995. The S/KEY one-time password system. IETF RFC-1760.]] Google Scholar
- IMPAGLIAZZO, R. AND RUDICH, S. 1989. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC '89, Seattle, WA, May 15-17, 1989), D. S. Johnson, Ed. ACM Press, New York, NY, 44-61.]] Google Scholar
- JABLON, D. P. 1996. Strong password-only authenticated key exchange. SIGCOMM Comput. Commun. Rev. 26, 5, 5-26.]] Google Scholar
- KAUFMAN, C., PERLMAN, R., AND SPECINER, M. 1995. Network Security: Private Communication in a Public World. Prentice-Hall series in computer networking and distributed systems. Prentice-Hall, Inc., Upper Saddle River, NJ.]] Google Scholar
- KELSEY, J., SCHNEIER, B., HALL, C., AND WAGNER, D. 1997. Secure applications of low-entropy keys. In Proceedings of the 1997 Workshop on Information Security. Springer-Verlag, Vienna, Austria, 121-134.]] Google Scholar
- KENT, S. AND ATKINSON, R. 1998. Security architecture for the Internet protocol. In IPSEC Working Group.]] Google Scholar
- KRAWCZYK, H. 1996. SKEME: A versatile secure key exchange mechanism for internet. In Proceedings of the 1996 Internet Society Symposium on Network and Distributed System Security. 114-127.]] Google Scholar
- LAMPORT, L. 1981. Password authentication with insecure communication. Commun. ACM 24, 11 (Nov.), 770-772.]] Google Scholar
- LUCKS, S. 1997. Open key exchange: How to defeat dictionary attacks without encrypting public keys. In Proceedings of the Workshop on Security Protocol (Ecole Normale Superieure, Apr.).]] Google Scholar
- MENEZES, A. J., VAN OORSCHOT, P. C., AND VANSTONE, S.n. 1997. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL.]] Google Scholar
- NIST, 1995. NIST FIPS PUB 180-1, Secure Hash Standard. National Institute of Standards and Technology, Gaithersburg, MD.]]Google Scholar
- PATEL, S. 1997. Number theoretic attacks on secure password schemes. In Proceedings of the 1997 IEEE Symposium on Security and Privacy (Oakland, CA, MAY). IEEE Press, Piscataway, NJ, 236-247.]] Google Scholar
- RACKOFF, C. AND SIMON, D. 1991. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In Advances in Cryptology--CRYPTO '91. Springer-Verlag, New York, NY, 433-444.]] Google Scholar
- SET, 1997. SET specification version 1. http://www.setco.org/set.html]]Google Scholar
- STEINER, M., TSUDIK, G., AND WAIDNER, M. 1995. Refinement and extension of encrypted key exchange. ACM SIGOPS Oper. Syst. Rev. 29, 3 (July 1995), 22-30.]] Google Scholar
- Wu, T. 1998. The secure remote password protocol. In Proceedings of the 1998 Internet Society Symposium on Network and Distributed System Security (San Diego, CA, Mar.). 97-111.]]Google Scholar
Index Terms
- Public-key cryptography and password protocols
Recommendations
Public-key cryptography and password protocols: the multi-user case
CCS '99: Proceedings of the 6th ACM conference on Computer and communications securityThe problem of password authentication over an insecure network when the user holds only a human-memorizable password has received much attention in the literature. The first rigorous treatment was provided by Halevi and Krawczyk, who studied off-line ...
Multi-factor password-authenticated key exchange
AISC '10: Proceedings of the Eighth Australasian Conference on Information Security - Volume 105We consider a new form of authenticated key exchange which we call multi-factor password-authenticated key exchange, where session establishment depends on successful authentication of multiple short secrets that are complementary in nature, such as a ...
Yaksha: augmenting Kerberos with public key cryptography
SNDSS '95: Proceedings of the 1995 Symposium on Network and Distributed System Security (SNDSS'95)The Kerberos authentication system is based on the trusted third-party Needham-Schroeder (1978) authentication protocol. The system is one of the few industry standards for authentication systems and its use is becoming fairly widespread. The system has ...
Reviews
Adrian Constantin Atanasiu
The authors study the use of human passwords for strong authentication and key exchange in asymmetric situations, in which the authentication server can store a strong secret, while the client uses a weak human-memorizable password as its only authentication key. Several simple password authentication protocols are analyzed. Some ways to enhance these protocols to provide two-way authentication, authenticated key exchange, defense against any compromise of the server, and user anonymity are described. The authors formally prove that public key techniques are unavoidable for password protocols that are resistant to offline guessing attacks. Finally, the notion of a public password is defined, in order to enable the use of protocols when the client's machine does not have the means to validate the server's key. Public passwords serve as “hand-held certificates” that users can carry without the need for special computing devices.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments