Rocinate

Task description

🤭😂

• Category: crypto (hard)

Spot the real weakness

In chall.py, r, e, a, b and every C_i come from random.randint, i.e. MT19937. The 100 C_i are public, so they are 100 near-full MT outputs — plenty to reconstruct the generator state. The LCG / e / Bezout machinery is a distraction that only matters for the final arithmetic.

Find a gap-free run of outputs

Each value is 1 + getrandbits(2047), which is 64 words of 32 bits with the low bit of the top word lost. randint(1, N) rejects any draw >= N, and since N / 2^2047 ~= 0.78, roughly 22% of draws are discarded — so the visible outputs are not contiguous in the MT stream. Testing the MT recurrence x[t+624] = x[t+397] ^ F(x[t], x[t+1]) across windows of chunks finds that C15..C33 form a run with no rejected draws in between.

Recover the MT state

Take 624 consecutive words starting at C15, brute-force the 2^9 combinations of the 9 missing top-word low bits, and keep the single candidate whose tempered output matches all 19 gap-free chunks.

MT19937 helpers (temper/untemper, forward recurrence, backward recovery):

M32 = 0xffffffff

def untemper(y):
    y ^= y >> 18
    y ^= (y << 15) & 0xefc60000
    t = y
    for _ in range(5): t = y ^ ((t << 7) & 0x9d2c5680)
    y = t
    t = y
    for _ in range(3): t = y ^ (t >> 11)
    return t & M32

def temper(y):
    y ^= y >> 11
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 15) & 0xefc60000
    y ^= y >> 18
    return y & M32

def F(xt, xt1):
    y = (xt & 0x80000000) | (xt1 & 0x7fffffff)
    return (y >> 1) ^ (0x9908b0df if y & 1 else 0)

def fwd(x, t):
    return x[t+397] ^ F(x[t], x[t+1])

def y_from(x624, x397):
    v = x624 ^ x397
    if v & 0x80000000:
        return (((v ^ 0x9908b0df) << 1) | 1) & M32
    return (v << 1) & M32

Full solver

The solver recovers the state, runs the stream backward to find e and r0, then uses Bezout combination over s^C_i mod N to recover s:

import sys, os, itertools
from math import gcd
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from parse import load
from mt import *

a, b, N, Zs, Cs, Ts = load(sys.argv[1])
K = N.bit_length(); W = (K - 1) // 32 + 1
vals = [a - 1, b - 1] + [c - 1 for c in Cs]

# Collect tempered words from C15..C33 (contiguous run)
start = 2 + 15  # index of C15 in vals
tw = []; part = []
for j in range(19):
    for (w, m) in chunk_words(vals[start + j], K):
        if m: part.append(len(tw))
        tw.append(w)

# Brute-force the 9 missing low bits (one per chunk's top word)
p624 = [i for i in part if i < 624]
sol = None
for bits in itertools.product([0, 1], repeat=len(p624)):
    t2 = tw[:]
    for i, bb in zip(p624, bits): t2[i] |= bb
    x = [untemper(w) for w in t2[:624]]
    good = True
    for t in range(624, len(tw)):
        nx = fwd(x, t - 624); x.append(nx)
        if t in part:
            if temper(nx) >> 1 != tw[t] >> 1: good = False; break
        elif temper(nx) != tw[t]: good = False; break
    if good:
        sol = [untemper(w) for w in t2[:624]]

# Extend stream backward to find e and r0
B = 64 * 60
x = {i: sol[i] for i in range(624)}
for t in range(624, 624 + 64 * 400): x[t] = fwd(x, t - 624)
for t in range(-1, -B, -1):
    hi = y_from(x[t + 624], x[t + 397]) & 0x80000000
    lo = y_from(x[t + 623], x[t + 396]) & 0x7fffffff
    x[t] = hi | lo

def chunk_val(t0):
    v = 0
    for j in range(W):
        o = temper(x[t0 + j]); kk = K - 32 * j
        if kk < 32: o >>= (32 - kk)
        v |= o << (32 * j)
    return v

# Locate every known value in the stream and walk back for e, r0
lo_k = -(B // 64) + 1
seq = [(k, chunk_val(64 * k)) for k in range(lo_k, 64 * 400 // 64 - 1)]
idx = {v: k for k, v in seq}
locs = [idx.get(v) for v in vals]

def prev_accepted(k):
    while chunk_val(64 * k) >= N: k -= 1
    return k

ke = prev_accepted(locs[0] - 1); e = chunk_val(64 * ke) + 1
kr = prev_accepted(ke - 1); r0 = chunk_val(64 * kr) + 1

Rs = [r0]
for _ in range(99): Rs.append((a * Rs[-1] + b) % N)
U = [Z // r for Z, r in zip(Zs, Rs)]

# Bezout combine: s^(gcd of all C_i) = s^1 mod N
g, acc = Cs[0], U[0]
for c, u in zip(Cs[1:], U[1:]):
    if g == 1: break
    def eg(a_, b_):
        x0, x1, y0, y1 = 1, 0, 0, 1
        while b_:
            q_ = a_ // b_; a_, b_ = b_, a_ - q_ * b_
            x0, x1 = x1, x0 - q_ * x1; y0, y1 = y1, y0 - q_ * y1
        return a_, x0, y0
    d, xx, yy = eg(g, c)
    acc = pow(acc, xx, N) * pow(u, yy, N) % N
    g = d

s = acc
print(s.to_bytes((s.bit_length() + 7) // 8, "big"))

Run the stream both ways to get e and r0

With the state known, the stream runs forward normally and backward by inverting the recurrence (high bit of x[t] from y_t, low 31 bits from y_{t-1}). Locate a, b and every C_i in the stream; every chunk sitting between two accepted values is a draw >= N, i.e. a rejection. Walking back from a and skipping rejections gives e (chunk -27) and then r0 (chunk -28). Verified by pow(r_i, e, N) == T_i for all 100 samples and r_i | Z_i over the integers.

Recover s

Since Z_i = r_i * s^C_i is an exact integer product, U_i = Z_i / r_i = s^C_i mod N. The exponents are coprime overall (gcd(C_0, C_1, ...) = 1), so iterated Bezout combination prod U_i^{k_i} = s^{sum k_i C_i} = s^1 = s mod N recovers s directly. Confirmed s^C_i == U_i for all 100 samples; long_to_bytes(s) is the flag.

Lessons

• When all randomness comes from Python’s random module, the problem is an MT19937 state-recovery problem in disguise — the number-theory dressing is a decoy.
• randint(1, N) rejects draws >= N, creating gaps in the MT output stream. Finding a contiguous run and brute-forcing the few missing low bits is tractable.
• Running the MT recurrence backward recovers secrets generated before any public output.