Cubism — fortid2026

Description

Cubism Gallery

          ███
      ███ ███ ███
  ███ ███ ███ ███ ███
      ███ ███ ███
          ███

A painting is more than the sum of its blocks.

Welcome, artist. Submit your cubist painting below. The curator will begin after the final row.

English summary: a TLS-wrapped TCP service (ncat --ssl <host> 1337) reads exactly SIDE_LENGTH * SIDE_LENGTH = 441 lines via sys.stdin.buffer.readline(21 + 2), concatenates them, and pipes the result to a bundled ./checker. If the checker exits 0, the service prints the FortID{...} flag; otherwise it rejects the "painting". The goal is to craft a 441-line "cubist painting" that makes the stripped checker happy.

Analysis

The wrapper (server.py)

• painting = b"".join(sys.stdin.buffer.readline(23) for _ in range(441)).
• subprocess.run(["./checker"], input=painting, env={}, timeout=5), return code 0 ⇒ flag.

So the entire problem is inside checker: a stripped x86-64 PIE ELF that statically bundles the quirc QR-decoding library.

Reversing the checker

1. It reads 441 lines, each exactly 21 characters of # (bit 1) or . (bit 0), and interprets them as a 21 x 21 x 21 binary cube C[a][b][c]:

   line index L in [0,440]  ->  a = L // 21 , b = L % 21
   character position c in the line -> C[a][b][c]
   

2. Hard voxel gate: the total number of # across all 441 lines must be <= 244 (cmp rbx, 0xf4 ; ja reject at 0x1172).

3. It builds 6 QR module grids = the six orthogonal OR-projections of the cube, renders each to a 348x348 image (background white 0xff, 12-px modules, 48-px quiet-zone border, # = black 0x00), feeds each to quirc_decode, and then snprintf("%s %s %s %s %s %s", ...) the six decoded payloads.

4. It strcmps the resulting string against "SIMON SAYS GIVE ME THE FLAG". Equal ⇒ exit(0) ⇒ flag.

The six projections and their expected words (with N = 21):

axis	grid	word
a (OR over a)	S_a[b][c] = OR_a C	SIMON
a, horizontally mirrored	S_a[b][20-c]	SAYS
b (OR over b)	S_b[a][c] = OR_b C	GIVE
b, mirrored	S_b[a][20-c]	ME
c (OR over c)	S_c[a][b] = OR_c C	THE
c, mirrored	S_c[a][20-b]	FLAG

The core difficulty

Opposite faces of the cube share the same OR-shadow and differ only by a horizontal mirror:

• S_a decodes SIMON directly and SAYS when horizontally mirrored.
• S_b decodes GIVE directly and ME when mirrored.
• S_c decodes THE directly and FLAG when mirrored.

So we need three 21x21 images, each a valid QR Version-1 code that decodes to word X in the normal orientation and to word Y when read mirrored by quirc. Additionally those three images must be simultaneously realizable as the three axis-shadows of one 21^3 cube, using at most 244 voxels.

Solution

Step 1 — quirc reads the horizontal mirror as the transpose

A naive horizontal mirror of a valid QR makes quirc report count=1 but ECC failure (it does not auto-handle mirrored codes). The key observation is geometric: for a clean, axis-aligned module grid, the horizontal mirror of S is what quirc sees when it looks at transpose(S) under the same finder-pattern orientation. Empirically verified against the real bundled quirc:

quirc.decode( hflip(S) )  ==  quirc.decode( transpose(S) )

Therefore each shadow S must be a transpose-dual QR: a single 21x21 module layout where S decodes message A and transpose(S) decodes message B. (This is the "double-sided QR" construction idea of Joris van Rantwijk.)

Step 2 — construct three transpose-dual V1 QRs

Each dual QR is built with:

• Mask 3 (!((i+j) % 3)), which is symmetric under transposition, so the same mask applies to both orientations.
• A palindromic format word so the format-information modules read identically in both orientations.
• Message A codewords placed in the normal zig-zag read order, message B codewords placed in the transposed zig-zag read order.
• The remaining (free) codeword modules become GF(2) variables. We require the Reed–Solomon syndromes to be zero in both orientations, which is a linear system over GF(2) (QR uses RS over GF(256) with primitive polynomial 0x11d). The system is solved by Gaussian elimination over GF(2); a small chosen set of "sacrificed" (correctable) codewords per orientation (EA, EB, <= 3 each) absorbs the overlap between the two messages within the ECC capacity.

# Reed-Solomon syndrome (matches quirc's block_syndromes), GF(256) prim poly 0x11d
EXP = [0]*512; LOG = [0]*256
x = 1
for i in range(255):
    EXP[i] = x; LOG[x] = i
    x <<= 1
    if x & 0x100: x ^= 0x11d
for i in range(255, 512): EXP[i] = EXP[i-255]

def quirc_syndromes(data, bs, npar):
    s = [0]*npar
    for i in range(npar):
        acc = 0
        for j in range(bs):
            c = data[bs-j-1]
            if c:
                acc ^= EXP[(LOG[c] + i*j) % 255]
        s[i] = acc
    return s

# mask 3, symmetric under transpose
def mask3(i, j):
    return 1 if ((i + j) % 3 == 0) else 0

# The 208 data/ecc cell coordinates in quirc's exact read_data() order are
# precomputed in qr_maps.data_read_order(). Bit k -> codeword k//8, bit k%8 (MSB first).

The three resulting shadows were saved as S_a.txt (SIMON/SAYS), S_b.txt (GIVE/ME) and S_c.txt (THE/FLAG), and each was validated against the real quirc in both orientations.

Step 3 — realize the three shadows as one cube (exact 3-projection problem)

A voxel (a,b,c) simultaneously lights module:

S_a[b][c] ,  S_b[a][c] ,  S_c[a][b]

A voxel may only be placed where all three target grids are dark; every dark module of every shadow must be covered by at least one voxel. This is an exact 3-orthogonal-projection / min-vertex-cover problem. A per-layer lower bound (matching argument; ~226 voxels) was computed, and several heuristics (cover3/cover4/exact_mincover, plus simulated annealing over the GF(2) null-space to choose the shadow representative that minimizes the cover) produced a concrete cover within budget. The final cube used 243 voxels (<= 244).

# Realize: allowed voxels then exact cover
N = 21
allowed = [(a,b,c) for a in range(N) for b in range(N) for c in range(N)
           if Sa[b][c] and Sb[a][c] and Sc[a][b]]
# ... solve min-cover over `allowed` (networkx matching / exact_mincover) ...
# Write cube.txt: C[a][b][c] = '#' iff (a,b,c) in cover
lines = []
for a in range(N):
    for b in range(N):
        lines.append(''.join('#' if (a,b,c) in cover else '.' for c in range(N)))
open("cube.txt", "w").write("\n".join(lines) + "\n")   # 441 lines x 21 chars, 243 '#'

Step 4 — verify and submit

# verify.py: recompute the 3 OR-projections of cube.txt, confirm equality with
# S_a/S_b/S_c, count voxels (<=244), and decode each shadow + transpose with the
# faithful quirc port.
# All 6 decodes correct, 243 voxels -> PASS.

The submission is cube.txt: 441 lines, each exactly 21 characters, made of # and ., with 243 #. Piping it to the checker yields Correct! and the flag. Verified locally in Docker against the real checker binary and on the live remote (openssl s_client -quiet -connect HOST:1337 < cube.txt).

Shape sample (first lines of cube.txt; sparse because most shadow modules are lit on a single layer):
..#..................
........#..#.........
#....................
..#..............#...
...#.......#.........
....................#
...

Recovered flag format: FortID{REDACTED}.

Key Indicators

Use this technique when:

• A stripped PIE binary bundles quirc (or any QR decoder) and strcmps decoded strings against constants — the challenge is on the encoder side.
• Input is a fixed-size line grid (readline(N+2) x N*N lines) of #/. forming a 3D bit-cube, and the checker builds OR-projections along the three axes.
• A hard voxel/module budget gate appears (cmp ..., imm ; ja reject), forcing a near-optimal cover rather than a naive one-shadow-per-layer layout.
• Opposite faces share one shadow and differ only by a mirror ⇒ you need transpose-dual QR codes (mask 3, palindromic format, RS syndromes = 0 in both orientations).
• Three independent 2D targets must be realized as the three orthogonal shadows of a single 3D object ⇒ exact 3-projection / min-vertex-cover problem.