# GynvaelEN mission 009

# cat mission_09.py
import datetime

# Microsoft rand
def rand():
 global seed
 seed = (seed * 214013 + 2531011) % 2147483648
 return seed / 65536


key = [0] * 31
secret = [0] * 31
xor = [0x9a, 0x60, 0x76, 0x14, 0x8b, 0x36, 0x5a, 0x10, 0x2b, 0x91, 0xc4, 0x6c, 0xab, 0x27, 0x92, 0x99, 0xf8, 0x6a, 0xec, 0x5d, 0x32, 0x20, 0x3d, 0x61, 0x8f, 0xc7, 0xfb, 0xdd, 0x02, 0x72, 0xbf]


for s in range(1500336000, 1500508800):
 seed = s
 for i in range(31):
  eax = rand()
  rdx = (2139127681 * eax) >> 39
  ecx = eax >> 31
  edx = (rdx & 0xffffffff) - ecx
  ecx = edx << 8
  edx += ecx
  eax -= edx
  key[i] = eax & 0xff

 for i in range(31):
  secret[i] = (xor[i] ^ key[i]) & 0xff

 if all(c < 128 for c in secret):
  print 'seed =', s
  print 'time = ', datetime.datetime.fromtimestamp(s)
  print ''.join([chr(c) for c in secret])
  break

# python mission_09.py
seed = 1500483661
time =  2017-07-19 18:01:01
Who needs to store keys anyway.

Source

https://www.youtube.com/watch?v=7RotbY17tKk (1:47:55)

Reference

https://en.wikipedia.org/wiki/COFF

# AlexCTF: CR5: Bring weakness - 300 pts

Get random numbers

# cat get.py 
from pwn import *

host = '195.154.53.62'
port = 7412

def give_me_the_next_number():
 r.sendlineafter('2: Give me the next number\n', '2')
 number = int(r.recvline())
 return number

r = remote(host, port)

for i in xrange(4):
 print give_me_the_next_number()

r.close()
# python get.py
855109115
895402096
2391280583
300480802

Linear congruential generator

random_n+1 = ((a * random_n) + c) % m
a = multiplier
c = increment
m = modulus

Get modulus

# cat get_modulus.py
from pwn import *

host = '195.154.53.62'
port = 7412

def give_me_the_next_number():
 r.sendlineafter('2: Give me the next number\n', '2')
 number = int(r.recvline())
 return number

def egcd(a, b):
 if a == 0:
  return (b, 0, 1)
 else:
  g, y, x = egcd(b % a, a)
 return (g, x - (b // a) * y, y)

results = []

for i in xrange(20):
 r = remote(host, port)
 last = give_me_the_next_number()
 current = give_me_the_next_number()
 tn = current - last
 last = current
 current = give_me_the_next_number()
 tn1 = current - last
 last = current
 current = give_me_the_next_number()
 tn2 = current - last
 u = abs(tn2*tn - tn1**2) # Important
 r.close()
 results.append(u)

print results

for i in xrange(0, 19):
 print egcd(results[i], results[i+1])[0]

# python get_modulus.py
[312571317250000395, 2949916660717308525, 640738713015133065, 435603004762385760, 2439656571633178950, 11411209872061185300L, 6407385815891338380, 610020832043386185, 1779427408702485555, 149150577634188375, 3371733426053132880, 402697709832197265, 2394242682672509175, 854013216788180865, 829159057095801915, 2030937970488420525, 9719562562552278360L, 4544082617950022895, 157160975107204845, 5385743285459484420L]
12884901885
12884901885
4294967295
8589934590
42949672950
17179869180
4294967295
4294967295
4294967295
4294967295
4294967295
4294967295
55834574835
4294967295
30064771065
4294967295
12884901885
244813135815
12884901885

Modulus = 4294967295 == 2**32 -1

Solve the equation with Wolfram Alfa and get (a, c)

r0 = 855109115
r1 = 895402096
r2 = 2391280583
r3 = 300480802
m = 4294967295
r1 = ((a*r0) + b) mod m
r2 = ((a*r1) + b) mod m
r3 = ((a*r2) + b) mod m

a = 6771334847
c = 6621298821

Get the flag

# cat get_flag.py
from pwn import *

host = '195.154.53.62'
port = 7412

def give_me_the_next_number():
 r.sendlineafter('2: Give me the next number\n', '2')
 number = int(r.recvline())
 return number

def guess_the_next_number(number):
 next = lcg(number)
 r.sendlineafter('2: Give me the next number\n', '1')
 r.sendlineafter('Next number (in decimal) is\n', str(next))
 return next

def lcg(seed):
 a = 6771334847
 c = 6621298821
 m = 4294967295
 return ((seed * a) + c) % m

r = remote(host, port)

seed = give_me_the_next_number()

for i in range(10):
 print seed
 seed = guess_the_next_number(seed)

print r.recvline()
r.close()

# python get_flag.py
604672456
322278383
3842182927
2626463750
2042127376
830485493
3402655117
2936071940
3380135806
3463756493
flag is ALEXCTF{f0cfad89693ec6787a75fa4e53d8bdb5}

References

https://en.wikipedia.org/wiki/Linear_congruential_generator
http://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator

# 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