Spill the Tea — fortid2026

Description

The provided photograph (flag.jpg) shows loose tea covering a QR code labeled “SCAN FOR FLAG.” Recover the encoded message without assuming that dark tea leaves are QR ink.

Analysis

The finder and alignment patterns establish a version-6, 41×41-module QR grid. Perspective rectification makes each module measurable. Traversing the non-function modules in QR zigzag order, unmasking with pattern 3 ((row + column) % 3 == 0), and reading the header gives byte mode and a 70-byte payload. Ordinary QR scanners and whole-byte Reed–Solomon erasure decoding fail because too many codewords contain obscured modules; individual visible bits remain useful.

Version 6 with error correction Q has four Reed–Solomon blocks, each with 19 data bytes and 24 parity bytes. The first 76 interleaved codewords are data; the remaining 96 are parity. In particular, the parity segment begins at stream index 76, not 60. Level H was an attractive but impossible earlier assumption: its four blocks hold only 60 data bytes total, while 70 byte-mode characters plus the 12-bit mode/length header require 572 bits, exceeding H's 480 data bits. The Q-level data region holds 608 bits.

For a bright module (median grayscale >175), trust white; for dark modules, trust black only when the inner patch is nearly uniform (standard deviation below approximately 6–9 and absolute median red–blue difference below 10). Ignore everything else. Reed–Solomon encoding is linear over GF(2): encode each of the 152 single-bit data vectors through RSCodec(24) to obtain a parity-bit coefficient matrix. A trusted image bit then becomes a linear equation in its block's 152 data bits, even if the rest of its codeword is obscured. Add the byte-mode header, organizer-provided flag-format prefix, printable ASCII high bits, and closing brace at bit offset 12 + 8*69. Offsets measured from the start of the data bytes instead of from the 12-bit header erroneously constrain payload bytes and can even overwrite the header.

With conservative thresholds, blocks 0 and 1 have rank 152; blocks 2 and 3 each have rank 140, leaving 12 free bits each. Enumerate their 4096 possibilities independently rather than taking their Cartesian product immediately. The expected alphanumeric/underscore/brace alphabet leaves one choice for block 2 and seven for block 3. The observed zero-filled terminator, an additional zero byte, and alternating QR pad bytes identify the correctly framed candidate; do not assume that the extra zero byte is required by the QR standard. Regenerating all parity bytes and unmasking the complete symbol checks its agreement with the photograph. The selected symbol disagrees with 0/339 clean white and 0/158 clean black data/parity modules, and with 31 modules of a broader 676-module confidence set; competing printable candidates disagree with at least 40 in that broader set. The recovered text is intentionally omitted here (FortID{REDACTED}).

Solution

Install opencv-python, numpy, and reedsolo; use the original image and the four-corner homography from perspective calibration (homog3.npy). Run the following from the task directory. It performs complete QR traversal, per-bit reconstruction, candidate filtering, padding verification, and full-symbol image comparison. It reports only redacted recovery metrics, never the message itself.

#!/usr/bin/env python3
import itertools
import string

import cv2
import numpy as np
from reedsolo import RSCodec

N, P, DATA, EC = 41, 24, 19, 24
image = cv2.imread('flag.jpg')
corners = np.load('homog3.npy').astype(np.float32).reshape(4, 2)
transform = cv2.getPerspectiveTransform(
    corners, np.float32([[0, 0], [N*P, 0], [0, N*P], [N*P, N*P]]))
warped = cv2.warpPerspective(image, transform, (N*P, N*P))
med = np.zeros((N, N)); deviation = np.zeros((N, N))
red_blue = np.zeros((N, N)); observed = np.zeros((N, N), dtype=np.int8)
for row in range(N):
    for col in range(N):
        patch = warped[row*P+5:(row+1)*P-5, col*P+5:(col+1)*P-5].astype(float)
        gray = cv2.cvtColor(patch.astype(np.uint8), cv2.COLOR_BGR2GRAY)
        med[row, col] = np.median(gray)
        deviation[row, col] = np.std(gray)
        red_blue[row, col] = np.median(patch[:, :, 2] - patch[:, :, 0])
        observed[row, col] = med[row, col] < 110

function = np.zeros((N, N), dtype=bool)
function[6, :] = True; function[:, 6] = True
for row, col in [(0, 0), (0, 33), (33, 0)]:
    function[row:row+9, col:col+9] = True
function[8, :9] = True; function[:9, 8] = True
function[8, 33:] = True; function[34:, 8] = True
function[32:37, 32:37] = True; function[33, 8] = True
positions = []
col, upwards = 40, True
while col > 0:
    if col == 6:
        col -= 1
    for row in (range(40, -1, -1) if upwards else range(41)):
        for c in (col, col-1):
            if not function[row, c]:
                positions.append((row, c))
    upwards = not upwards
    col -= 2
assert len(positions) == 1383  # 172 complete codewords and 7 remainder bits

rs = RSCodec(EC)
parity_basis = []
for bit in range(DATA*8):
    unit = bytearray(DATA)
    unit[bit//8] = 1 << (7-bit%8)
    parity_basis.append(rs.encode(unit)[DATA:])

def parity_row(bit):
    byte, offset = divmod(bit, 8)
    return sum(1 << i for i, code in enumerate(parity_basis)
               if (code[byte] >> (7-offset)) & 1)

def eliminate(rows):
    pivots = {}
    for vector, rhs in rows:
        while vector:
            lead = vector.bit_length()-1
            if lead not in pivots:
                pivots[lead] = (vector, rhs)
                break
            prev, value = pivots[lead]
            vector ^= prev; rhs ^= value
        else:
            if rhs:
                raise ValueError('inconsistent observations: tighten image threshold')
    return pivots

# Format-only known prefix; never embed any recovered message bytes.
header = '0100' + format(70, '08b') + ''.join(format(x, '08b') for x in b'FortID{')
known = {i: int(bit) for i, bit in enumerate(header)}
for char in range(70):
    known[12 + 8*char] = 0  # ASCII top bit
for bit in range(8):
    known[12 + 8*69 + bit] = (ord('}') >> (7-bit)) & 1

def options(block, threshold):
    trusted = (med > 175) | ((med < 80) & (deviation < threshold) &
                               (np.abs(red_blue) < 10))
    equations = []
    for stream_byte in range(172):
        if stream_byte % 4 != block:
            continue
        index = stream_byte//4 if stream_byte < 76 else (stream_byte-76)//4
        for bit in range(8):
            row, col = positions[8*stream_byte+bit]
            if not trusted[row, col]:
                continue
            value = int(observed[row, col]) ^ int((row+col)%3 == 0)
            coeff = (1 << (8*index+bit)) if stream_byte < 76 else parity_row(8*index+bit)
            equations.append((coeff, value))
    for bit, value in known.items():
        byte, offset = divmod(bit, 8)
        if byte//DATA == block:
            equations.append((1 << (8*(byte%DATA)+offset), value))
    pivots = eliminate(equations)
    free = sorted(set(range(DATA*8))-pivots.keys())
    print('block', block, 'rank', len(pivots), 'free bits', len(free))
    results = []
    for assignment in itertools.product((0, 1), repeat=len(free)):
        bits = [0]*152
        for i, value in zip(free, assignment):
            bits[i] = value
        for lead in sorted(pivots):
            coeff, rhs = pivots[lead]
            for i in range(lead):
                if (coeff >> i) & 1:
                    rhs ^= bits[i]
            bits[lead] = rhs
        results.append(bytes(sum(bits[8*j+k] << (7-k) for k in range(8))
                             for j in range(DATA)))
    return results

blocks = [options(0, 6), options(1, 9), options(2, 7), options(3, 6)]
alphabet = set((string.ascii_letters + string.digits + '_{}').encode())

def message(data):
    bits = ''.join(format(byte, '08b') for block in data for byte in block)
    return bytes(int(bits[12+8*j:20+8*j], 2) for j in range(70))

def score(data):
    encoded = [rs.encode(block) for block in data]
    stream = (bytes(encoded[b][j] for j in range(DATA) for b in range(4)) +
              bytes(encoded[b][DATA+j] for j in range(EC) for b in range(4)))
    white = ink = extended = 0
    for index in range(172*8):
        row, col = positions[index]
        qr_bit = ((stream[index//8] >> (7-index%8)) & 1) ^ int((row+col)%3 == 0)
        if med[row, col] > 175:
            white += qr_bit != 0
        if med[row, col] < 80 and deviation[row, col] < 6 and abs(red_blue[row, col]) < 10:
            ink += qr_bit != 1
        if (med[row, col] > 155 or (med[row, col] < 80 and
            deviation[row, col] < 12 and abs(red_blue[row, col]) < 10)):
            extended += qr_bit != observed[row, col]
    return white, ink, extended

def framed(data):
    # 70 byte-mode characters use 12+560 bits; four zero terminator bits
    # fill byte 71. The observed symbol additionally uses one zero byte,
    # then alternating QR pad bytes; the extra zero byte is not mandatory.
    raw = b''.join(data)
    return raw[71] & 15 == 0 and raw[72:76] == bytes((0, 0xec, 0x11, 0xec))

survivors = []
for c in blocks[2]:
    if not all(x in alphabet for x in message((blocks[0][0], blocks[1][0], c, blocks[3][0]))[36:54]):
        continue
    for d in blocks[3]:
        data = (blocks[0][0], blocks[1][0], c, d)
        text = message(data)
        if all(x in alphabet for x in text) and text.startswith(b'FortID{') and text.endswith(b'}'):
            survivors.append((data, score(data)))
print('printable candidates:', len(survivors))
valid = [(data, errors) for data, errors in survivors if framed(data)]
assert len(valid) == 1, 'expected one candidate with observed QR padding'
data, errors = valid[0]
assert errors[:2] == (0, 0), 'candidate conflicts with high-confidence modules'
print('Recovered FortID{REDACTED}; module disagreements:', errors)

Key Indicators

• A QR symbol with a large opaque occlusion but many intact individual modules calls for bit-level parity equations, not all-or-nothing codeword erasures.
• Version 6, mask 3, byte mode, and a 70-byte header narrow the viable block layout to Q rather than H.
• Clean white interiors and low-variance neutral black interiors provide reliable equations even where surrounding tea makes whole codewords undecodable.
• The observed terminator/pad pattern and full re-encoding distinguish plausible-looking text from the actual symbol.