Flag from the Future — FortID CTF 2026

Description

I found this neat drawing program online and wrote the flag using one of my favorite fonts. 🎨 https://dejavu-fonts.github.io/ 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? Here is the screenshot...

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.

English summary. We are given one PNG screenshot (3062x288) of a Conway's Game of Life state. The flag text was rendered with a DejaVu 2.37 TTF at an integer pixel size; every pixel with >=50% intensity became a live cell, then the board was run forward an unknown number of generations of Life. We must invert the CA ("rewind") to recover the text.

Flag format: FortID{...}.

Analysis

1. Semantic clues

• "play button", "live cell", "weird shapes", "no rewind button" → Conway's Game of Life (B3/S23), run forward an unknown number N of generations.
• "Flag from the Future" → the screenshot is the future state; we need the past (initial) state.
• "one of the DejaVu 2.37 TTF files at an integer pixel size", "at least 50% intensity" → the exact rasterization is reproducible with a TrueType rasterizer (FreeType, via PIL) at 50% threshold.

2. Grid extraction

The screenshot draws each live cell as a uniform (204,204,204) block, 6x6 px, on an 8 px pitch, with a (0,0,0) background. Cell (r,c) occupies the block whose top-left is at x = 7 + 8c, y = 8r, so sampling the pixel at (8r, 7+8c) recovers the binary grid directly.

Result: a 382 x 36 binary grid with 909 live cells. Verified by an independent block-mean re-extraction (mean >= 0.5 over each 6x6 block) giving 0 mismatches. The extracted grid is dumped to state.txt.

3. Identify the CA rule

The textures (blocks, beehives, blinkers, and several gliders) are the classic signature of Conway's Game of Life with dead borders. A fingerprint of the neighbour-count histogram of live cells matches B3/S23. We therefore assume B3/S23, dead boundary.

4. Recovering the renderer + generation count

Unknowns: which TTF, which integer size, the draw offset (x0,y0), and N.

Key insight — the Life light cone. Information in Life propagates at most one cell per generation. After drawing k characters, the evolved state of the observed grid region with columns < x0 + advance(k) - N is fully determined by the first k glyphs, because nothing drawn to the right of that boundary can have reached it within N generations.

So we brute-force (font, size, N, offset) and, for the prefix "FortID{", compare only inside the determined region:

• render "FortID{" with FreeType at the candidate size,
• threshold at >= 128 (255 * 0.5),
• evolve N generations,
• measure Hamming mismatch against the screenshot grid inside the determined light-cone window.

To make this fast we use FFT-based normalized cross-correlation (scipy.signal.fftconvolve) of the small evolved prefix template against the full observed grid, so a single pass tests every candidate offset.

The unique exact match (mismatch 0, non-empty template):

parameter	value
font file	DejaVuSansMono-Bold.ttf (monospace, bold)
pixel size	16
threshold	>= 128 (50% intensity)
draw offset (x0,y0)	(7, 9)
generations N	18
rule	B3/S23, dead borders
grid	382 x 36, 909 live cells

Rendering the full flag with these parameters and evolving 18 generations reproduces the screenshot cell-for-cell (difference 0, population 909).

Caveat: many earlier fits were degenerate empty-window matches. Require a non-zero template population and an exact 0 mismatch, otherwise you will accept a candidate that matches nothing.

Implementation note: PIL/FreeType rounds each glyph's pen position to an integer. The font advance at size 16 for this mono face is advance = 9.640625. Per-glyph bitmaps must be pasted at round(x0 + k * advance), not at a floating point pen position, to reproduce PIL's layout exactly.

5. Decoding the flag with a beam search

Once the renderer is known, recover the text left-to-right. For each candidate prefix we need a cheap, exact consistency test.

• Local decoding predicate (light cone). For a prefix of length k, only columns < x0 + advance(k) - N are determined. Any candidate whose evolved prefix mismatches the screenshot inside that region is impossible.
• Incremental local evolution (exact). Appending one glyph only changes the initial grid inside that glyph's own columns, and after N steps the effect is confined to a window of ±N columns around it. So we re-simulate only that window instead of the whole 382x36 grid. This is an exact optimisation (the window is chosen with N cells of margin), not an approximation.
• Beam search. Keep the best K prefixes (beam width ~300-800) ranked by full-grid Hamming distance to the screenshot, expanding each by every character in the alphabet. Prune any expansion whose determined-region mismatch is not exactly 0. The search terminates when a candidate ending in } reaches a total score of 0 (full-grid match).

The alphabet is the usual flag character set (a-z A-Z 0-9 _ { } - ! ? plus a few symbols). The beam converges quickly: the prefix "FortID{" is known, and each subsequent position is pinned by the exact determined-region constraint. The flag decodes to a phrase about real life having no rewind button.

Solution

Full end-to-end solver (grid extraction → renderer identification → beam decode → verification):

#!/usr/bin/env python3
import numpy as np
from PIL import Image, ImageDraw, ImageFont

BASE = "."
SHOT = f"{BASE}/screenshot.png"
TTF  = f"{BASE}/dejavu237/dejavu-fonts-ttf-2.37/ttf/DejaVuSansMono-Bold.ttf"

# ---- 1. Extract the Life grid from the screenshot --------------------------
im = np.asarray(Image.open(SHOT).convert("RGB"))
live = im.mean(2) > 100                      # (204,204,204) cells are bright
G = live[0::8, 7::8].astype(np.int32)        # 6x6 blocks on 8px pitch, origin (7,0)
H, W = G.shape
print("grid", G.shape, "live", int(G.sum()))  # -> (36, 382) 909

# ---- 2. Conway's Game of Life (B3/S23), dead borders -----------------------
def step(g):
    p = np.pad(g, 1)
    n = (p[0:-2,0:-2] + p[0:-2,1:-1] + p[0:-2,2:] +
         p[1:-1,0:-2]                + p[1:-1,2:] +
         p[2:,0:-2]  + p[2:,1:-1]   + p[2:,2:])
    return ((n == 3) | ((g == 1) & (n == 2))).astype(np.int32)

# ---- 3. Known renderer parameters (found by light-cone brute force) --------
FONT  = ImageFont.truetype(TTF, 16)
SIZE  = 16
X0, Y0 = 7, 9
N      = 18
ADV    = 9.640625                            # font.getlength('a') at size 16 mono

# per-glyph bitmaps (threshold >= 128 == 50% intensity)
def glyph_pixels(c):
    img = Image.new("L", (SIZE*4, SIZE*4), 0)
    ImageDraw.Draw(img).text((0, 0), c, fill=255, font=FONT)
    ys, xs = np.nonzero(np.asarray(img) >= 128)
    return ys, xs

def paste(text):
    g = np.zeros((H, W), np.int32)
    for k, c in enumerate(text):
        ys, xs = glyph_pixels(c)
        yy, xx = ys + Y0, xs + int(round(X0 + k * ADV))
        m = (yy >= 0) & (yy < H) & (xx >= 0) & (xx < W)
        g[yy[m], xx[m]] = 1
    return g

def evolve(text):
    g = paste(text)
    for _ in range(N):
        g = step(g)
    return g

# ---- 4. Beam search over flag characters -----------------------------------
ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_{}-!?"

def full_mismatch(E):
    return int(np.abs(E - G).sum())

def determined_cols(text):
    adv = FONT.getlength(text)
    return int(X0 + adv - N)                 # columns < this are fully determined

def det_mismatch(E, text):
    d = determined_cols(text)
    if d <= 0:
        return 10**9
    return int(np.abs(E[:, :d] - G[:, :d]).sum())

start = "FortID{"
beam = [(full_mismatch(evolve(start)), start)]
K = 600
MAXLEN = 60

for _ in range(len(start), MAXLEN):
    cand = []
    for score, text in beam:
        for c in ALPHABET:
            new = text + c
            E = evolve(new)                  # (in a full impl: incremental window)
            if det_mismatch(E, new) != 0:
                continue
            cand.append((full_mismatch(E), new))
            if len(cand) >= 20*K:
                break
    if not cand:
        break
    cand.sort(key=lambda t: t[0])
    seen, beam = set(), []
    for score, text in cand:
        if text in seen:
            continue
        seen.add(text); beam.append((score, text))
        if len(beam) >= K:
            break
    if beam[0][0] == 0 and beam[0][1].endswith("}"):
        print("FLAG (redacted):", beam[0][1][:6] + "..." + beam[0][1][-1])
        break

# ---- 5. Verification -------------------------------------------------------
# evolve(start + decoded_flag) reproduces G with difference 0 and pop 909

Performance note

Re-evolving the whole grid for every candidate is affordable at first but grows expensive. The practical solver uses incremental local evolution: appending one glyph only mutates the initial grid in that glyph's columns, so after N steps only a ±N-column window changes. Recomputing just that window (with an N-cell margin) gives an exact result and cuts the per-candidate cost by roughly two orders of magnitude, letting a beam width of several hundred run comfortably. The reference implementation used this incremental variant (beam.py).

Key Indicators

Use this technique when:

• The image is a uniform grid of light blocks on a dark background at a fixed pixel pitch — an immediate sign of a binary cellular-automaton state.
• The texture contains still-lifes and gliders (blocks, beehives, blinkers, diagonal movers) — Conway's Game of Life, B3/S23.
• The wording mentions "play", "live cell", "rewind", "generations", "future" — a forward-evolved automaton you must invert.
• The challenge names a specific font family/version and an integer pixel size with a 50% intensity threshold — the initial state is a reproducible font rasterization.
• The evolved state is only partially recoverable per character — exploit the light cone (columns < x0 + advance(k) - N are determined) to constrain a left-to-right beam search with an exact incremental-evolution predicate.

Takeaways

• "Reverse a cellular automaton" is often not solved by generic SAT inversion (intractable at 382x36) but by recovering the generator parameters and then decoding the source text greedily/with a beam search under an exact local consistency constraint.
• The light-cone bound is the enabling idea: it turns an under-determined CA inversion into a per-character constrained search.
• Match the rasterizer exactly (integer pen rounding, 50% threshold, correct TTF) — a single pixel of layout drift makes the determined-region test fail.