Rocinate

The brief

🤭😂

• rocinate.zip, 116 KB

In short

Rocinate hides the flag in a Guillou Quisquater style transcript. Every secret comes from Python's Mersenne Twister and Z is never reduced mod N, so rebuilding and rewinding the generator turns the protocol into division.

Two emojis and a transcript

The description is two emojis. A 714 byte script hides the flag as a secret s and prints 100 rounds of an identification protocol over a 2047 bit modulus N, with T = r^e mod N and Z = r times s^c.

One product left unreduced

Z should be reduced mod N. It is not, so each Z is the exact product of r and s^c mod N, 4,083 to 4,094 bits long. Whoever knows r can unmask s^c by plain division.

Every secret from one generator

The seed r, the exponent e, the constants a and b and all 100 values of c come from Python's random, the Mersenne Twister. The 102 published draws carry 6,528 of its 32 bit words. 624 words fix its whole state.

Ten draws with no gaps

About 22 percent of draws are at least N and get thrown away unseen, which leaves gaps. The lab tested the twister's own recurrence on the published words and found ten back to back draws with no gap between them.

Rebuilt, then run backwards

Nine words in that window had lost their lowest bit, so the lab tried all 512 fillings and kept the one that predicted the next draws. Run in reverse, the generator gave a 26 draws back, then e and r just before it.

Division, then Bezout

The LCG from r gives all 100 values of r, and each Z divides exactly, leaving s^c mod N. Two coprime exponents combined with Bezout coefficients give s. It fits all 100 rounds, and it is the flag.

The insight

Secrets drawn from Python's random leak the generator itself. 102 public draws were enough to rebuild it and rewind it to the hidden seed and exponent.

The flag

hiCTF{lmaoooo_w0t???y0u_d1d_17_??435p37++}