Papers on Authentication and key distribution

One of our central research projects has been to bring the provable security approach to the notoriously tough problems of authentication and session key exchange / distribution. We provide definitions and proven secure protocols for a variety of problems. The first paper in this line was Entity authentication and key distribution which looked at a two party setting and introduced a model for sessions. The three party case (Kerberos model) was addressed in the paper Provably secure session key distribution: the three party case. A simulation based approach is developed in A modular approach to the design and analysis of authentication and key exchange protocols. The paper Authenticated Key Exchange Secure Against Dictionary Attacks addresses dictionary attacks and also includes updated versions of the basic definitions of the first two papers above for the two party setting.


Entity Authentication and key distribution

Authors: M. Bellare and P. Rogaway

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.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


Provably secure session key distribution: the three party case

Authors: M. Bellare and P. Rogaway

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.

Best available version: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


A modular approach to the design and analysis of authentication and key exchange protocols

Authors: M. Bellare, R. Canetti and H. Krawczyk

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.

Full version: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


Authenticated Key Exchange Secure Against Dictionary Attacks

Authors: M. Bellare, D. Pointcheval and P. Rogaway

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.

Proceedings version: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).

Full version: Not yet available.


Related work or links