Authenticated key exchange secure against dictionary attacks

Authors: Mihir Bellare, David Pointcheval, and Phillip Rogaway

Reference: Advances in Cryptology - Eurocrypt '00. . Lecture Notes in Computer Science, volume 1807, B. Preneel, editor. Springer-Verlag, 2000, pp 139-155.

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.

Availability: Paper available as PDF or PostScript or gzipped-PostScript

The AuthA Protocol for Password-Based Authenticated Key Exchange

Authors: Mihir Bellare and Phillip Rogaway

Reference: An unpublished contribution to IEEE P1363

Abstract: We suggest a simple protocol, AuthA, for the problem of password-based authenticated key exchange (AKE). We assume the asymmetric trust model: the client A has a password pwa and the server B has a particular one-way function of this, pwb. Two flows of the protocol comprise a Diffie-Hellman key exchange, using a group on which the Diffie-Hellman problem is hard. At least one of these two flows is encrypted using the key pwb. Then an authentication tag, AuthA, is flowed from the client to the server. This tag is just the hash of some values easily computable by both parties. The server checks the received tag prior to accepting the session key.

The protocol just sketched provides security against dictionary attack, and it ensures forward secrecy and client-to-server authentication. Server-to-client authentication can be added cheaply, by flowing a second authentication tag, AuthB, from server to client.

Like most work in this area, our protocol springs from ideas of Bellovin and Merritt [BeMe92,BeMe93]. There has been a large body of other follow-on to this, including protocol suggestions by [STW95, Ja96, Ja97, Lu97, MS99, Wu98, RCW98, BESW00, BMP00]. But AuthA would seem to be somewhat simpler and more efficient than prior suggestions.

Rigorous proofs and definitions in this domain turn out to be extremely complex, and a proof of security (in the random-oracle model or the ideal-cipher model, under the Diffie-Hellman assumption) is the subject of ongoing work by the authors. Definitions appear in [BPR00] as does a proof for the symmetric protocol at the core of what is described here.

Availability: Paper available as PDF or PostScript or gzipped-PostScript

Rogaway's home page.