# 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