Password Authenticated Key Exchange(PAKE)
Password authentication is ubiquitous in many applications. In a common implementation, a client authenticates to a server by sending its client ID and password to the server over a secure connection. This makes the password vulnerable to server mishandling, including accidentally logging the password or storing it in plaintext in a database. Server compromise resulting in access to these plaintext passwords is not an uncommon security incident, even among security-conscious organizations. Moreover, plaintext password authentication over secure channels such as TLS is also vulnerable to cases where TLS may fail, including PKI attacks, certificate mishandling, termination outside the security perimeter, visibility to TLS-terminating intermediaries, and more.
What's a PAKE?
A PAKE protocol, first introduced by Bellovin and Merritt, is a special form of cryptographic key exchange protocol. Key exchange (or “key agreement”) protocols are designed to help two parties (call them a client and server) agree on a shared key, using public-key cryptography. The earliest key exchange protocols — like classical Diffie-Hellman — were unauthenticated, which made them vulnerable to man-in-the-middle attacks.
The distinguishing feature of PAKE protocols is the client will authenticate herself to the server using a password. For obvious reasons, the password, or a hash of it, is assumed to be already known to the server, which is what allows for checking.
If this was all we required, PAKE protocols would be easy to build.
What makes a PAKE truly useful is that it should also protect the client’s password. A stronger version of this guarantee can be stated as follows: after a login attempt (valid, or invalid) both the client and server should learn only whether the client’s password matched the server’s expected value, and no additional information. This is a powerful guarantee. It’s not dissimilar to what we ask for from a zero-knowledge proof.
The obvious problem with PAKE is that many people don’t want to run a “key exchange” protocol in the first place! They just want to verify that a user knows a password.
Some applications:
Balanced and Augmented protocols
PAKE protocols are commonly classified as either balanced or augmented.
Balanced PAKE
A balanced PAKE assumes that the two parties share a secret, which is a password or derived from a password.
Secure Requirements
- Resisting offline dictionary attacks
- Limiting online attacks to one password guess per protocol execution
- Ensuring session-key security
- Providing forward secrecy
Augmented PAKE
When a balanced PAKE is used in a client-server setting, if the secret stored on the server is stolen, it can be directly used to impersonate the client. To address this, an augmented PAKE adds a “server compromise resistance” requirement:
- Even if the server is compromised, an offline dictionary attack is needed to impersonate the client.
This is typically realized by requiring that the client remember a password, while the server stores only a one-way transformation of it.
Jarecki et al. recently suggested an extra “pre-computation resistance” requirement, such that:
- An attacker must perform an offline dictionary attack that cannot make use of any pre-computed table.
Note that these requirements increase the burden on attackers, but do not stop attacks; once a server is compromised, an offline dictionary attack should be expected (one response is to update all passwords).
TAXONOMY: PAKE DESIGN CLASSES
The main PAKE designs have used passwords in three ways:
- as an encryption key
- as an input string to derive a generator
- as an integer in modular arithmetic (in the exponent for a multiplicative group, or as a scalar in an additive group over an elliptic curve).
The third case includes protocols having different security properties depending on the design approach and formal analysis model (e.g., common reference string, random oracle).
a summary of major PAKE schemes
- Password used as encryption key. This class includes using a password as the encryption key and typically must assume an ideal cipher.
- Password-derived generator. A protocol group generator is derived from a password.
- Trusted setup. The protocol relies on a trusted setup, which defines two (or more) generators whose discrete logarithm relationship must be unknown.
- Secure two-party computation. Here PAKE is viewed as a two-party secure computation problem on an equality function; the use of a non-interactive zero-knowledge proof (ZKP)aims to check that parties follow a specification honestly.
- Password-derived exponent. In this class, a password is used to derive
as a verifier in a type of Diffie-Hellmankey exchange.
PAKE security proofs are generally constructed in one or more of three security models
- Ideal cipher (IC)
- Common reference string (CRS)
- Random oracle (RO)