Problem Summary

Dr. Evil wants to play a game and he demands one million billion shitcoins for the flag.

52.59.124.14:5032

chall.py contains a pseudo-RNG CRG that randomly generates

  • a 64-bit modulus self.m
  • a relatively prime parameter self.a, and
  • a relatively prime initial state self.state.
def __init__(self, n):
    '''n - bitlength of state'''
    self.n = n
    self.m = getRandomNBitInteger(n)
    while True:
        self.a = bytes_to_long(os.urandom(n >> 3)) % self.m # n/8 bytes
        if math.gcd(self.a, self.m) == 1: break
    while True:
        self.state = bytes_to_long(os.urandom(n >> 3)) % self.m # n/8 bytes
        if math.gcd(self.state, self.m) == 1: break
    self.buffer = []

This pseudo-RNG yields random bits by enumerating the bits of self.state, generating a new state self.state = self.a * pow(self.state, 3, self.m) % self.m when the bits run out.

def next(self):
    if self.buffer == []:
        self.buffer = [int(bit) for bit in bin(self.state)[2:].zfill(self.n)]
        self.state = self.a * pow(self.state, 3, self.m) % self.m
        #log('new state: ', self.state)
    return self.buffer.pop(0)

The pseudo-RNG is used to generate a series of coin flips. We can either gain money by guessing a coin flip correctly or lose money by guessing incorrectly. Our goal is to gain enough money to reach a balance of at least 1000000000.

Solution

Observe that we only need to know one bit in self.state before it is revealed. We will bet an amount of 1 whenever we are unsure of the next bit and an amount of our whole balance when we are sure. On average, our 1 bets will contribute an amount of 0 while our balance bets will double our balance, meaning our balance will grow exponentially.

For the bit that we aim to know, we focus our attention to the units bit, as it is special and can sometimes be predicted when doing these types of operations. In particular, if self.m is even, then self.a and self.state are guaranteed to be odd as they are relatively prime to self.m. When this happens, self.state starts out as odd, and self.a * pow(self.state, 3, self.m) % self.m will continue to be odd. As such, in this case we can reliably predict units bit (i.e. every 64th bit) to be a 1.

The script below predicts head (0) for all non-units bits (as it is slightly more frequent due to Benford’s law) and tails (1) for all units bits. We’ll rerun the script until we obtain a m that is even and luckily gain enough balance so that the bets of amount 1 are not enough to bankrupt us.

from pwn import *

r = remote("52.59.124.14", 5032)

try:
    cnt = 0
    while True:
        for i in range(64):
            print((line := r.recvline().strip()))
            amount = int(line[line.find(b"(you have ") + 10:line.find(b")")])
            if i < 63:
                r.sendline(b"1")
                print(r.recvline())
                r.sendline(b"head")
            else:
                r.sendline(bytes(str(amount), "utf-8"))
                print(r.recvline())
                r.sendline(b"tails")

            print(line := r.recvline().strip())
            win = line == b"you win"

            cnt += 1
except Exception as e:
    while True:
        print(r.recvline())

Flag: ENO{1nfin1t3_r1che5_3re_y0ur5_1t_s33m5}