exploit.py

import time
import random
import os
from pwn import *
from sage.all import divisors

r = remote('crypto.2021.chall.actf.co', 21600)

class Generator():
    DIGITS = 8
    def __init__(self, seed):
        self.seed = seed
        assert(len(str(self.seed)) == self.DIGITS)

    def getNum(self):
        self.seed = int(str(self.seed**2).rjust(self.DIGITS*2, "0")[self.DIGITS//2:self.DIGITS + self.DIGITS//2])
        return self.seed
        
def valid(x):
	if (x // pow(10, 7) > 0 and x // pow(10, 8) == 0):
		return True
	return False

def find_r(x, y):
    d = divisors(x)

    for r1 in d:
        if (valid(r1) == False):
            continue
        r2 = x // r1
        if (valid(r2) == False):
            continue

        print ('[*] Checking divisors:')
        print ('\t|p1: {0}\n\t|p2: {1}'.format(r1, r2))
            
        g1 = Generator(r1)
        g2 = Generator(r2)

        o = g1.getNum() * g2.getNum()
        if (o == y):
            return (r1, r2)
        
    raise Exception('divisors not found')

def attack():
    print ('[*] Randoms recovery phase')
    r.sendlineafter('? ', 'r')
    x1 = int((r.recvuntil('\n')[:-1]).decode())
    r.sendlineafter('? ', 'r')
    x2 = int((r.recvuntil('\n')[:-1]).decode())

    r1, r2 = find_r(x1, x2)
    g1 = Generator(r1)
    g2 = Generator(r2)

    # sync with server
    g1.getNum()
    g2.getNum()

    print ('[*] Guessing phase')
    r.sendlineafter('? ', 'g')
    for i in range(2):
        y = g1.getNum() * g2.getNum()
        print ('[+] Next random: {0}'.format(y))
        r.sendlineafter('? ', str(y))

    print(r.recv())
	
attack()