Tokyo Westerns CTF 2018 - Mixed Cipher

mixed_cipher.py

from pwn import *
from randcrack import RandCrack
from gmpy import gcd
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES

# proc = remote('crypto.chal.ctf.westerns.tokyo', 5643)
proc = process('./server.py')

# context.log_level = 'debug'

BLOCK_SIZE = 16

def aes_decrypt(key, s):
    iv = s[:BLOCK_SIZE]
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.decrypt(s[BLOCK_SIZE:])

def encrypt(s):
    proc.recvlines(6)
    proc.sendline('1')
    proc.recvuntil("text: ")
    proc.sendline(s)
    rsa = proc.recvline().strip().split()[1]
    aes = proc.recvline().strip().split()[1]
    return [int(rsa, 16), aes.decode('hex')]

def decrypt(c):
    proc.recvlines(6)
    proc.sendline('2')
    proc.recvuntil("text: ")
    s = long_to_bytes(c).encode('hex')
    proc.sendline(s)
    proc.recvline()
    rsa = proc.recvline().strip().split()[1]
    print rsa
    return rsa.decode('hex')

def print_flag():
    proc.recvlines(6)
    proc.sendline('3')
    proc.recvline()
    proc.recvline()
    return proc.recvline().strip().decode('hex')

def get_enc_key():
    proc.recvlines(6)
    proc.sendline('4')
    proc.recvline()
    return int(proc.recvline().strip(), 16)

rc = RandCrack()

for i in range(156):
    iv = encrypt('a')[1][:16]
    iv = iv[::-1]
    rc.submit(u32(iv[0:4]))
    rc.submit(u32(iv[4:8]))
    rc.submit(u32(iv[8:12]))
    rc.submit(u32(iv[12:16]))

a_enc = encrypt('a')[0]
rc.predict_getrandbits(128)
b_enc = encrypt('b')[0]
rc.predict_getrandbits(128)

e = 65537
n = gcd(ord('a')**e - a_enc, ord('b')**e - b_enc)
print 'N: ', n

enc_key = get_enc_key()
enc_flag = print_flag()
actual_iv = long_to_bytes(rc.predict_getrandbits(128), 16)
enc_flag = actual_iv + enc_flag[16:]
print 'Encrypted Key: ', enc_key
print 'Encrypted Flag: ', enc_flag.encode('hex')

bounds = [(0, 1), (1, 1)]
c = enc_key

for _ in range(0, n.bit_length(), 2):
    print _, bounds
    nm_half = bounds[0][0] * bounds[1][1] + bounds[1][0] * bounds[0][1]
    dm_half = bounds[0][1] * bounds[1][1] * 2
    g = gcd(nm_half, dm_half)
    nm_half, dm_half = nm_half / g, dm_half / g

    c = (pow(4, e, n) * c) % n
    res = ord(decrypt(c)[-1]) % 4

    if res == 0:
        nm = bounds[0][0] * dm_half + bounds[0][1] * nm_half
        dm = bounds[0][1] * dm_half * 2
        g = gcd(nm, dm)
        nm, dm = nm / g, dm / g
        bounds[1] = (nm, dm)
    elif res == 1:
        nm = bounds[0][0] * dm_half + bounds[0][1] * nm_half
        dm = bounds[0][1] * dm_half * 2
        g = gcd(nm, dm)
        nm, dm = nm / g, dm / g
        bounds[0] = (nm, dm)
        bounds[1] = (nm_half, dm_half)
    elif res == 2:
        nm = nm_half * bounds[1][1] + dm_half * bounds[1][0]
        dm = dm_half * bounds[1][1] * 2
        g = gcd(nm, dm)
        nm, dm = nm / g, dm / g
        bounds[0] = (nm_half, dm_half)
        bounds[1] = (nm, dm)
    else:
        nm = nm_half * bounds[1][1] + dm_half * bounds[1][0]
        dm = dm_half * bounds[1][1] * 2
        g = gcd(nm, dm)
        nm, dm = nm / g, dm / g
        bounds[0] = (nm, dm)

key = long_to_bytes(bounds[1][0] * n / bounds[1][1])
print 'Key: ', key.encode('hex')

print aes_decrypt(key, enc_flag)

randcrack.py

class RandCrack:

    def __init__(self):
        self.counter = 0
        self.mt = []
        self.state = False

    def submit(self, num):
        if self.state:
            print("Already got enough bits")
            return
        bits = self._to_bitarray(num)

        assert(all([x == 0 or x == 1 for x in bits]))
        self.counter +=1
        self.mt.append(self._harden_inverse(bits))
        if self.counter == 624:
            self._regen()
            self.state = True

    def _predict_32(self):
        if not self.state:
            print("Didn't recieve enough bits to predict")
            return 0
        if self.counter >= 624:
            self._regen()
        self.counter += 1

        return self._harden(self.mt[self.counter-1])

    def predict_getrandbits(self,k):
        if not self.state:
            print("Didn't recieve enough bits to predict")
            return 0
        if k == 0:
            return 0
        words = (k-1) // 32 + 1
        res = []
        for i in range(words):
            r = self._predict_32()
            if k < 32:
                r = [0]*(32-k) +r[:k]
            res = r + res
            k -= 32
        return self._to_int(res)

    def predict_randbelow(self, n):
        k = n.bit_length() 
        r = self.predict_getrandbits(k)
        while r >= n:
            r = self.predict_getrandbits(k)
        return r

    def predict_randrange(self, start, stop=None, step=1, _int=int):
        # Adopted messy code from random.py module
        # In fact only changed _randbelow() method calls to predict_randbelow()
        istart = _int(start)
        if istart != start:
            raise ValueError("non-integer arg 1 for randrange()")
        if stop is None:
            if istart > 0:
                return self.predict_randbelow(istart)
            raise ValueError("empty range for randrange()")

        # stop argument supplied.
        istop = _int(stop)
        if istop != stop:
            raise ValueError("non-integer stop for randrange()")
        width = istop - istart
        if step == 1 and width > 0:
            return istart + self.predict_randbelow(width)
        if step == 1:
            raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))

        # Non-unit step argument supplied.
        istep = _int(step)
        if istep != step:
            raise ValueError("non-integer step for randrange()")
        if istep > 0:
            n = (width + istep - 1) // istep
        elif istep < 0:
            n = (width + istep + 1) // istep
        else:
            raise ValueError("zero step for randrange()")

        if n <= 0:
            raise ValueError("empty range for randrange()")

        return istart + istep*self.predict_randbelow(n)

    def predict_randint(self, a,b):
        return self.predict_randrange(a, b+1)

    def predict_choice(self, seq):
        try:
            i = self.predict_randbelow(len(seq))
        except ValueError:
            raise IndexError('Cannot choose from an empty sequence')
        return seq[i]

    def _to_bitarray(self, num):
        k = [int(x) for x in bin(num)[2:]]
        return [0] * (32-len(k)) + k

    def _to_int(self, bits ):
        return int("".join(str(i) for i in bits), 2)

    def _or_nums(self, a, b):
        if len(a) < 32:
            a = [0]* (32-len(a))+a
        if len(b) < 32:
            b = [0]* (32-len(b))+b

        return [x[0] | x[1] for x in zip(a, b)]

    def _xor_nums(self, a, b):
        if len(a) < 32:
            a = [0]* (32-len(a))+a
        if len(b) < 32:
            b = [0]* (32-len(b))+b

        return [x[0] ^ x[1] for x in zip(a, b)]

    def _and_nums(self, a, b):
        if len(a) < 32:
            a = [0]* (32-len(a))+a
        if len(b) < 32:
            b = [0]* (32-len(b))+b

        return [x[0] & x[1] for x in zip(a, b)]




    def _decode_harden_midop(self, enc, and_arr, shift):
        
        NEW = 0
        XOR = 1
        OK =  2
        work = []
        for i in range(32):
            work.append((NEW,enc[i]))
        changed = True
        while changed:
            changed = False
            for i in range(32):
                status = work[i][0]
                data = work[i][1]
                if i >= 32-shift and status == NEW:
                    work[i] = (OK,data)
                    changed = True
                elif i < 32-shift and status == NEW:
                    if and_arr[i] == 0:
                        work[i] = (OK, data)
                        changed = True
                    else:
                        work[i] = (XOR, data)
                        changed = True
                elif status == XOR:
                    i_other = i+shift
                    if work[i_other][0] == OK:
                        work[i] = (OK, data ^ work[i_other][1])
                        changed = True

        return [x[1] for x in work]


    def _harden(self, bits):
        bits = self._xor_nums(bits, bits[:-11])
        bits = self._xor_nums(bits, self._and_nums(bits[7:] + [0] * 7 , self._to_bitarray(0x9d2c5680)))
        bits = self._xor_nums(bits, self._and_nums(bits[15:] + [0] * 15 , self._to_bitarray(0xefc60000)))
        bits = self._xor_nums(bits, bits[:-18])
        return bits

    def _harden_inverse(self, bits):
        # inverse for: bits = _xor_nums(bits, bits[:-11])
        bits = self._xor_nums(bits, bits[:-18])
        # inverse for: bits = _xor_nums(bits, _and_nums(bits[15:] + [0] * 15 , _to_bitarray(0xefc60000)))
        bits = self._decode_harden_midop(bits, self._to_bitarray(0xefc60000), 15)
        # inverse for: bits = _xor_nums(bits, _and_nums(bits[7:] + [0] * 7 , _to_bitarray(0x9d2c5680)))
        bits = self._decode_harden_midop(bits, self._to_bitarray(0x9d2c5680), 7)
        # inverse for: bits = _xor_nums(bits, bits[:-11])
        bits = self._xor_nums(bits, [0] * 11 + bits[:11]+[0] * 10)
        bits = self._xor_nums(bits, bits[11:21])

        return bits


    def _regen(self):
        # C code translated from python sources
        N = 624
        M = 397
        MATRIX_A = 0x9908b0df
        LOWER_MASK = 0x7fffffff
        UPPER_MASK = 0x80000000
        mag01 = [self._to_bitarray(0), self._to_bitarray(MATRIX_A)]

        l_bits = self._to_bitarray(LOWER_MASK)
        u_bits = self._to_bitarray(UPPER_MASK)
        
        for kk in range(0,N-M):
            y = self._or_nums(self._and_nums( self.mt[kk], u_bits), self._and_nums(self.mt[kk+1],l_bits))
            self.mt[kk] = self._xor_nums(self._xor_nums( self.mt[kk+M] , y[:-1]) , mag01[y[-1] & 1])

        for kk in range(N-M-1, N-1):
            y = self._or_nums(self._and_nums( self.mt[kk], u_bits), self._and_nums(self.mt[kk+1],l_bits))
            self.mt[kk] = self._xor_nums(self._xor_nums( self.mt[kk+(M-N)] , y[:-1]) , mag01[y[-1] & 1])

        y = self._or_nums(self._and_nums( self.mt[N-1], u_bits), self._and_nums(self.mt[0],l_bits))
        self.mt[N-1] = self._xor_nums(self._xor_nums( self.mt[M-1] , y[:-1]) , mag01[y[-1] & 1])

        self.counter = 0


if __name__ == "__main__":
    import random, time

    print("Testing random module cracker...")

    cracker = RandCrack()

    random.seed(time.time())

    for i in range(624):
        cracker.submit(random.randint(0,4294967294))

    print("Guessing next 32000 random bits success rate: {}%"
        .format(sum([random.getrandbits(32)==cracker.predict_getrandbits(32) for x in range(1000)])/10))