From Zero To X

zTrix's Blog

PlaidCTF 2014 - Parlor (Crypto 250) Writeup

by Wenlei Zhu (zTrix@blue-lotus)

Problem description

Crypto (250 pts)

The Plague is running a betting service to build up funds for his massive empire. Can you 
figure out a way to beat the house? The service is running at 54.197.195.247:4321.

use nc to connect the service, we got the following screen

/------------------------------------------------------------------------------\
| Welcome to the betting parlor!                                               |
|                                                                              |
| We implement State of the Art cryptography to give you the fairest and most  |
| exciting betting experience!                                                 |
|                                                                              |
| Here's how it works: we both pick a nonce, you tell us odds, and you give us |
| some money.                                                                  |
| If md5(our number + your number) % odds == 0, you win bet amount*odds.       |
| UPDATE: IF YOU DIDN'T REALIZE IT, WE DO INCLUDE A NEWLINE AT THE END OF YOUR |
| NUMBER. SORRY FOR THE INCONVENIENCE. THANK YOU FOR USING PARLOR              |
| Otherwise, we get your money! We're even so nice, we gave you $1000 to start.|
|                                                                              |
| If you don't trust us, we will generate a new nonce, and reveal the old nonce|
| to you, so you can verify all of our results!                                |
|                                                                              |
| (Oh, and if you win a billion dollars, we'll give you a flag.)               |
\______________________________________________________________________________/

====================
  1) set your odds
  2) set your bet
  3) play a round
  4) get balance
  5) reveal nonce
  6) quit
====================

So, it’s a small betting game, if we can win enough money, we’ll get a flag.

Studying the rules, we can see that, the smaller the odds, the more likely we can win. If we set odds to 1^2, the chance to win will be a half. But we cannot bet the same nonce after winning.

So if we can figure out a way to always win, then we can double our balance each time, reaching a billion won’t be a problem any more.

Since the md5 is calculated on server_nonce + player_nonce, and server_nonce won’t change until you reveal it, and player_nonce is under our control, so we can easily think of the Hash length extension attack.

However, to use Hash length extension attack, we need the result of md5(server_nonce + player_nonce). If we set odds to 1^100, then we can get 100 bits of the md5 digest, how about the remaining 28 bits?

Since 2^28 is not a huge number, we can use brute-force. Here is the attack plan:

  1. Set our bet to 1$, odds to 2^100, play a round, send ‘a\n’
  2. It’s mostly likely we will lose, never mind, grab the generated value, which should be sth like 0000000171ccbeef0869667267a6bbdd in hex format.
  3. Construct hash length attack padding suffix, play another round, send ‘a\n’ + suffix + ‘b\n’, which would be sth like a\n\x80\x00\x00......\x00\x90\x00\x00\x00\x00\x00\x00\x00b\n
  4. And, not surprised, we lose again, never mind, grab the second generated value, which should be sth like 0000000f48eabc92e4b180a8d1b7c3d3 in hex format.

OK, now we know

  1. md5(server_nonce + 'a\n') == XXXXXX171ccbeef0869667267a6bbdd
  2. md5(server_nonce + 'a\n\x80\x00......\x00\x90\x00\x00\x00\x00\x00\x00\x00b\n' == YYYYYYf48eabc92e4b180a8d1b7c3d3
  3. if we know the value of XXXXXXX, we can calculate YYYYYYf48eabc92e4b180a8d1b7c3d3 by hash length extention attack

So just brute-force the value of XXXXXXX, and calculate the second md5 value, until we get the same suffix (f48eabc92e4b180a8d1b7c3d3).

After that, use hash extension attack again to search md5 hashes ending with bit 0, which is very easy. Send those winning nonce and get the flag!

(parlor.py) download
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
#!/usr/bin/env python2
#-*- coding:utf-8 -*-

import os, sys
import subprocess

# https://github.com/zTrix/zio
from zio import *

def md5_ext(s, a):
    tl = len(s) * 8
    ret = s + '\x80'
    while len(ret) % 64 != 56:
        ret += '\x00'
    ret += l32(tl)
    ret += l32(0)
    return ret + a

host = '54.197.195.247'
port = 4321

io = zio((host, port), print_write = COLORED(REPR))

io.read_until('6) quit')
io.writeline('1')
io.read_until('and 100):')
io.writeline('100')

io.read_until('6) quit')
io.writeline('3')
io.read_until('nonce for this round')
io.write('a\n')
io.read_until('we generated ')
remain1 = int(io.read_until(',')[:-1])
remain1_str = '0' * 7 + hex(remain1)[2:].rstrip('L')
print remain1, remain1_str

ext = md5_ext('k' * 16 + 'a\n', 'b\n')
io.read_until('6) quit')
io.writeline('3')
io.read_until('nonce for this round')
io.write(ext[16:])
io.read_until('we generated ')
remain2 = int(io.read_until(',')[:-1])
remain2_str = '0' * 7 + hex(remain2)[2:].rstrip('L')
print remain2, remain2_str

if False:
    io.read_until('6) quit')
    io.writeline('5')
    io.read_until('the nonce has been ')
    nonce = int(io.readline().strip(), 16)
    print hex(nonce)[2:].rstrip('L')

log(' '.join(['./search', remain1_str, remain2_str]), 'red')
prefix = subprocess.check_output(['./search', remain1_str, remain2_str])
assert len(prefix.strip()) == 7

first_md5 = prefix.strip() + remain1_str[7:]

io.read_until('6) quit')
io.writeline('1')
io.read_until('between 1 and 100):')
io.writeline('1')

log(' '.join(['./even', first_md5]), 'red')
candi = subprocess.check_output(['./even', first_md5])
for line in candi.strip().splitlines():
    ary = line.split(', ')
    c = chr(int(ary[0]))
    if c == 'b': continue
    ext = md5_ext('k' * 16 + 'a\n', c + '\n')
    log('hash expectation: %s' % ary[1], 'red')

    io.read_until('6) quit')
    io.writeline('2')
    io.read_until(' and ')
    balance = io.read_until('):')[:-2]
    io.writeline(balance)

    io.read_until('6) quit')
    io.writeline('3')
    io.read_until('nonce for this round')
    io.write(ext[16:])

    rs = io.read_until('====')
    if 'Too bad' in rs:
        break
    elif 'key' in rs:
        break

io.close()

Here is the command line output recorded by asciinema commandline output record

Download source code here

Comments