PAKE @ Hitcon 2016
Writeup of a challenge completed some time ago. Modified challenge code here
The challenge
The protocol is essentially SPEKE, but rather than use one large password, a number of smaller passwords are used and combined to avoid online bruteforce.
Talking to yourself
The first observation is that two sessions with the same server can convince each other that they know the passwords.
This may not appear very useful. But this allows us to bruteforce one small password (with 4-bits of entropy) at a time. We guess the next unknown password and let the two connections convince each other they know the remaining passwords. There are some minor details to take care of before we can do this, observe the core loop of the server:
|
|
If the password is equal for the two parties:
\[
\begin{equation} \label{eq1}
\begin{split}
w & = password^{2} \mod p
\\ b_1 & \leftarrow random()
\\ b_2 & \leftarrow random()
\\ bb_1 & = w^{b_1} \mod p
\\ bb_2 & = w^{b_2} \mod p
\\ aa_1 &= bb_2 \text{ : transmitted though the proxy}
\\ aa_2 &= bb_1 \text{ : transmitted though the proxy}
\\ k_1 &= aa_1^{b_1} = bb_2^{b_1} = w^{{b_2}^{b_1}} = w^{b_2 b_1} = aa_2^{b_2} = k_2 \mod p
\end{split} \\
\end{equation}
\]
You know how DH works… If we place ourself in the middle (for the password we are currently guessing) clearly \(k_1 \neq k_2\), yet: \(\text{key}_1 \oplus k_1 = \text{key}_2 \oplus k_2\) ; Since the remaining keys are the same. XORing a constant (the flag) into \(\text{key}_1\) and \(\text{key}_2\) obviously does not change this relation. This relation only holds if we guess \(w\) correctly, since otherwise the values \(k_1, k_2\) will not match those on the server (included in the \(\text{key}_1, \text{key}_2\)).
Finally
With this in mind, the exploit is surprisingly trivial (+/- some annoying PoW stuff):
|
|
After getting all the passwords we simply play by the rules to retrieve “key” and XOR the output with key to retrieve the flag (see nice.py). Full code on github