The RCTF 2018 (ctftime.org) ran from 19/05/2018, 09:00 UTC to 21/05/2018 08:59 UTC.

I wrote the following writeup for the crypto challenge *cpushop*.

# cpushop (176 pts)

### Challenge description

The challenge provided a python-script (`cpushop.py`

) and a hostname/port of the server running the script (`cpushop.2018.teamrois.cn 43000`

).

Let’s examine the script:

root@kali:~/Documents/roisctf/cpushop# cat cpushop.py #!/usr/bin/env python # encoding: utf-8 import random import string import signal import sys import os import time from hashlib import sha256 from urlparse import parse_qsl os.chdir(os.path.dirname(os.path.abspath(__file__))) signkey = ''.join([random.choice(string.letters+string.digits) for _ in xrange(random.randint(8,32))]) items = [('Intel Core i9-7900X', 999), ('Intel Core i7-7820X', 599), ('Intel Core i7-7700K', 349), ('Intel Core i5-7600K', 249), ('Intel Core i3-7350K', 179), ('AMD Ryzen Threadripper 1950X', 999), ('AMD Ryzen 7 1800X', 499), ('AMD Ryzen 5 1600X', 249), ('AMD Ryzen 3 1300X', 149), ('Flag', 99999)] money = random.randint(1000, 10000) def list_items(): for i,item in enumerate(items): print '%2d - %-30s$%d' % (i, item[0], item[1]) def order(): n = input_int('Product ID: ') if n < 0 or n >= len(items): print 'Invalid ID!' return payment = 'product=%s&price=%d×tamp=%d' % (items[n][0], items[n][1], time.time()*1000000) sign = sha256(signkey+payment).hexdigest() payment += '&sign=%s' % sign print 'Your order:\n%s\n' % payment def pay(): global money print 'Your order:' sys.stdout.flush() payment = raw_input().strip() sp = payment.rfind('&sign=') if sp == -1: print 'Invalid Order!' return sign = payment[sp+6:] try: sign = sign.decode('hex') except TypeError: print 'Invalid Order!' return payment = payment[:sp] signchk = sha256(signkey+payment).digest() if signchk != sign: print 'Invalid Order!' return for k,v in parse_qsl(payment): if k == 'product': product = v elif k == 'price': try: price = int(v) except ValueError: print 'Invalid Order!' return if money < price: print 'Go away you poor bastard!' return money -= price print 'Your current money: $%d' % money print 'You have bought %s' % product if product == 'Flag': print 'Good job! Here is your flag: %s' % open('flag').read().strip() def input_int(prompt): sys.stdout.write(prompt) sys.stdout.flush() try: n = int(raw_input()) return n except: return 0 def menu(): print "CPU Shop" while True: print "Money: $%d" % money print "1. List Items" print "2. Order" print "3. Pay" print "4. Exit" sys.stdout.flush() choice = input_int("Command: ") { 1: list_items, 2: order, 3: pay, 4: exit, }.get(choice, lambda *args:1)() sys.stdout.flush() if __name__ == "__main__": signal.alarm(60) menu()

### What does the script do?

–> On line 14 a `signkey`

is defined, which may consist of 8 to 32 letters (upper- and lowercase) and digits. The length (8-32) as well as the letters/digits are random.

–> When selecting `"2. Order"`

in the menu being displayed, the user can choose one of the products from the `items`

array defined on line 15.

–> The last element of the `items`

array is the `Flag`

which costs `99.999$`

.

–> Since our available money is a random value between `1.000$`

and `10.000$`

(line 16), we obviously cannot afford the `Flag`

.

–> After having selected a product to order the `order`

function is called (line 22) printing the four attributes, which identifiy an order:

– product (the name of the product, e.g. `Flag`

)

– price (the price of the product, e.g. `99999`

)

– timestamp (the current timestamp: `time.time()*1000000`

)

– **sign** (the sha256-hash of the order prepended by the `signkey`

: `sign = sha256(signkey+payment).hexdigest()`

)

–> When choosing `"3. Pay"`

, the function `pay`

is called (line 32). Within the function …

– … an order (formerly printed by the `order`

function) is read (line 36).

– … the `sign`

attribute is extracted (line 41).

– … the sign-value (`signchk`

) for the order being read is calculated using the secret `signkey`

(line 49).

– … the extracted `sign`

is compared to `signchk`

(line 50). If the comparison fails, the order is invalid and the function is quit.

– … the values of the attributes `product`

and `price`

are extracted (line 56 and 59).

– … the extracted `price`

is compared to the available `money`

(line 64). If the money does not suffice, the function is quit (`"Go away you poor bastard!"`

).

– … if the order is valid, the available money suffices and the selected product is `Flag`

, the contents of the file `flag`

are printed: `open('flag').read().strip()`

(line 72).

### How can we afford the `Flag`

?

If we would know the random `signkey`

, we could sign an order of the product `Flag`

with a `price`

we can afford.

Since the `signkey`

has a minimum length of 8 and consists of letters and digits, the minimal key-space is `62**8 = 218.340.105.584.896`

. So bruteforcing does not seem to be an option.

Instead we can use a technique called length extension attack.

The *length extension attack* is based on the fact that a hash-function like sha256 processes data block-by-block. Each processed block results in an internal state of the hash-function, which is the base for the calculation of the next block. After the last block is processed, the internal state is returned in the form of the hash-value. Since we know the hash-value (`sign`

), we can restore the internal state and continue the calculation of the hash-value for additional data, which we would like to append to the order.

For the attack to work for a hash `H(secret || message)`

we need to know `message`

and the length of `secret`

. In our case `message`

is the order (`payment`

), which we know. `secret`

is the `signkey`

, which lengths we do not exactly know, but it must be between 8 and 32.

If we append `&price=1`

to the order and calculate the valid `sign`

value, we can buy the product `Flag`

for `1$`

, since the original value of `price`

(`99999`

) is overwritten with the new value we append (`1`

):

for k,v in parse_qsl(payment): if k == 'product': product = v elif k == 'price': try: price = int(v) ...

The following picture illustrates the attack:

### Implementation

In order to carry out the length extension attack, which means to calculate the value for `sha256`

from the picture above, we can use a tool called HashPump._{sign}('

*HashPump* is available as a python-module:

root@kali:~# pip install hashpumpy ...

The following script …

–> … orders the `Flag`

.

–> … extracts the value for `sign`

and `payment`

from the order.

–> … loops over the possible key length from 8 to 32.

–> … uses `hashpumpy`

to append `'&price=1'`

to the order and calculate the new value for `sign`

without knowing the secret `signkey`

.

–> … tries to submit the payment of `1$`

to buy the `Flag`

.

root@kali:~/Documents/roisctf/cpushop# cat buyFlag.py #!/usr/bin/env python from pwn import * import hashpumpy p = remote('cpushop.2018.teamrois.cn', 43000) p.recv() # order Flag p.sendline("2") p.recvuntil("Product ID: ") p.sendline("9") # extract sign and payment from order payment = p.recv() sp = payment.find('&sign=') sign = payment[sp+6:] sign = sign[:sign.find('\n')] payment = payment[payment.find('product'):payment.find('&sign')] for keylen in range(8,32): log.info('trying keylen='+str(keylen)) n = hashpumpy.hashpump(sign, payment, '&price=1', keylen) order = n[1] + "&sign="+n[0] p.sendline("3") p.recvuntil("Your order:") p.sendline(order) p.recv(1000) ret = p.recv(1000) if ("Invalid" not in ret): print(ret) print(p.recvuntil("Money: ")) quit()

Running the script yields the flag:

root@kali:~/Documents/roisctf/cpushop# ./buyFlag.py [+] Opening connection to cpushop.2018.teamrois.cn on port 43000: Done [*] trying keylen=8 [*] trying keylen=9 [*] trying keylen=10 [*] trying keylen=11 [*] trying keylen=12 [*] trying keylen=13 [*] trying keylen=14 [*] trying keylen=15 [*] trying keylen=16 [*] trying keylen=17 [*] trying keylen=18 [*] trying keylen=19 [*] trying keylen=20 [*] trying keylen=21 [*] trying keylen=22 [*] trying keylen=23 [*] trying keylen=24 [*] trying keylen=25 [*] trying keylen=26 [*] trying keylen=27 [*] trying keylen=28 [*] trying keylen=29 [*] trying keylen=30 Your current money: $4908 You have bought Flag Good job! Here is your flag: RCTF{ha5h_l3ngth_ex7ens10n_a77ack_1s_ez} Money: [*] Closed connection to cpushop.2018.teamrois.cn port 43000

The flag is `RCTF{ha5h_l3ngth_ex7ens10n_a77ack_1s_ez}`

.

Super write-up dude!

Thanks ðŸ™‚