Isn't Socialist Millionaires vulnerable if Alice's and Bob's message are picked from a shared list?

Question

I'm interested in a situation where Alice and Bob each pick cards from a deck of 52, and want to test if they picked the same card without revealing what the card is (a "mental poker" situation). The protocol that came to mind was "Socialist Millionaires".

But if I'm correctly understanding the writeup of Socialist Millionaires that's currently on Wikipedia, and if that writeup is accurate, then I think that it's possible for Bob to learn Alice's secret message (and vice versa) if they are both picking their secret messages from a shared list, such as the card-drawing scenario.

The trick I thought of is that, after the protocol is finished, Bob has enough information that he can pick different values of his secret and test them. If they just picked from 52 cards, he just has to test 52 values of his secret message until he gets a "yes they are equal", and then he'll know what Alice has.

Using the notation from the wiki article, the answer to the question of whether $c = P_aP_b^{-1}$ is equivalent to the answer to the question of $x=y$, where $x$ is Alice's secret message and $y$ is Bob's.

The wiki article says

Note that :\begin{align} P_aP_b^{-1} &= \gamma^r \gamma^{-s} = \gamma^{r - s} \\ &= h^{\alpha\beta(r - s)} \end{align} and therefore :\begin{align} c &= \left(Q_aQ_b^{-1}\right)^{\alpha\beta} \\ &= \left(h^r g^x h^{-s} g^{-y}\right)^{\alpha\beta} = \left(h^{r - s} g^{x - y}\right)^{\alpha\beta} \\ &= \left(h^{r - s} h^{ab(x - y)}\right)^{\alpha\beta} = h^{\alpha\beta(r - s)} h^{\alpha\beta ab(x - y)} \\ &= \left(P_aP_b^{-1}\right) h^{\alpha\beta ab(x - y)} \end{align}.

Now, it seems to me that Bob knows $c$ from a Diffie-Hellman Key Exchange they did earlier.

$P_a$ and $P_b$ were transmitted in the clear, so Bob can calculate $\left(P_aP_b^{-1}\right)$.

He knows $h^{ab}$ and $h^{\alpha\beta}$ from two other DHKE's they did. So Bob can raise one to the power of the other and get $h^{ab\alpha\beta}$.

He knows $y$ because that's his secret message.

So if he wants to test against a new secret message ($y'$) offline, all he has to do is find:

\begin{align} c_1 &= c\left(P_aP_b^{-1}\right)^{-1} \\ &= h^{ab\alpha\beta(x-y)} \end{align}

Then find:

\begin{align} c_2 &= \left(c_1\right)^{y} \\ &= h^{ab\alpha\beta x} \end{align}

Now, Bob wants to test if Alice's card was a particular $y'$ that Bob has chosen. So he calculates:

\begin{align} c_3 &= c_2^{\left(y'\right)^{-1}} \\ &= h^{ab\alpha\beta(x-y')} \end{align}

Finally, he calculates:

\begin{align} c_4 &= c_3\left(P_aP_b^{-1}\right) \\ &= \left(P_aP_b^{-1}\right)h^{ab\alpha\beta(x-y')} \end{align}

And if $c_4 = P_aP_b^{-1}$, then this means that $x=y'$ and Bob has discovered what Alice's card is. None of these steps involved receiving new secret numbers from Alice or sending anything to Alice, so he can try for as many new $y'$ as he wants. Alice can't stop him, or even know that he's doing it.

Bob can try for all 52 cards, and he can discover which one was Alice's secret $x$.

Am I right about this? Is there something I'm missing?

Answer 1

The attack you are referring to is called an offline dictionary attack, which checks all possible values against a given transcript. However, the typical security notion for the socialist millionaires problem should forbid this attack. In fact, designing a protocol which is secure "except for offline dictionary attacks" is trivial: both players simply hash their input, with some public hash function, and exchange the outputs; if they are equal, then they own the same value; otherwise, they don't. Attacking essentially amounts to hashing all possible messages.

The protocol you describe is more complex, and it is in fact immune to such offline dictionary attacks; it's main purpose is essentially to avoid them. The error in your reasoning is the following sentence:

He knows $h^{ab}$ and $h^{\alpha\beta}$ from two other DHKE's they did. So Bob can raise one to the power of the other and get $h^{ab\alpha\beta}$.

This is not true: one can compute $h^{ab\alpha\beta}$ from $h^{ab}$ and $\alpha\beta$, or from $h^{\alpha\beta}$ and $ab$, but not from $h^{ab}$ and $h^{\alpha\beta}$. Computing $h^{ab\alpha\beta}$ from $h^{ab}$ and $h^{\alpha\beta}$ is equivalent to breaking the computational Diffie-Hellman assumption. In fact, under the decisional Diffie-Hellman assumption, $h^{ab\alpha\beta}$ is indistinguishable from random, even given both $h^{ab}$ and $h^{\alpha\beta}$. This is the observation that underlies the security argument for this protocol.