Lucent Logo

PAK

A protocol for Password-Authenticated Key Exchange


Background

How do you set up a secure session between a server and a remote user over the Internet (or any insecure network), while only requiring the user to remember a short password?  To set up a secure session, you must perform a key exchange, and to prevent man-in-the-middle attacks (among other attacks) it must be authenticated.  But the only shared information between the user and server is based on a short password!   This is a classic problem, and has been studied for many years.  Some popular solutions, or at least partial solutions, to this problem are: (1) telnet, which sends passwords unencrypted, and thus is vulnerable to passive eavesdropping attacks, (2) challenge-response protocols, which are vulnerable to offline dictionary attacks by an eavesdropping adversary, and (3) ssh, which requires the user to know the public key of the server in order to prevent active adversary attacks.  A popular Web-based solution to this problem involves SSL, which requires the user to be able to verify third-party certificates in order to prevent active adversary attacks.  In the past few years much better solutions have been proposed, but only recently have any solutions been formally shown to be secure.

The PAK protocol

The PAK protocol is an efficient protocol for password-authenticated key exchange which has been formally shown to be secure against active attackers, where "active" implies that an attacker can intercept, replay, modify, and/or insert messages between any parties.  Note that this allows for an attacker to impersonate a server.  The definition of formal security is somewhat technical, but essentially it means that the best an active attacker can do is guess passwords and verify them one-by-one online through communication with an honest party.  In particular, this implies that the attacker will not get any information that would allow an offline dictionary attack.  (For those interested in cryptography, what we actually show is that breaking this protocol implies breaking the Diffie-Hellman problem, and the proof is given in the random oracle, or ideal hash function, model.)  Some extended versions of PAK (such as those in the software that can be downloaded) are also resilient to server-compromise, meaning essentially that plaintext passwords are not stored on the server, and an attacker that compromises the server's password file would still need to perform a dictionary attack to break into the system.

Protocol Description

Here we give a short description of the PAK protocol, suitable for someone familiar with cryptography (in particular, the Diffie-Hellman protocol), but not necessarily familiar with password authentication.  It starts by showing some naive methods for trying to authenticate a Diffie-Hellman protocol, then proceeds to a simplified version of PAK, and finally ends with the full version of the PAK protocol that is resilient to server compromise.

Download

PAK-enabled versions of telnet and ftp are now available for free download under a non-exclusive non-commercial license.  They should compile on any UNIX systems.  These are mainly designed for research purposes, and were built on top of the SRP distribution (with the SRP protocol replaced by the PAK protocol).  You may also need to download a big number package, either gmp, cryptolib, or openssl, if you do not have one already installed on your system.  Links to these can be found on the SRP .

Papers

Diffie-Hellman based:

RSA-based:

Links

See Integrity Sciences and SRP for information on other work in this area.
 

Back to Phil MacKenzie's home page