Human RNG — FortID CTF 2026

Description

"You've heard about LCGs, LFSRs, MTs, Xorshifts, RDRANDs, Lavarands... But, can you crack a Human RNG?"

Handout: encrypt.py, bitstream.txt, ciphertext.png (plus a Google-Drive "human at work" typing video that turned out to be a decoy).

English summary. encrypt.py builds a QR code of the flag, flattens its 41x41 module matrix to 1681 bits, and XORs them with a 1681-bit human-typed keystream; the XOR result is saved as ciphertext.png (black pixel = bit 1). bitstream.txt only exposes the first 1999 keystream bits and then the literal marker <1681-bits-redacted> — the exact keystream used for the ciphertext is hidden. The goal is to recover the flag body.

Analysis

Mechanics (from encrypt.py)

• flag = PREFIX + "{" + body + "}" where PREFIX = "FortID", with len(body) == 44 and re.fullmatch(r"[a-z]+(?:_[a-z]+)+", body) — lowercase English words joined by underscores.
• QR built with qrcode: version=6, error_correction=ERROR_CORRECT_H, box_size=1, border=0, mask_pattern=0 → a 41x41 = 1681-bit matrix, read row-major, dark module = bit 1.
• key = load_keystream(1681) = the last 1681 bits of bitstream.txt, taken after the visible prefix. The prefix and the ciphertext keystream are strictly disjoint slices.
• ct = qr_bits XOR key; ct is written as a 41x41 image scaled to 410x410 (nearest).

Why the hidden tail cannot be predicted

The keystream is human-typed, so it is memoryless but strongly biased toward alternation: measured on the 1999 visible bits, P(flip) ≈ 0.7017, P(0) ≈ 0.4747, run lengths geometric, flip autocorrelation ≈ 0, and Berlekamp-Massey linear complexity ≈ n/2. The hidden suffix is therefore not a deterministic function of the prefix — no LFSR/LCG/MT model fits. About 298 QR modules are structurally fixed (finder/timing/alignment/format), so those keystream bits are "known" in value but are flag-independent: they alone do not disclose the flag.

Decisive idea: maximum-likelihood over the candidate's derived keystream

The keystream is not predictable bit-by-bit, but its statistics are learnable. For any candidate body b, define

key_candidate(b) = ciphertext_bits XOR QR_matrix(PREFIX + "{" + b + "}")

If b is the true body, then key_candidate(b) is the real human keystream, so it should look like the prefix. Model the prefix with an order-1 Markov chain and score the derived keystream with its log-likelihood. The right candidate sits at the top of the landscape; wrong candidates produce a "diffed" (essentially random) stream and score far lower.

This is the only non-circular signal. (Decrypting the ciphertext with the candidate key and re-decoding a QR is circular: the key is built from the very candidate matrix, so the QR always decodes back to it. Do not use it as verification.)

The subtle trap in the candidate space

The flag body is a grammatical sentence with a fixed English lead-in, an 8-character middle slot, and a fixed trailing phrase. Naively enumerating the middle as a single 8-letter word caps at gibberish (obscure dictionary words). The 8-character middle can also be two short words joined by an underscore — exactly the kind of natural phrase the sentence calls for — which the single-word search misses. Enumerating the middle as first_word + "_" + second_word makes the natural phrase the unique maximum, ~40 points above the next candidate and a 1-opt local maximum (no single-character change improves it). Its derived keystream statistics (00/01/10/11 = 258/608/608/206, transition rate 0.7238 vs prefix 0.7017) closely match the human model.

What did not work (brief)

• Predicting the human stream with a bias/PRNG model — it is memoryless; no short generator.
• Extracting the keystream from the extra typing video — a dedicated analysis found no audio, visual, timing, LED, or container channel; keystroke-count detectors gave 989–2284 (never a stable 1681), all ~chance against the known fixed QR bits. The video is decoration.
• The naive circular QR-decode check — always "succeeds" by construction.
• Enumerating only single-word middles — reaches only gibberish local maxima.

Solution

1. Parse ciphertext.png into 1681 bits (sample the centre of each module; black = 1).
2. Fit an order-1 Markov model on the 1999 visible prefix bits of bitstream.txt.
3. Generate candidates from the sentence template, with an 8-character middle that may contain an underscore (two words joined).
4. For each candidate compute key_candidate = ct XOR QR(candidate) and its Markov log-likelihood; keep the maximum.
5. Read the winning body off and submit it wrapped in the flag format FortID{REDACTED}.

#!/usr/bin/env python3
"""Recover the flag from ciphertext.png = QR(flag) XOR (biased, suffix-redacted) human keystream.

Usage: python3 solve.py "<fixed lead-in words>" "<fixed trailing words>"

The body has the shape  <lead_in>_<MID8>_<trailing>, where MID8 is 8 lowercase characters
that may themselves contain one underscore (i.e. two short words joined by '_').
"""
import math, re, sys
import numpy as np
import qrcode
from qrcode.constants import ERROR_CORRECT_H
from PIL import Image

N, VERSION, MASK = 41, 6, 0
PREFIX = "FortID"
LEAD, TAIL = sys.argv[1], sys.argv[2]          # fixed English words of the phrase

# --- 1. ciphertext.png -> 1681 bits, row-major, black pixel == 1 -------------
im = Image.open("ciphertext.png").convert("1")
step = im.size[0] // N                          # 410 // 41 == 10
px = im.load()
CT = np.array([1 if px[x * step + step // 2, y * step + step // 2] == 0 else 0
               for y in range(N) for x in range(N)], dtype=np.int64)

# --- 2. order-1 Markov model fitted on the visible prefix --------------------
raw = open("bitstream.txt").read().strip()
prefix = np.array([int(c) for c in raw[:raw.find("<")] if c in "01"], dtype=np.int64)
LOGP = np.empty((2, 2))                          # LOGP[a, b] = log2 P(next=b | cur=a)
for a in (0, 1):
    row = np.array([np.sum((prefix[:-1] == a) & (prefix[1:] == b)) for b in (0, 1)], float)
    LOGP[a] = np.log2(row / row.sum())

# --- 3. regenerate the QR module matrix for a candidate ----------------------
def qr_bits(flag):
    qr = qrcode.QRCode(version=VERSION, error_correction=ERROR_CORRECT_H,
                       box_size=1, border=0, mask_pattern=MASK)
    qr.add_data(flag)
    qr.make(fit=False)
    return np.array([1 if c else 0 for row in qr.get_matrix() for c in row], dtype=np.int64)

def score(body):
    """Log-likelihood that ct XOR QR-of-candidate is a real human keystream."""
    key = CT ^ qr_bits(PREFIX + "{" + body + "}")
    return LOGP[key[:-1], key[1:]].sum()

# --- 4. enumerate the 8-char middle, INCLUDING two-word (underscore) forms ---
words = {w.strip() for w in open("words_alpha.txt") if re.fullmatch(r"[a-z]+", w.strip())}
by_len = {}
for w in words:
    by_len.setdefault(len(w), set()).add(w)

best = []
for f in words:                                  # first short word of the middle
    if not (1 <= len(f) <= 6):
        continue
    need = 7 - len(f)                            # len(f) + 1 (underscore) + need == 8
    for w in by_len.get(need, ()):               # second short word
        body = f"{LEAD}_{f}_{w}_{TAIL}"
        if len(body) != 44:
            continue
        best.append((score(body), body))

best.sort(reverse=True)
for s, b in best[:10]:
    print(f"{s:9.2f}  {PREFIX}{{{b}}}")          # top line = the flag

Running it prints a single clear winner (a natural two-word middle) by a wide margin, and that body is the flag. The recovered value is intentionally omitted here.

Key Indicators

Use this technique when:

• A stream cipher keystream is human-generated and only a prefix is exposed; look for P(flip) ≈ 0.70 and geometric run lengths (humans avoid repeating symbols), and Berlekamp-Massey linear complexity ≈ n/2 (rules out a short LFSR/LCG/MT).
• The ciphertext is a QR module matrix (or any format whose bits you can regenerate for a candidate plaintext), so derived_key = ciphertext XOR regenerate(candidate).
• A separate, short human-typed keystream exists whose statistics you can model — then maximise the log-likelihood of the derived key over a structured candidate space. This is the non-circular signal; re-decoding the regenerated QR from the derived key is circular.
• The plaintext has a fixed-length structured slot (here 8 chars) that can be filled by either one word or two words joined by an underscore — enumerate both, or you cap at gibberish.
• Beware decoy media (a "human typing" video that carries no usable channel); a clean, memoryless statistical source is the real lead.