Simply using password as a third "private key" for PAKE

Question

I'm reading through the development of PAKE protocols, starting with EKE and SPEKE, their potential pitfalls, and what motivates their protocol choices. And I've been wondering, what is wrong with the following (very simple) modification to classic DH to make that PAKE:

Let Alice and Bob have a shared secret s = hash(password). Alice and Bob pick private keys a, b. Starting with DH, Alice and Bob compute their public keys as

$A = g^{as}\mod p$

$B = g^{bs}\mod p$

After they exchange public keys, they can calculate their shared key as $K = g^{abs}\mod p$

What is wrong with this simple scheme? I'm guessing it somehow allows an offline dictionary attack on s. I know s has no low entropy, but I'm still not seeing how.

Answer 1

Here's the problem with this scheme: suppose $A$ is the honest client, and $B$ is a dishonest server (who doesn't know $s$). Then, $A$ tries to log in, he selects $a$ and transmits

$$A = g^{as} \bmod p$$

Then, $B$ just picks a random value $b$, and transmits

$$B = g^b \bmod p$$

Then, $A$ will compute a 'shared secret' $$S = B^a \bmod p$$ (which would be $g^{abs} \bmod p$ had $B$ executed the protocol honestly, instead, we have $S = g^{ab} \bmod p$). Then, $A$ sends a message $M_S$ keyed by that shared secret (whether it be a key confirmation message or an initial encrypted data exchange, it doesn't really matter).

$B$ has no further interactions with $A$.

Then, here is what $B$ can do; he can pick an entry in his dictionary $password'$ and compute $s' = hash(password')$. He can then compute $S' = A^{s'^{-1}b} \bmod p$; if he happened to pick the correct password, then $s = s'$, and so $S' = A^{s^{-1}b} = g^{as \cdot s^{-1}b} = g^{ab} = S$, and so he can use that shared secret to verify the message.

If he didn't happen to pick the correct password, he can go back and select another entry in his dictionary, and repeat the off-line computation until he finds the right entry.

Bottom-line: with your protocol, an active attacker can do a full dictionary search as the result of a single exchange.