Rot256 : Cryptography & Other Random Bits.

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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!'
    exit
  end

  # 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)
end

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):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

from pwn import *
from hashlib import sha512, sha1

p = int('''
2853702329485239989809026491769982230023783615873322184937757867
5282616616142308243698229788844323124061946357688697147688990617
5870272573060319231258784649665194518832695848032181036303102119
3344326121727677106725603905962411362806784256240469884333105883
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('52.197.112.79', 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')
                break
            t = o
    else:
        # Gotta go fast
        if '\x00' in prefix:
            c.close()
            return get_conn()
        p = process(['./pow', prefix])
        t = p.recvall().strip().decode('hex')
        p.close()
    c.send(t.encode('base64'))
    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()
        conn1.sendline(bb2)
        conn2.sendline(bb1)

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
    conn1.sendline(str(g)) 
    conn2.sendline(str(g)) 
    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

            conn1.close()
            conn2.close()

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

        else:
            print 'Failed on index:', n
            exit(-1)
    passwords.close()

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