Augmented PAKE and What a Stolen Verifier Costs an Attacker

A password system stores a function of the password and hopes the function is slow. A password-authenticated key exchange stores something different: a value from which the password cannot be checked without performing an interactive protocol with the server, and from which a precomputed table cannot be built for other servers. The construction is worth understanding because it inverts the assumption behind password hashing, and because the inversion is narrower than its advocates sometimes claim.

Two kinds of PAKE, and why the distinction matters

A balanced PAKE assumes both parties hold the same secret. The password is the shared key, both sides prove knowledge of it, and the protocol derives a session key from it. SPAKE2, specified in RFC 9382, and J-PAKE, specified in RFC 8236, are balanced: neither party stores anything derived from the password that the other does not.

An augmented PAKE assumes the server stores a value derived from the password, and the client holds the password itself. SRP, from RFC 2945, is the canonical example. The distinction is not cosmetic. A balanced PAKE requires the server to hold the password or an equivalent, which means a breach hands the attacker the same secret the user types. An augmented PAKE lets the server hold a verifier that is not the password and cannot be replayed as one.

There is a third property that separates the good designs from the mediocre ones: resistance to precomputation. An attacker who steals a table of verifiers would like to precompute, once, a mapping from candidate passwords to verifier values, and then test every stolen row against that table. If the verifier computation depends only on the password, that works. If it depends on a per-server secret or a per-user salt that the attacker does not have, the table is useless. OPAQUE, published by Jarecki, Krawczyk, and Xu at EUROCRYPT 2018, is built around an oblivious pseudorandom function whose key is held by the server, so the verifier for a given password differs per server and cannot be computed offline without that key.

SRP, step by step

SRP is the clearest illustration of the arithmetic. All operations are in a multiplicative group modulo a large prime $N$, with a generator $g$. The group and hash are fixed parameters, published in RFC 5054 for TLS use.

Enrolment is where the verifier is created. The server issues a random salt $s$ and the client computes

$$x = H(s ,|, H(I ,|, \text{’:’} ,|, P)), \qquad v = g^x \bmod N$$

where $I$ is the username and $P$ the password. The server stores $s$ and $v$. It never sees $P$ or $x$.

Authentication is a Diffie-Hellman exchange with the verifier substituted for one of the exponents. The client picks a random $a$ and sends $A = g^a$. The server picks a random $b$, computes $B = kv + g^b$ where $k$ is a hash-derived multiplier, and sends $B$ along with $s$. Both sides then compute a scrambling parameter $u = H(A ,|, B)$, and the shared secret is

$$S = (B - kv)^{a + ux} = (A \cdot v^u)^b$$

The client can compute the left form because it knows $x$; the server can compute the right form because it knows $v = g^x$ and $b$. Neither has both. From $S$ both derive a key $K = H(S)$, and each proves knowledge of it with a hash over the transcript. The server’s proof is what authenticates the server to the client, and it is why SRP is mutually authenticating.

The property that matters for a breach is the shape of $v$. It is $g^x$ for a secret exponent derived from the password. To test a candidate password $P’$ against a stolen row, an attacker computes $x’$ from the salt and username, then $g^{x’}$, and compares. That is one modular exponentiation per guess, not one hash per guess.

The exponentiation is the entire defence, and it is worth being precise about its size. Testing a candidate password means computing $g^{x’}$ with a full-length exponent, which by square-and-multiply is on the order of a thousand modular squarings and half as many multiplications modulo a 2048-bit prime. That is a fixed arithmetic cost per guess and it involves no significant memory, so an attacker’s throughput is set by how many multipliers can be bought. The ratio to a memory-hard KDF is not obviously favourable: Argon2id with a 64 MiB working set is designed to be hostile to exactly that kind of parallel hardware, and SRP’s verifier check has no memory cost at all.

What SRP does provide is the elimination of precomputation across accounts. Each row has its own salt, so the attacker must derive $x’$ per row, which is a cheap hash, and then exponentiate per row. There is no table that amortises across a million stolen records the way a rainbow table amortises a bare hash. That is a real gain and it is the gain that the phrase “no password-equivalent stored” is reaching for.

What the client-side protocol actually buys

The second gain is that the password never crosses the wire, not even inside TLS. In a conventional login the server receives the plaintext password and can log it, retain it in memory, or mishandle it. In SRP the server receives $A$ and $B$, neither of which is a function of the password in a usable form, and the password exists only on the client and inside the exponent $x$.

This is a genuine reduction in the trusted computing base: the server cannot leak what it never had. It is also the reason SRP was proposed for TLS as a set of cipher suites in RFC 5054, where the password exchange is part of the handshake and the resulting TLS channel is authenticated by it.

The cost is that the client must run the protocol. That means code on the client that implements group arithmetic correctly, with constant-time exponentiation and valid group element checks. A client that accepts a malformed $B$ or fails to validate that $A$ and $B$ are in the group can be attacked in ways the protocol’s proofs do not cover. In a browser, that code is JavaScript delivered by the server, which means the server can serve a modified client that sends the password in the clear. The reduction in trust is therefore real only when the client code is trusted independently, which in a web context it is not. Native applications and hardware tokens are where the property holds in the strong sense.

OPAQUE and the precomputation gap

OPAQUE closes the remaining gap by making the verifier depend on a server-held key. The client’s password is the input to an oblivious pseudorandom function, evaluated jointly: the client blinds the password, the server applies its key to the blinded value, and the client unblinds the result. The server learns nothing about the password from the evaluation, and the client obtains an output that is a pseudorandom function of the password under a key only the server holds.

From that output the client derives two things: a private key for the account, and a registration record that the server stores. The stored record is an envelope encrypted under a key derived from the same output. On login, the client re-runs the OPRF, decrypts the envelope, and proves possession of the private key.

The consequence for a breach is sharper than SRP’s. Without the OPRF key, an attacker holding the envelopes cannot test candidate passwords at all, because the input to the key derivation is a pseudorandom value they cannot compute. The attack becomes: obtain the OPRF key, then run the protocol per guess. That is a meaningful elevation of the key’s importance, and it means the key must live in a component that is not breached along with the database, ideally an HSM or a separate service. OPAQUE also gives the client a long-term private key that can be used for signatures, which is the same shape as a WebAuthn credential but derived from a password rather than held in hardware.

The operational costs that decide deployment

PAKE protocols are not free at the protocol level. Each authentication involves several group exponentiations per side, which is more computation than a hash-based login and more round trips than a single POST. SRP over a 2048-bit group needs a handful of exponentiations, and OPAQUE’s OPRF adds another. The latency is small in absolute terms but it is on the login path and it is not compressible the way a single hash is.

The failure modes are also less forgiving than a hash comparison. A group element that is not in the subgroup of order $q$ can leak the discrete logarithm of the shared secret, which is why the parameters include a safe prime and why implementations must validate incoming values. A client that sends a zero or a small-order element, whether by bug or by attack, breaks the protocol in ways that a hash comparison cannot. The RFC 5054 parameters exist for this reason and should not be replaced with arbitrary primes.

Interoperability is the practical blocker. There is no browser API for PAKE, so a web deployment ships the protocol as JavaScript, which as noted gives back the trust it was meant to gain. Server-side support is uneven across libraries, and the parameter negotiation is a source of incompatibility. This is why hash-based storage remains the default even where a PAKE would be strictly better on paper: the deployment cost is a client, not a library call.

The comparison that matters is therefore not “PAKE versus bcrypt” but “PAKE versus bcrypt plus a rate limiter plus breach-corpus checking”. A PAKE removes the offline attack’s precomputation advantage and removes the password from the server’s memory, and it does nothing about a password that is in a corpus, nothing about an attacker who phishes the login in real time, and nothing about the recovery path. Those are the same residual exposures that online guessing limits and factor independence address, and no storage construction substitutes for them.

Where the verifier model fits

The honest summary is that an augmented PAKE changes what a breach yields rather than whether a breach matters. A stolen SRP verifier requires one exponentiation per guess per row; a stolen OPAQUE envelope requires the server’s OPRF key before any guess is possible. Both are strictly better than a bare hash and neither is better than a memory-hard hash with a large working set against an attacker with dedicated hardware, because the PAKE’s cost per guess is arithmetic while the memory-hard function’s cost is bandwidth and capacity.

The design that combines them is the one that keeps both properties: a PAKE for the online protocol, so the password never reaches the server, and a memory-hard derivation inside the client’s half of the computation, so the offline cost against a stolen verifier is high. That combination is not standardised as a single protocol, which is the reason it is not widely deployed, and it is the shape that the pieces in password hashing and the protocols here would take if the interoperability cost were solved.