Password-Authenticated Key Exchange

Ordinary password authentication sends the password — over TLS, to a server that hashes and compares it. That works, and it concentrates risk: the server sees every password in plaintext at login, a compromised or malicious server harvests them, and TLS interception or a mis-issued certificate exposes them in transit. PAKE protocols remove the transmission entirely: two parties who share only a low-entropy password derive a strong shared key, and an attacker — including one who records everything — cannot mount an offline dictionary attack.

The defining property #

A password has maybe 20–40 bits of entropy. Any protocol whose transcript lets an attacker test candidate passwords offline is broken by definition, because testing a few billion candidates is cheap.

EKE: the original idea #

Bellovin and Merritt (1992) introduced Encrypted Key Exchange. The move, as Schneier presents it in ch. 22.5, is to use the shared password $P$ as a symmetric key to encrypt a freshly generated, random public key:

sequenceDiagram
    participant A as Alice (knows P)
    participant B as Bob (knows P)
    A->>B: A, E_P(K')  — random public key, encrypted under the password
    B->>A: E_P(E_K'(K)) — random session key, double-encrypted
    A->>B: E_K(R_A)
    B->>A: E_K(R_A, R_B)
    A->>B: E_K(R_B)
    Note over A,B: both confirmed knowledge of K

Why this defeats offline guessing: an eavesdropper who guesses $P$ and decrypts step 1 obtains a candidate public key — but a random public key is indistinguishable from random bytes, so there is nothing to check the guess against. Contrast a protocol that encrypts a known-format value under the password: the attacker decrypts with each candidate and checks whether the plaintext is well-formed, which is a verifier and hence an offline attack.

The final four steps are mutual confirmation: steps 3–5 prove to Alice that Bob knows $K$, steps 4–6 prove the converse.

Balanced vs augmented #

EKE is balanced: both sides store the same password-derived value. That means a server database breach hands the attacker everything needed to impersonate users directly.

Augmented (asymmetric) PAKE fixes this: the server stores a verifier from which the password cannot be recovered cheaply, and which cannot be used directly to authenticate.

Where PAKE actually fits #

The honest scope: PAKE is not a replacement for how most web applications authenticate today, and pretending otherwise is why it stayed niche for thirty years.

• WiFi (WPA3/SAE) — the strongest real deployment. It fixed WPA2's offline attack, where capturing a handshake let an attacker grind the passphrase offline forever.
• Device pairing and IoT provisioning — a short PIN bootstraps a strong channel, with no PKI.
• End-to-end encrypted services — where the server must not learn the password because the password also derives the client's data-encryption key.
• Password managers and sync — SRP's main habitat.

Note also that browsers have no native PAKE, so a web deployment means running it in JavaScript delivered by the server you are trying not to trust — which undercuts the threat model. Passkeys (WebAuthn) solve the same problem from a different direction, with platform support, and are the more practical answer for the web.

Source claims audit #

The EKE material was seeded from Applied Cryptography ch. 22.5.