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
.
- Download PAKtelnet and PAKftp from: (Downloading has been temporarily
suspended.)
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