Rafail Ostrovsky - Publications

Forward Security in Password-Only Key Exchange Protocols

Jonathan Katz, Rafail Ostrovsky, Moti Yung


Password-only authenticated key exchange (PAKE) protocols are designed to be secure even when users choose short, easily-guessed passwords. Security requires, in particular, that the protocol cannot be broken by an off-line dictionary attack in which an adversary enumerates all possible passwords in an attempt to determine the correct one based on previously-viewed transcripts. Recently, provably-secure protocols for PAKE were given in the idealized random oracle/ideal cipher models [BPR00,BMP00,MPS00] and in the standard model based on general assumptions [GL01] or the DDH assumption [KOY01].

The latter protocol (the KOY protocol ) is currently the only known efficient solution based on standard assumptions. However, only a proof of basic security for this protocol has appeared. In the basic setting the adversary is assumed not to corrupt clients (thereby learning their passwords) or servers (thereby modifying the value of stored passwords). Simplifying and unifying previous work, we present a natural definition of security which incorporates the more challenging requirement of forward secrecy . We then demonstrate via an explicit attack that the KOY protocol as originally presented is not secure under this definition. This provides the first natural example showing that forward secrecy is a strictly stronger requirement for PAKE protocols. Finally, we present a slight modification to the KOY protocol which prevents the attack and --- as the main technical contribution of this paper --- rigorously prove that the modified protocol achieves forward secrecy.

comment: Appeared in Proceedings of Security in Communication Netowrks 2002 conference (SCN-2002).

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.