Rip and Tear

Full solution below. Spoilers ahead.

Task description

I cloned the best source port of my favorite childhood game, and played around with the source code a bit. Take a look at what I did, and watch how I rip and tear through E1M1.

The handout is chocolate-doom.patch (a diff against Chocolate Doom), gameplay.mkv (a 4 minute 12 second, 1920 by 1080, 60 fps recording of the patched build) and a solver/solve.py. There is no service, so the recording is the only output of the real binary that an attacker gets.

int M_Random (void) { rndindex = (rndindex+1)&0xff; return rndtable[rndindex]; }
int P_Random (void) { prndindex = (prndindex+1)&0xff; return rndtable[prndindex]; }

What the patch does

The patch touches one file, src/doom/m_random.c. It removes the const from rndtable so the array becomes writable, and adds an InitRndtable that runs once, the first time any random function is called, XORing one flag bit into the low bit of every entry:

static const char* FLAG = "FortID{<REDACTED>}";
...
assert(flagLength == 32);
for (i = 0; i < 256; ++i) {
    byteIndex = i / 8;
    bitIndex  = 7 - (i % 8);                   // most significant bit first
    flagBit   = (FLAG[byteIndex] >> bitIndex) & 1;
    rndtable[i] ^= flagBit;
}

The assert(flagLength == 32) fixes the flag at exactly 32 bytes, which is 256 bits, one for each table entry. If I can tell, for a given index i, whether the game used rndtable[i] or rndtable[i] ^ 1, I learn flag bit i. The bit order is most significant first within each byte, so bit 8*k is the top bit of character k, a fact the solver uses later.

Where randomness shows on screen

The melt callers are in wipe_initMelt in f_wipe.c, the transition where the old screen drips away column by column. That code is stock Chocolate Doom (the full source tree is not in the handout, only the patch), so these lines are quoted from upstream:

y[0] = -(M_Random()%16);
for (i=1;i<width;i++) {
    r = (M_Random()%3) - 1;
    y[i] = y[i-1] + r;
    if (y[i] > 0) y[i] = 0;
    else if (y[i] == -16) y[i] = -15;
}

Each melt column is 2 pixels wide, so there are 160 columns on the 320 pixel screen. Column 0 gets a start delay y[0] = -(M_Random() % 16), and every later column’s step y[i] - y[i-1] is (v % 3) - 1 for the next value v. What makes the step readable is that v and v ^ 1 are always consecutive integers (flipping the low bit adds or subtracts one), and consecutive integers never agree modulo 3, so v % 3 and (v ^ 1) % 3 always differ. One visible column step therefore pins down one flag bit. The only steps that lose information are those clamped at 0 or at -15.

There are other M_Random callers (the status-bar face, sound pitch, the intermission screen). I did not audit the complete list of callers against the source; the melt is the one that writes 160 consecutive table reads straight onto the screen, which is what makes it usable.

Measuring the melt in the video

wipe_doMelt advances each column every tic. A column with y < 0 waits while y counts up toward 0; once it reaches 0 it slides down by dy = y + 1 while y < 16, then by 8 pixels per tic. After tau active tics the displacement is one of 0, 1, 3, 7, 15, 31, 39, 47, ... (this exact list is POS in the solver). Each displacement value belongs to exactly one tau, and within any single frame a column’s tau = t + y0, where t is the frame’s tic count and y0 the column’s start delay. The solver (solve.py) hardcodes the parts that are fixed properties of the recording:

• the game viewport inside the 1920 by 1080 frame: CROP = "crop=1357:1017:281:31", which is x = 281 to 1637 and y = 31 to 1047 (4:3, pillarboxed);
• the four wipes, as (frame before, frame after) pairs: WIPES = [(116, 188), (350, 425), (11127, 11205), (12050, 12128)].

The pipeline then runs, per wipe:

1. Normalise. ffmpeg crops the viewport and area-downsamples it back to 320 by 200, so one pixel is one Doom pixel:

   ffmpeg -i gameplay.mkv -vf "crop=1357:1017:281:31,scale=320:200:flags=area,format=rgb24" -f rawvideo rgb.raw

2. Fit the displacement per column. For every distinct frame inside a wipe and each 2-pixel column, find the shift s that best explains frame = new_screen[0:s] ++ old_screen[0:200-s], where the old and new screens are the frames just before and just after the melt. Scoring the whole column is far more reliable than matching a small region such as the status bar.

3. Recover y0. Map displacements to tau, then jointly solve for the per-frame tic count t and the per-column y0 by alternating majority votes of tau - t and tau - y0 until they stop changing. This gives y0 for all 160 columns, up to one unknown global offset, because the first melt tics are not always captured on camera.

4. Align with the table. Brute-force the global tic offset (range -20 to 20) and the starting rndindex k0 (256 options). A column step gives the bit that makes rndtable[k0+j] or rndtable[k0+j] ^ 1 reproduce the observed step, and the correct (offset, k0) is the one with zero contradictions. A wrong pair breaks about a third of the steps, so the choice is unambiguous. The recorded output was:

   wipe @116:   best (bad, offset, k0) = [(0, -3, 232), (0, -2, 232), (1, -1, 232)]
   wipe @350:   best (bad, offset, k0) = [(0, -8, 2),   (9, -7, 2),   (10, -6, 2)]
   wipe @11127: best (bad, offset, k0) = [(0, -1, 144), (1, -7, 144), (1, -6, 144)]
   wipe @12050: best (bad, offset, k0) = [(0, -5, 21),  (4, -4, 21),  (5, -3, 21)]

The four wipes start at table indices 232, 2, 144 and 21, and each covers 160 consecutive indices, so between them they cover all 256 bits, most of them more than once.

Resolving the conflicts

The solver needs ffmpeg and a roughly four-minute decode of the 1080p video. The flag line is redacted here per house style:

python -P solver/solve.py gameplay.mkv chocolate-doom/src/doom/m_random.c <workdir>

  bit 116: conflicting votes [0, 1, 0]
  bit 117: conflicting votes [1, 0, 1]
  bit 232: conflicting votes [1, 0]
FortID{...}

Three bits disagreed between wipes:

• Bits 116 and 117 fall in byte 14. Two wipes agree and wipe 2 disagrees, and wipe 2’s column 113 had only two usable measurements and feeds exactly these two steps, so the majority wins.
• Bit 232 is the top bit of byte 29. Wipe 1 has a tied plus-or-minus-one offset that only changes y[0] % 16. Since the flag is ASCII, every top bit has to be 0, which is also what wipe 3 reports. The solver encodes this directly by forcing bits[8*k] = 0 for all 32 bytes.

To check the answer, I built the modified table from the recovered flag, re-simulated wipe_initMelt at each wipe’s k0, and compared against the measured y0 columns. 639 of 640 columns matched, the single miss being the weak column in wipe 2:

116   k0 232  mismatching columns []
350   k0 2    mismatching columns [114]
11127 k0 144  mismatching columns []
12050 k0 21   mismatching columns []

The FortID{ prefix and the closing } fell out of the video without being forced, which independently confirms the alignment. The 32 characters of the recovered string are in the field below.

Defence

Anything that keys a generator, even a cosmetic one, leaks through every effect it drives, and a screen recording captures the result at full resolution. A “harmless” low bit does not exist once a visible transform like % 3 preserves the difference between neighbouring values. Treat recordings and replays as data that carries internal state, and never seed a shipped generator with a secret.