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:

passwords.each.with_index(1) do |password, i|
  puts "Round #{i}"

  # Perform a simple PAKE handshake
  # You can find explanation in http://goo.gl/3foagq  (In code comment :D)
  w = pow(password, 2, p)  # NO to Legendre
  b = 2 + SecureRandom.random_number(p - 2)
  bb = pow(w, b, p)
  aa = gets.to_i
  if aa < 514 || aa >= p - 514
    puts 'CHEATER!'

  # If I give it the password, then k == bb (if correct)
  k = pow(aa, b, p)
  key ^= Digest::SHA512.hexdigest(k.to_s).to_i(16)

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\)).


With this in mind, the exploit is surprisingly trivial (+/- some annoying PoW stuff):

from pwn import *
from hashlib import sha512, sha1

p = int('''
64872005613290545811367950034187020564546262381876467'''.replace('\n', ''))

q = p - 1

ps = []
for x in range(1, 17):
    ps.append(int(sha512(str(x)).hexdigest(), 16))
gs = map(lambda x: pow(x, 2, p), ps)
ax = {x: y for (x, y) in zip(range(1, 17), gs)}

DEBUG = False
SLOW = False

def get_conn():
    if DEBUG:
        c = process(['ruby', 'pake.rb'])
        return c
    c = remote('', 20431)
    # c = process(['ruby', 'pake.rb'])
    c.recvuntil('prefix: ')
    prefix = c.recvuntil('\n').decode('base64')
    if SLOW:
        t = ''
        print 'Solving PoW'
        while 1:
            o = sha1(prefix + t).digest()
            if o.startswith('\x00\x00') and ord(o[2]) // 2 == 0:
                print o.encode('hex')
            t = o
        # Gotta go fast
        if '\x00' in prefix:
            return get_conn()
        p = process(['./pow', prefix])
        t = p.recvall().strip().decode('hex')
    c.recvuntil('Good job!')
    return c

def proxy(conn1, conn2, rounds):
    for i in range(0, rounds):
        conn1.recvuntil('Server send')
        conn2.recvuntil('Server send')
        bb1 = conn1.recvuntil('\n').strip()
        bb2 = conn2.recvuntil('\n').strip()

def guess(conn1, conn2, pw):
    g = ax[pw]
    print 'Guessing:', pw, g

    # Proxy
    conn1.recvuntil('Server send')
    conn2.recvuntil('Server send')
    bb1 = conn1.recvuntil('\n').strip()
    bb2 = conn2.recvuntil('\n').strip()
    k1  = int(sha512(bb1).hexdigest(), 16)
    k2  = int(sha512(bb2).hexdigest(), 16)

    # Inject guess
    return k1, k2

def get_flag(conn):
    conn.recvuntil('Flag is (of course after encryption :D): ')
    return int(conn.recvuntil('\n'))

if __name__ == '__main__':
    passwords = open('out-passwords', 'w')
    N = 11
    for n in range(0, 11):
        for test in ax:
            print 'Round', n, ', trying:', hex(test)
            conn1 = get_conn()
            conn2 = get_conn()

            proxy(conn1, conn2, n)
            k1, k2 = guess(conn1, conn2, test)
            proxy(conn1, conn2, N - n - 1)

            flag1 = get_flag(conn1)
            flag2 = get_flag(conn2)

            diff1 = flag1 ^ k1
            diff2 = flag2 ^ k2


            if diff1 == diff2:
                print 'Password:', n, '=', hex(test)
                passwords.write(str(test) + '\n')
            print 'Wrong guess'

            print 'Failed on index:', n

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