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&timestamp=%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 sha256sign('&price=1') from the picture above, we can use a tool called HashPump.

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}.