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 == 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