Password-authenticated key exchange (PAKE)

Deep dive

How it works

In: password pw, identities A and B, optional AAD · Out: session key Ke plus a confirmation tag per side · State: per run only the secret scalar (x or y) and w · Cost: about 4 scalar multiplications per side, 2 messages plus 2 tags.

SPAKE2 (RFC 9382 §3.3, §4):

1. Setup: prime-order group (order p, generator P, cofactor h) and two fixed elements M, N with unknown discrete logs; for other curves derive them by hash-to-curve (RFC 9380).
2. w = MHF(pw) mod p, taken from a hash 64 bits longer than p to remove bias. The MHF is a memory-hard hash (Argon2, scrypt).
3. A picks x and sends pA = w·M + x·P. B picks y and sends pB = w·N + y·P. Roles are fixed: A uses M, B uses N.
4. A computes K = h·x·(pB − w·N), B computes K = h·y·(pA − w·M). They agree only when their w agree.
5. TT = len-prefixed A, B, pA, pB, K, w. Ke ‖ Ka = Hash(TT).
6. KcA ‖ KcB = KDF(Ka, nil, "ConfirmationKeys" ‖ AAD); cA = MAC(KcA, TT), cB = MAC(KcB, TT) (HKDF, MAC).
7. A sends cA, B verifies and answers cB, A verifies; neither finishes before verifying. On mismatch abort and count the failure; otherwise Ke is the session key.

Why one guess per run. For any candidate w' some x' gives pA = w'·M + x'·P, so pA is uniform and reveals nothing. A guess can only be checked by taking part in a run and producing the right confirmation tag.

SPAKE2+ (RFC 9383). The prover derives w0 and w1; the verifier stores w0 and L = w1·P. A stolen verifier does not let the thief log in as the prover.

OPAQUE (RFC 9807). Registration: the client blinds the password through an OPRF, the server applies a per-client key derived from its oprf_seed, the client stretches the result (Argon2id, scrypt) and seals its AKE private key in an envelope the server stores; the server never sees the password. Login: the same OPRF round recovers the envelope, then a 3DH exchange with confirmation runs. Per-user OPRF keys mean a stolen database cannot be attacked with tables precomputed before the breach. Unknown users get a simulated response, so account names cannot be enumerated (§10.9).

Password to group element. Dragonfly (RFC 7664) hunts and pecks: hash (password, counter, addresses) until the value is a valid x-coordinate. The loop length depends on the password. Vanhoef and Ronen found timing and cache side-channels in this step in WPA3 and EAP-pwd implementations, enabling offline dictionary attacks; RFC 7664's minimum of k iterations only narrows the leak. The defence is an encoding with no password-dependent branch or memory access: constant-time hash-to-curve (constant-time code, side-channels). SPAKE2 sidesteps it: its mask is a scalar multiple of a fixed point.

Code

A toy SPAKE2: squares modulo a 62-bit safe prime, u128 mulmod, toy hash, fixed-seed xorshift. Compiled and run: same password gives equal keys and valid confirmations, a wrong password gives different keys and failed confirmations, pA differs per run. About 3.1 µs per complete run (both sides) on an Apple M4 Pro. M and N are hashed-then-squared values with discrete log assumed unknown (toy assumption).

// TOY SPAKE2 (RFC 9382 shape), subgroup of order q in Z_p*, p = 2q+1. Toy parameters, insecure;
// use RFC 9382 with P-256/Ed25519 groups via a vetted library.
const P: u128 = 4611686018427377339; // safe prime
const Q: u128 = 2305843009213688669; // (P-1)/2, prime: order of the subgroup of squares
const G: u128 = 4; // generator of that subgroup

fn mulm(a: u128, b: u128) -> u128 { a * b % P }
fn powm(mut b: u128, mut e: u128) -> u128 {
    let mut r = 1;
    while e > 0 { if e & 1 == 1 { r = mulm(r, b); } b = mulm(b, b); e >>= 1; }
    r
}
// Toy hash (FNV-1a + mixer): not collision resistant.
fn h(parts: &[&[u8]]) -> u64 {
    let mut s = 0xcbf29ce484222325u64;
    for p in parts {
        for b in (p.len() as u64).to_le_bytes().iter().chain(p.iter()) {
            s = (s ^ *b as u64).wrapping_mul(0x100000001b3);
        }
    }
    (s ^ (s >> 29)).wrapping_mul(0xbf58476d1ce4e5b9) ^ s >> 32
}
fn xorshift(s: &mut u64) -> u128 { // fixed seed: reproducible, not secure
    *s ^= *s << 13; *s ^= *s >> 7; *s ^= *s << 17;
    1 + *s as u128 % (Q - 1) // exponent in [1, q)
}
// hashed value squared; its dlog is assumed unknown (toy assumption)
fn element(label: &[u8]) -> u128 { let v = h(&[label]) as u128 % P; mulm(v, v) }

/// g^e * base^w, base = M (role A) or N (role B)
fn message(e: u128, base: u128, w: u128) -> u128 { mulm(powm(G, e), powm(base, w)) }

/// K = (peer * peer_base^-w)^e, peer_base^-w = peer_base^(q-w); then TT -> (Ke, cA, cB)
fn derive(peer: u128, peer_base: u128, e: u128, w: u128, pa: u128, pb: u128) -> (u64, u64, u64) {
    let k = powm(mulm(peer, powm(peer_base, Q - w)), e);
    let b = |x: u128| x.to_le_bytes();
    let tt = h(&[b"A", b"B", &b(pa), &b(pb), &b(k), &b(w)]).to_le_bytes();
    let ka = h(&[&tt, b"Ka"]).to_le_bytes();
    let mac = |who: &[u8]| h(&[&h(&[&ka, who]).to_le_bytes(), &tt]); // MAC(Kc_who, TT)
    (h(&[&tt, b"Ke"]), mac(b"cA"), mac(b"cB"))
}

/// Returns (pA, keys equal, A accepts cB, B accepts cA).
fn run(pw_a: &[u8], pw_b: &[u8], rng: &mut u64) -> (u128, bool, bool, bool) {
    let (m, n) = (element(b"M"), element(b"N"));
    let (wa, wb) = (h(&[b"w", pw_a]) as u128 % Q, h(&[b"w", pw_b]) as u128 % Q);
    let (x, y) = (xorshift(rng), xorshift(rng));
    let (pa, pb) = (message(x, m, wa), message(y, n, wb));
    let va = derive(pb, n, x, wa, pa, pb);
    let vb = derive(pa, m, y, wb, pa, pb);
    (pa, va.0 == vb.0, va.2 == vb.2, va.1 == vb.1)
}

fn main() {
    assert_eq!(2 * Q + 1, P);
    assert!(powm(G, Q) == 1 && powm(element(b"M"), Q) == 1);
    let mut rng = 0x9e3779b97f4a7c15u64;
    let (p1, same, a_ok, b_ok) = run(b"correct horse", b"correct horse", &mut rng);
    assert!(same && a_ok && b_ok);
    let (p2, same2, _, _) = run(b"correct horse", b"correct horse", &mut rng);
    assert!(same2 && p1 != p2); // fresh randomness: pA differs per run
    let (_, same3, a_bad, b_bad) = run(b"correct horse", b"wrong horse", &mut rng);
    assert!(!same3 && !a_bad && !b_bad); // wrong password: keys differ, confirmations fail
    let t = std::time::Instant::now();
    for _ in 0..20000 { run(b"pw", b"pw", &mut rng); }
    println!("ok; {:.1} us per run (both sides)", t.elapsed().as_secs_f64() * 1e6 / 20000.0);
}

Complexity and constants

SPAKE2 per side: x·P, w·M, w·N and one multiplication of the peer's unblinded point, so 4 scalar multiplications; w·M and w·N can be cached per password. Traffic: two group elements (33 B compressed, 65 B uncompressed on P-256) and two MAC tags. The toy's 3.1 µs is a 62-bit group, not P-256: the ECDH page measured about 100 µs per P-256 multiplication on the same chip. The memory-hard hash usually dominates: RFC 9807's recommended Argon2id uses m = 2^21 KiB (2 GiB), t = 1, p = 4, run on the client. OPAQUE login is three messages (KE1, KE2, KE3).

Efficiency

• Cost: order of 0.4 ms of P-256 group work per side per run (derived: 4 × the 100 µs measured for RustCrypto p256 on the ECDH page); compute-bound, plus the deliberate cost of the password hash. Network: 2 elements, 2 tags.
• Levers:
  • cache w·M and w·N — 2 of 4 scalar multiplications saved (RFC 9382 formulas) — repeated runs with one stored password.
  • hash the password once per login — one memory-hard hash instead of several — retries and re-keying.
  • reject locked-out accounts before any group work — no multiplication for bogus attempts (design choice) — public endpoints.
  • fixed-base tables for x·P — cheaper than variable-base (elliptic curve arithmetic) — when the library has them.
  • tune the KSF to the weakest client — client cost versus protection after a server breach (RFC 9807 §10.8) — mobile and embedded.
• Naive → standard → state of the art:
  • send H(password) or a challenge-response · a recorded exchange is guessed offline at hash speed
  • balanced PAKE (SPAKE2, SAE) · 4 scalar multiplications per side, one online guess per run
  • augmented PAKE (OPAQUE, SPAKE2+) · same plus OPRF or verifier; no password equivalent on the server

Implementation notes

• Encode w to fixed length (RFC 9382 pads it to the length of p); keep every password-dependent step branch-free.
• Check received elements for group membership; multiply by h (RFC 9382, RFC 9383).
• Put both identities, both messages, K and w into TT; an empty identity risks unknown key-share (RFC 9382). Put the version list in AAD against downgrade.
• Never use K directly (RFC 9382). Draw x and y from a CSPRNG; a repeated x breaks the one-guess bound.
• Count failures per account and source with backoff, including failed confirmations.

Pitfalls

• Password-dependent hunting and pecking leaks the password through timing or cache (Dragonblood).
• Skipping key confirmation: a wrong password goes unnoticed until the first record fails, and nothing counts the attempt.
• M or N with a known discrete log lets its holder strip the mask; derive them from a seed.
• A fast hash for w: after a leak of a verifier or OPAQUE record, guessing runs at hash speed.
• Unlimited retries: the guarantee is one guess per run, not per hour.
• The cited RFCs use discrete-log groups; none is post-quantum.

Variants and alternatives

In production

• WPA3-Personal: SAE, implemented in hostap src/common/sae.c; enterprise EAP-pwd also runs Dragonfly.
• Matter commissioning: SPAKE2+ with a PBKDF2 verifier from the setup passcode (connectedhomeip kSpake2p_* constants).
• magic-wormhole: depends on the spake2 Python package.
• Kerberos: RFC 9382 notes existing SPAKE2 variants.

Implementations

Sources

• Bellovin, Merritt, Encrypted key exchange: password-based protocols secure against dictionary attacks, IEEE S&P 1992. doi
• Jarecki, Krawczyk, Xu, OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-computation Attacks, EUROCRYPT 2018. doi
• Vanhoef, Ronen, Dragonblood: Analyzing the Dragonfly Handshake of WPA3 and EAP-pwd, IEEE S&P 2020. doi · eprint
• Ladd, SPAKE2, a Password-Authenticated Key Exchange, RFC 9382, 2023. rfc
• Taubert, Wood, SPAKE2+, an Augmented PAKE Protocol, RFC 9383, 2023. rfc
• Bourdrez, Krawczyk, Lewi, Wood, The OPAQUE Augmented PAKE Protocol, RFC 9807, 2025. rfc
• Harkins (ed.), Dragonfly Key Exchange, RFC 7664, 2015. rfc
• Faz-Hernandez et al., Hashing to Elliptic Curves, RFC 9380, 2023. rfc