Papers on Authentication and key distribution

Abstract: Entity authentication and authenticated key exchange are central problems in secure distributed computing but, up until now, they have lacked satisfactory definitions and proven-correct solutions. One consequence is that unsound or unanalyzable protocols continue to proliferate. This paper provides the first treatment of entity authentication and authenticated key exchange in the complexity-theoretic framework of modern cryptography. Addressed in detail are problems of the two-party setting: mutual authentication and mutual authentication with the concomitant exchange of a session key. We treat both the shared-key and public-key versions of these problems. For each we present a definition, protocol, and proof that the protocol achieves the definition, assuming a minimal complexity-theoretic assumption. When this assumption is appropriately instantiated, the protocols given are practical and efficient.

Ref: Extended abstract in Advances in Cryptology - Crypto 93 Proceedings, Lecture Notes in Computer Science Vol. 773, D. Stinson ed, Springer-Verlag, 1994. Full paper available below.

Abstract: We study session key distribution in the three-party setting of Needham and Schroeder. (This is the trust model assumed by the popular Kerberos authentication system.) Such protocols are basic building blocks for contemporary distributed systems---yet the underlying problem has, up until now, lacked a definition or provably-good solution. One consequence is that incorrect protocols have proliferated. This paper provides the first treatment of this problem in the complexity-theoretic framework of modern cryptography. We present a definition, protocol, and a proof that the protocol satisfies the definition, assuming the (minimal) assumption of a pseudorandom function. When this assumption is appropriately instantiated, our protocols are simple and efficient.

Ref: Extended abstract in Proc. 27th Annual Symposium on the Theory of Computing, ACM, 1995. Available below.

Abstract: We present a general framework for constructing and analyzing authentication protocols in realistic models of communication networks. This framework provides a sound formalization for the authentication problem and suggests simple and attractive design principles for general authentication and key exchange protocols. The key element in our approach is a modular treatment of the authentication problem in cryptographic protocols; this applies to the definition of security, to the design of the protocols, and to their analysis. In particular, following this modular approach, we show how to systematically transform solutions that work in a model of idealized authenticated communications into solutions that are secure in the realistic setting of communication channels controlled by an active adversary.

Using these principles we construct and prove the security of simple and practical authentication and key-exchange protocols. In particular, we provide a security analysis of some well-known key exchange protocols (e.g. authenticated Diffie-Hellman key exchange), and of some of the techniques underlying the design of several authentication protocols that are currently being deployed on a large scale for the Internet Protocol and other applications.

Ref: Extended abstract in Proc. 30th Annual Symposium on the Theory of Computing, ACM, 1998. Full version available below.

Abstract: Password-based protocols for authenticated key exchange (AKE) are designed to work despite the use of passwords drawn {from} a space so small that an adversary might well enumerate, off line, all possible passwords. While several such protocols have been suggested, the underlying theory has been lagging. We begin by defining a model for this problem, one rich enough to deal with password guessing, forward secrecy, server compromise, and loss of session keys. The one model can be used to define various goals. We take AKE (with implicit authentication) as the basic goal, and we give definitions for it, and for entity-authentication goals as well. Then we prove correctness for the idea at the center of the Encrypted Key-Exchange (EKE) protocol of Bellovin and Merritt: we prove security, in an ideal-cipher model, of the two-flow protocol at the core of EKE.

Ref: Extended abstract in Advances in Cryptology - Eurocrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. ??, B. Preneel ed, Springer-Verlag, 2000.