Consistently Static Psuedo Random Number Generator — broncoctf2026

Description

I made a birthday oracle recently, but I can't get it to work at all. It only gets the day of the week right 14% of the time! Here are my results from the last testing session... can you take a look at it and see what's wrong?

Two files are provided:

• results.txt — a transcript of the oracle guessing month / day-of-week / region 101 times.
• challenge.py — the source of the "broken" PRNG-backed oracle.

Goal: recover the flag, which is used directly as the PRNG entropy/seed.

The "14% right on day of week" hint is 1/7 — the RNG is not random at all, it is a fully deterministic linear recurrence whose entire internal state is the flag.

Analysis

The vulnerable source:

import random

class RNG:
    def __init__(self, entropy: bytes):
        self.nextrep = 0
        shift = random.randint(0, len(entropy))
        self.schedule = list(range(len(entropy)))
        self.schedule = self.schedule[shift:] + self.schedule[:shift]
        if random.random() > 0.5:
            self.schedule.reverse()
        self.state = list(entropy)

    def next(self):
        a = sum(self.state) % 256
        self.state[self.schedule[self.nextrep % len(self.schedule)]] = a
        self.nextrep += 1
        return a

flag = open("flag.txt","rb").read()
rand = RNG(flag)
# loop prints "born in {month}... on a {day}, in {area}"
guess = rand.next()
month = months[guess % 12]
day   = days[guess % 7]
area  = areas[guess % 5]

Key observations:

1. The flag IS the state. state is initialized to the flag bytes. There is no external randomness in next() — only random.randint/random.random in the constructor pick a rotation shift and an optional reverse of the update schedule.

2. Each output leaks a full state sum. Output a[k] = sum(state) % 256 before step k. Then step k overwrites exactly one state slot p = schedule[k] with a[k].

3. The oracle never prints the raw byte. It only discloses three residues per output: guess % 12 (month), guess % 7 (day), guess % 5 (region).

Step 1 — Recover raw output bytes via CRT

lcm(12, 7, 5) = 420 > 255, so the triple (guess%12, guess%7, guess%5) uniquely identifies a byte in 0..255. Parse each transcript line back to the residue triple, then find the unique x in 0..255 matching all three moduli. This yields all 101 raw output bytes.

Step 2 — Invert the linear recurrence

At step k, the only state change is slot p = schedule[k] being overwritten with a[k]. Therefore:

a[k+1] = a[k] - old_value_at_p + a[k]   (mod 256)
       = 2*a[k] - old_value_at_p        (mod 256)
=> old_value_at_p = (2*a[k] - a[k+1])   (mod 256)

For the first pass k = 0 .. L-1 (where L = flag length), each slot is being written for the first time, so old_value_at_p is exactly the original flag byte at position schedule[k]:

flag[schedule[k]] = (2*out[k] - out[k+1]) mod 256

Step 3 — Reconstruct the schedule ordering (the critical pitfall)

The recovered values from step 2 are indexed by schedule[k], not by flag position. schedule is range(L) rotated by an unknown shift and optionally reversed. You must:

• brute-force flag length L,
• brute-force shift in 0..L-1 and reverse in {False, True},
• place each recovered value at position schedule[k],
• and then re-simulate the entire RNG and confirm it reproduces all 101 observed outputs.

The unique consistent solution is L = 34 (33 printable chars + trailing \n), reversed schedule, shift = 15.

Pitfall lesson: a naive attempt that reads the (2*out[k]-out[k+1]) stream directly as flag bytes (just reverse-rotating the raw stream) produced the WRONG flag bronco{crypt0_1uREDACTED} (extra u). That is because the recovered values are ordered by schedule[k], not by flag index. Only reconstructing the schedule and validating by full re-simulation yields the correct byte order.

Solution

#!/usr/bin/env python3
import re
from pathlib import Path

months = ["January","February","March","April","May","June",
          "July","August","September","October","November","December"]
days   = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
areas  = ["Asia","Africa","the Americas","Europe","Australia"]

rows = re.findall(
    r"born in (\w+)\.\.\. on a (\w+), in (Asia|Africa|the Americas|Europe|Australia)",
    Path("results.txt").read_text(),
)

# Step 1: CRT-recover each raw output byte from (mod 12, mod 7, mod 5)
outputs = []
for m, d, a in rows:
    res = (months.index(m), days.index(d), areas.index(a))
    outputs.append([x for x in range(256) if (x % 12, x % 7, x % 5) == res][0])

def sim(flag, shift, rev):
    """Re-run the RNG exactly and return the produced output stream."""
    L = len(flag)
    sched = list(range(L))
    sched = sched[shift:] + sched[:shift]
    if rev:
        sched = sched[::-1]
    state = list(flag)
    out = []
    for _ in range(len(outputs)):
        v = sum(state) % 256
        state[sched[len(out) % L]] = v
        out.append(v)
    return out

# Steps 2 & 3: invert recurrence, brute-force schedule, validate by re-simulation
for L in range(8, 60):
    # original flag byte written at schedule[k] during the first pass
    removed = [(2 * outputs[k] - outputs[k + 1]) % 256 for k in range(L)]
    for rev in (False, True):
        for shift in range(L):
            sched = list(range(L))
            sched = sched[shift:] + sched[:shift]
            if rev:
                sched = sched[::-1]
            flag = [None] * L
            for k in range(L):
                flag[sched[k]] = removed[k]
            if None in flag:
                continue
            if sim(flag, shift, rev) == outputs:
                print(L, shift, rev, bytes(flag))
# -> 34 15 True b'bronco{REDACTED}\n'