Flag from the Future

Full solution below. Spoilers ahead.

Task description

I found this neat drawing program online and wrote the flag using one of my favorite fonts. 🎨 I pressed the play button, and before I could react, the flag transformed itself into these weird shapes. Why is there no rewind button!? Can you help me recover the flag?

Note: The flag was rendered from one of the DejaVu 2.37 TTF files at an integer pixel size. Every rasterized pixel with an intensity of at least 50% became a live cell.

The handout is a single screenshot.png, white squares on black, and there is no service. The “drawing program with a play button” is a cellular automaton: the flag text was rasterised into live cells and then stepped forward an unknown number of generations.

Conway's Game of Life, and why it does not rewind

Life runs on an infinite grid of cells, each dead or alive. Every generation, all cells update at once from their eight neighbours under rule B3/S23: a dead cell with exactly three live neighbours is born, a live cell with two or three neighbours survives, everything else dies. From a starting pattern you get one and only one next pattern.

Going the other way is the problem. Many different boards collapse to the same successor (a lone cell with no neighbours dies, and so does a cell with four, so the previous state is ambiguous), which is why there is no rewind button. What saves the attack is that Life is still local: a cell’s next state depends only on its immediate neighbours, so after N generations a given cell depends only on the starting cells within N steps of it. That bounded cone of influence is what lets a guess be tested without ever stepping backward.

From screenshot to grid

Each cell is a 6 by 6 pixel square on an 8 pixel pitch (column j covers x = 8j-1 to 8j+4, row i covers y = 8i to 8i+5). Sampling one pixel near the centre of each cell turns the image into a binary grid:

a = np.array(Image.open('screenshot.png').convert('L')) > 128
g = np.array([[a[8*i+2, 8*j+1] if 8*j+1 < a.shape[1] else 0
               for j in range(383)] for i in range(36)], np.uint8)

Running that on the handout, and then painting the grid back out as 6 by 6 squares to check nothing was lost:

image size (WxH): (3062, 288)
grid shape: (36, 383)   live cells: 909
differing pixels (rebuild vs original): 0

The redraw matches the screenshot pixel for pixel, so the 36 by 383 grid of 909 live cells is a faithful copy of the board. Everything after this works on that grid.

Identifying the rule and the generation count

The board holds blinkers (a row of three that flips between horizontal and vertical), beehives (a stable six-cell ring) and three identical lens shapes along the bottom. These are standard Conway’s Life objects, which fixes the rule as B3/S23. The lenses are the giveaway: they are the busy middle phase of a pentadecathlon, a period-15 oscillator whose clean phase is a straight 1 by 10 bar of cells. A bar seen a few generations on looks exactly like these lenses.

That pins down two things at once. The three lenses are _ characters, drawn as 1 by 10 bars, and the generation count N satisfies N = 3 (mod 15), because that is the phase offset from the clean bar to the shape on the board. The bars sit on row 27 and start at columns 162, 201 and 297, which also fixes where three of the underscores are in the original.

Testing guesses with the light cone

Because Life loses information, I could not step backward, so I guessed forward and compared. A cell after N generations depends only on the starting cells within N columns of it (the light cone from the box above). If the first k characters are known, then every column more than N to the left of character k+1’s ink is fully determined by the known prefix, and has to match the screenshot exactly. A single mismatch kills the guess. That turns an impossible global inversion into a search one character at a time over printable ASCII, with the flag format (FortID{...}) giving the first seven characters for free.

Font, size and N all came from the leading F. I simulated the known prefix for every DejaVu 2.37 face at pixel sizes 8 to 47 and several hinting modes, keeping only combinations where _ renders as a 1 by 10 bar and N = 3 (mod 15). One reproduced all 46 live cells around the F with no mismatch: DejaVuSansMono-Bold, 16 px, default hinting, N = 18. The underscore row fixes the baseline at row 24 and the F fixes the pen origin at column 8.

The pen advance gotcha

A plain monospace layout with a flat 10 px advance (what Pillow’s default text layout does) reproduces the first three characters and then drifts. The underscores give the layout away: they sit 154, 193 and 289 px from the origin, which are not multiples of 10. Dividing instead by the unhinted advance of DejaVu Sans Mono (1233/2048 em times 16 px, or 9.6328 px) gives exactly 16.0, 20.0 and 30.0 character cells. So the glyph bitmaps are hinted, but the pen advances by the fractional unhinted width and is rounded to a whole pixel per glyph.

The arithmetic is where real time went. FreeType carries the pen in 26.6 fixed point (units of 1/64 px) and stores the advance as the integer 617 (that is 617/64 = 9.6406 px), not the exact 616.5/64 = 9.6328 px. The two only disagree once the accumulated error crosses half a pixel, which first happens at character 15: 617*15/64 = 144.61 rounds to column 145, while 616.5*15/64 = 144.49 rounds to 144. Every early search that used the exact float advance died at exactly that character, on every alphabet and every font, which looked like a wrong-character bug but was a rounding bug. With FreeType’s own value, glyph k lands at:

x = origin + (617 * k + 32) // 64 + bitmap_left

I also tried trimming the influence radius to 10 to 17 columns to speed the search up. It occasionally rejected the true character, so the exact 18-column cone (plus one column for glyphs whose bitmap starts left of the pen) is the only safe test. A shorter radius is fine for ranking candidates, never for rejecting them.

The search and the check

For each prefix I tried every printable character, ran 18 generations on a window around the new glyph (batched with numpy) and kept the prefixes whose newly determined column slice matched exactly. A freshly placed character barely affects its own slice, so up to roughly 95 squared prefixes can survive a single level, then collapse to one as soon as the next slice is checked. Near the right edge I enumerated the last few characters before } and required the whole board to match. The run walked out cleanly to a single candidate:

0  41    FortID{R
4  1     FortID{R3al_
0  54    FortID{R3al_L1f3           (after fixing the 617/64 advance)
11 1     FortID{R3al_L1f3_...
18 2849  FortID{R3al_L1f3_...
...      (tail enumerated, single whole-board match)

As a final independent check I rendered the winning candidate on a plane padded by 60 cells, ran 18 generations and compared with the screenshot:

face = ft.Face('DejaVuSansMono-Bold.ttf'); face.set_pixel_sizes(0, 16)
for ch in flag:
    face.load_char(ch, ft.FT_LOAD_DEFAULT | ft.FT_LOAD_RENDER)
    gl = face.glyph; bm = gl.bitmap
    a = np.array(bm.buffer, np.uint8).reshape(bm.rows, bm.pitch)[:, :bm.width]
    x = P + 8 + (pen + 32)//64 + gl.bitmap_left; y = P + 24 - gl.bitmap_top
    g[y:y+a.shape[0], x:x+a.shape[1]] |= (a >= 128)      # at least 50% intensity
    pen += (gl.linearHoriAdvance + 512)//1024            # 16.16 to 26.6, gives 617
for _ in range(18): g = step(g)

The recorded output was:

advance 26.6 = 617
mismatches on visible board: 0   live cells outside view: 0   live: 909 / 909

All 909 live cells match and nothing lands outside the view. The three underscores fall at string indices 16, 20 and 30, exactly the three pentadecathlons. The recovered string is the flag in the field below.

Why locality beats irreversibility

“Irreversible” is not the same as “hides the input”. Life discards information globally, but its locality, plus a strong prior (a known font and the FortID{...} format), rebuilds the input one character at a time. The same reasoning applies to any local transform used as obfuscation, such as a blur, a pixelation or a convolution: if an attacker can model the forward process exactly, they can search the input space piece by piece. The long-lived oscillators made it worse for the defender, because their phase leaked the generation count and their position leaked the glyph layout before a single character had been guessed.