Daniel Wichs
New York University

Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman 

When designing password-authenticated key exchange protocols (as opposed to
key exchange protocols authenticated using cryptographically secure keys),
one must not allow any information to be leaked that would allow
verification of the password (a weak shared key), since an attacker who
obtains this information may be able to run an off-line dictionary attack to
determine the correct password. Of course, it may be extremely difficult to
hide all password information, especially if the attacker may pose as one of
the parties in the key exchange. Nevertheless, we present a new protocol
called PAK which is the first Diffie-Hellman-based password-authenticated
key exchange protocol to provide a formal proof of security (in the random
oracle model) against both passive and active adversaries. In addition to
the PAK protocol that provides mutual explicit authentication, we also show
a more efficient protocol called PPK that is provably secure in the
implicit-authentication model. We then extend PAK to a protocol called
PAK-X, in which one side (the client) stores a plaintext version of the
password, while the other side (the server) only stores a verifier for the
password. We formally prove security of PAK-X, even when the server is
compromised. Our formal model for password-authenticated key exchange is
new, and may be of independent interest.

Victor Boyko, Philip MacKenzie, and Sarvar Patel