Password-authenticated key exchange
A password-authenticated key exchange (PAKE) protocol is an authenticated key exchange between a client and a server that share only a password, drawn from a dictionary that may be small: over a network the adversary controls, each session the adversary actively attacks lets it test at most one password guess, and eavesdropping lets it test none.
Syntax
Following BPR00, there is a set of clients and a set of servers; each client holds a password , and each server holds . A PAKE protocol consists of:
- , a randomized algorithm generating public parameters, with in the plain model,
- for each user , the stateful interactive algorithm run by each instance , , of . An instance of a client communicating with a server has input , and an instance of has input . An instance processes incoming messages and eventually either rejects or accepts, outputting a partner identity , a session identity and a session key .
Two instances and are partners if one is a client instance and the other a server instance, both accepted with the same and the same session key , each one’s names the other’s user, and no other instance accepted with that — BPR00.
Properties
Correctness
If the messages between an instance of a client communicating with a server and an instance of are delivered unchanged, both instances accept, are partners, and output the same session key, except with negligible probability.
Security
The passwords are sampled independently and uniformly from , and the adversary controls all communication through four oracles — BPR00:
- delivers the message to and returns the instance’s reply and whether it has accepted or rejected; a special message starts a client instance, naming its server;
- runs an honest execution between and and returns its transcript;
- returns the session key of if it has accepted;
- returns, according to a hidden bit , the session key of () or a uniform key ().
An instance is fresh if it has accepted and no query was made to it or to its partner. is admissible if it makes exactly one query, to an instance that is fresh at the end of the game; revealing the tested instance or its partner would hand the key.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{pake}}_{\Pi,D,\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Setup(1^\secpar)$; $b \getsr \bits$
\State $\mathit{pw}_C \getsr D$ for every $C \in \mathsf{Client}$
\State $b' \gets \calA^{\mathsf{Send}, \mathsf{Execute}, \mathsf{Reveal}, \mathsf{Test}}(\pp)$
\Comment{Admissible: one $\mathsf{Test}$ query, to an instance fresh at the end}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\mathsf{Test}(U, i)$}
\begin{algorithmic}
\If{$\Pi^i_U$ has not accepted}
\Return $\bot$
\EndIf
\State $K_0 :=$ the session key of $\Pi^i_U$; $K_1 \getsr \calK$
\Return $K_b$
\end{algorithmic}
\end{algorithm}
A PAKE protocol is secure if for every dictionary , which may depend on , and all efficient admissible making queries to , there is a negligible function such that
— BPR00. The term cannot be dropped: an adversary that runs the client’s algorithm on its own password guesses against server instances succeeds with probability proportional to its number of guesses — standard. queries do not count towards , so transcripts of honest executions must not let the adversary test password guesses offline.
Variations
Forward secrecy
BPR00 also define forward secrecy, in which the adversary may in addition corrupt users and learn their passwords, and session keys established before a corruption must remain pseudorandom.
UC-secure PAKE
A UC-secure PAKE UC-realizes the password-based key-exchange functionality of CHKLM05 against a malicious adversary that corrupts parties statically, possibly in a hybrid model such as the common reference string model; a result against adaptive corruptions says so. The environment hands each party its password, so no distribution on passwords is assumed, nor independence between the passwords of different parties. The adversary may test one password guess per session instance, and a correct guess lets it choose that instance’s key; two instances of a session whose passwords match and that the adversary did not attack receive the same uniform key — CHKLM05. CHKLM05 realize in the common reference string model under standard number-theoretic assumptions, and show that it cannot be realized in the plain model — CHKLM05.
Asymmetric PAKE
In an asymmetric PAKE (aPAKE) the server stores a mapping of the password rather than the password, and security is required even after the server is compromised: apart from impersonating the server to its users, the only attack the compromise allows is an offline exhaustive dictionary attack against each user’s password. A strong aPAKE is in addition secure against pre-computation attacks, which deterministic password mappings and salts sent in the clear allow — JKX18. JKX18 define strong aPAKE in the UC framework and build it from an OPRF together with either any aPAKE or any authenticated key-exchange protocol secure against key-compromise impersonation. OPAQUE, their instantiation of the second construction, is UC-secure in the random-oracle model and has two messages, three with mutual authentication — JKX18.
TODO: the UC aPAKE functionality of GMR06, the defining paper as JKX18 cite it, stated from the paper: its server-compromise interface, its offline password tests, and whether those tests may precede the compromise, which separates aPAKE from strong aPAKE. aPAKE becomes a node only once this functionality is encoded.
Other results
- Bellovin and Merritt introduced the problem with the Encrypted Key Exchange (EKE) protocols — BM92; BPR00 prove the two-flow protocol at the core of EKE secure in an ideal-cipher model.
- In the common reference string model, DDH gives a three-round PAKE without random oracles (DDH ⇒ PAKE) — KOY01.
- GL03 generalize the protocol of KOY01 to a framework, in the common reference string model, built from non-malleable commitments, one-time signatures and smooth projective hash functions, and instantiate it under DDH, quadratic residuosity and -th residuosity.
- Without any setup or random oracle, trapdoor permutations give session-key generation from passwords alone, under a definition in which the effect of an adversary attacking an execution is comparable to a constant number of queries of the form “is the password?” — GL01.
Participates in
Produces Password-authenticated key exchange