Cubism

Full solution below. Spoilers ahead.

Task description

Cubism was one of the most influential visual art styles of the early twentieth century.

We’ve built a tool that checks whether a supplied cubist painting is a true work of art. Prove your worth and earn your flag!

The handout is checker (a stripped x86-64 PIE ELF) and server.py. The flag lived on a remote service that ran the checker.

The server only checks an exit code

server.py reads 441 lines of up to 21 characters from stdin, feeds them to ./checker, and prints the flag only if the checker exits 0:

SIDE_LENGTH = 21
painting = b"".join(
    sys.stdin.buffer.readline(SIDE_LENGTH + 2)
    for _ in range(SIDE_LENGTH * SIDE_LENGTH)   # 21*21 = 441 lines
)
result = subprocess.run([CHECKER], input=painting, ...)
if result.returncode != 0:
    reject()
print(f"Enjoy your flag: {FLAG}")

The flag string is never passed to the checker. The whole task is to craft a 441-line grid of # and . that makes checker exit 0. The server’s banner reads “A painting is more than the sum of its blocks,” which turns out to be a literal hint: the blocks are slices of a cube.

It is a QR decoder in disguise

The binary is stripped, so I worked from static disassembly (objdump -d -Mintel) and from gdb, both run under WSL against the Linux ELF. The constants below (the # budget, the projection jump table, the 348-pixel render buffer) come from that disassembly.

The leftover strings in .rodata settle the first question immediately. Parsing the ELF and pulling printable runs out of the rodata region:

$ python -I strings.py checker        # tiny custom extractor, gdb-free
0x600b '%s %s %s %s %s %s'
0x601d 'SIMON SAYS GIVE ME THE FLAG'
0x6039 'Correct!'
0x6088 '1.0'
0x609a 'Success'
0x60a2 'Invalid grid size'
0x60b4 'Invalid version'
0x60c4 'Format data ECC failure'
0x60dc 'Unknown data type'
0x60ee 'Data overflow'
0x60fc 'Data underflow'
0x610b 'quirc/lib/identify.c'
0x6120 'row[x] == from'
0x6140 'q->pixels[y0 * q->w + x0] == from'
0x61b0 'flood_fill_line'
0x61c0 'flood_fill_seed'

That block is the fingerprint of quirc, a small C QR-code decoding library. The run from Success through Data underflow is quirc’s own quirc_strerror table verbatim, 1.0 is its version string, quirc/lib/identify.c is a source path baked into an assertion, and flood_fill_line / flood_fill_seed / q->pixels[y0 * q->w + x0] == from are assertion messages from quirc’s finder-pattern flood fill. The imported sqrt (the only interesting libc math import) is quirc’s perspective-correction maths. So the checker statically links quirc and feeds it images. This part I re-verified this session, straight from the handed-out binary.

The target string is also right there: %s %s %s %s %s %s is a six-slot join format, and the expected result is SIMON SAYS GIVE ME THE FLAG, which is six whitespace-separated words.

The input is a 21x21x21 cube with a budget

The parse loop reads 21 blocks of 21 rows of 21 columns, 9261 cells in all (21**3 = 9261). Each cell must be # (stored as 1) or . (stored as 0); anything else is rejected. Line n = i*21 + j, column k, is voxel C[i][j][k], so the first 21 lines of the file are the i = 0 slice, the next 21 are i = 1, and so on. A voxel is one cell of a 3D grid, the 3D equivalent of a pixel.

After each row the checker enforces a hard cap on the total number of filled cells. From the original disassembly:

cmp rbx, 0xf4      ; rbx = running count of '#'
ja  reject         ; reject once the total number of '#' exceeds 244

So at most 244 cells over the whole cube may be #. The handed-out solution.txt uses 242, which I checked against the cap:

$ wc -l solution.txt ; grep -o '#' solution.txt | wc -l
441 solution.txt
242
$ awk '{print length}' solution.txt | sort -u
21

441 lines, every line exactly 21 characters, 242 # out of 9261 cells, comfortably under the 244 cap. That 244 budget is the real difficulty of the task: the obvious cube that produces the right silhouettes is far too dense, so most of the work goes into making a sparse cube.

Six projections must decode to six words

After parsing, an outer loop runs six times. Each pass projects the cube down to a 21x21 image through a per-state jump table, renders every module as a 12x12 block into a 348x348 white image, and runs it through quirc_identify, quirc_extract and quirc_decode. The 348 is a quiet zone at work: a QR code needs a clear margin around it to be found, and 29 * 12 = 348 is the 21 modules plus a 4-module border on each side, scaled up by 12. If any of the six projections fails to decode, the checker rejects. After all six succeed it joins the decoded words with %s %s %s %s %s %s and compares the result against SIMON SAYS GIVE ME THE FLAG.

Reading the jump table during the original solve, and confirming it by dumping the rendered image out of gdb, gave the six projections:

state	output pixel	word
0	out[j][k] = OR_i C[i][j][k]	SIMON
1	out[j][20-k] (mirror of state 0)	SAYS
2	out[i][k] = OR_j C[i][j][k]	GIVE
3	out[i][20-k] (mirror of state 2)	ME
4	out[i][j] = OR_k C[i][j][k]	THE
5	out[i][20-j] (mirror of state 4)	FLAG

States 0, 2 and 4 are three silhouette projections, one per axis: each output pixel is the OR of the cube along the missing axis, so a module is black if any voxel in that line of sight is filled. That is exactly the shadow a solid shape casts. States 1, 3 and 5 re-read each silhouette mirrored left to right, like looking at the same transparent cube face from behind. A version-1 QR code is 21x21 modules, which is why the grid is that size, and why the 27-character phrase (which would need a larger version-2 code) is split into six short words, one per face.

The three silhouettes really are QR codes

I can show this directly from the real solution.txt, no decoder and no live service needed. Collapsing the cube along each axis with the OR rule above reproduces the three images the checker renders:

$ python -I project.py solution.txt
total voxels: 242

=== P = OR over i  (state 0, SIMON) ===
#######.#####.#######
#.....#.####..#.....#
#.###.#...#.#.#.###.#
#.###.#..#....#.###.#
#.###.#.##.##.#.###.#
#.....#.#.##..#.....#
#######.#.#.#.#######
........#.#..........
###..##.#########..##
.#...#.##...#.####..#
.###.###..#..#.#.....
#.#....##....#...####
.#.#.##....#..#..#...
........###..#...##..
#######..#.#.###.##..
#.....#.#.....#...#.#
#.###.#..#.........##
#.###.#..###.###..#..
#.###.#.#.......#####
#.....#.####.##.##..#
#######.#..#.#.###.##

=== Q = OR over j  (state 2, GIVE) ===
#######.#.##..#######
#.....#.#..##.#.....#
#.###.#..###..#.###.#
#.###.#....#..#.###.#
#.###.#.#.....#.###.#
#.....#.#.#.#.#.....#
#######.#.#.#.#######
........#............
###..##.#....####..##
##.#.#....###.....#.#
#...#.#.#.##.#.....##
#.#.##.###...#.##...#
#####.#...###..#.##..
........##....##....#
#######...#..###.#.##
#.....#.#.#.#.#.#...#
#.###.#..#.....##.###
#.###.#...#..#####...
#.###.#.##.##....#.##
#.....#.###....###..#
#######.####....##.##

(R = OR over k, state 4, THE, is the third, same shape)

P finder TL,TR,BL: (True, True, True)
Q finder TL,TR,BL: (True, True, True)
R finder TL,TR,BL: (True, True, True)

All three collapse to a clean 21x21 QR code: the 7x7 finder patterns (the big corner squares a scanner locks onto) sit in the top-left, top-right and bottom-left corners of each image, with the alternating timing rows between them. The three silhouettes carry about 220 set modules each, but their union in 3D is only the 242 filled voxels. So the real solution is exactly the mechanism the disassembly described: three 21x21 QR codes, one read down each axis of the cube.

Quirc reads a mirrored code as its transpose

Each image therefore has to do two jobs at once: quirc must read M as one word and read the mirror of M as the next word. During the solve I dumped quirc’s internal sampling grid in gdb and found the fact the whole construction hangs on:

quirc reads the horizontal mirror of an image as its transpose.

A mirrored QR code has its three finder patterns at the top-left, top-right and bottom-right corners instead of the usual top-left, top-right, bottom-left. Quirc reorients the code using the right-angle corner of the finder layout, and for a left-right mirror that reorientation is a 90-degree rotation, which composed with the mirror equals a transpose (rows and columns swapped). So feeding quirc the mirror of M makes it sample transpose(M).

Each projection then has to satisfy quirc(M) = wordA and quirc(transpose(M)) = wordB, for the pairs (SIMON, SAYS), (GIVE, ME) and (THE, FLAG). An ordinary QR code’s transpose does not decode: for every mask and error-correction level I tried, quirc returned error 4, “Format data ECC failure.” That is a data error, not a format one, which means quirc still read a valid version-1 grid and a valid format block from the transpose, and only the payload bits were wrong. That is the opening: the grid is structurally fine, so if I can also fix the payload bits of the transpose, a single image decodes two ways.

A controllable QR encoder and GF(2) linear algebra

I wrote a QR version-1 encoder with Reed-Solomon error correction over GF(256), the standard mask patterns, and a data-module placement order that I derived empirically from the segno library (and validated by reproducing segno’s matrices bit for bit for every length-17 message). The encoder deliberately exposes the free padding bits that follow the message and its terminator. Those bits pad the code out to capacity, and quirc ignores them on decode, so they are free to choose.

Gotcha: segno quietly raises the ECC level

segno defaults to boost_error=True, which silently upgrades the error-correction level for short messages because the spare capacity is there. That changes the format bits and the data layout, so every matrix comparison and all the format work has to pass boost_error=False to keep the level fixed. I lost time to encoders that disagreed before I spotted this.

QR encoding is affine over GF(2) (ordinary arithmetic mod 2) in those free padding bits: flipping a padding bit flips a fixed, linear set of module values after Reed-Solomon and masking. For a pair (wordA, wordB) with chosen levels and masks, I set up a linear system that forces only the data cells of transpose(M) to match a valid encoding of wordB. Quirc corrects the format bits with BCH error correction and skips the single asymmetric dark module, so those cells can be left unconstrained:

transpose( encode(wordA, pA) ) == encode(wordB, pB)   on all data cells

Solving that system over GF(2) gives the free padding bits (pA, pB) that make both readings land. I confirmed each candidate with the real binary as an oracle during the solve: extrude the image onto slice i = 0, then read states 0 and 1 under gdb. For all three pairs the combination level L, mask 1 for the forward read and mask 4 for the transpose read works, giving three images: P (SIMON / SAYS), Q (GIVE / ME) and R (THE / FLAG).

One cube for three images

The three projections share a single cube, so P (the silhouette over i), Q (over j) and R (over k) have to be mutually consistent: there must exist a cube whose three shadows are exactly those images. The densest such cube is C[i][j][k] = P[j][k] AND Q[i][k] AND R[i][j], which fills a voxel whenever all three silhouettes allow it. The three images are consistent precisely when that cube projects back to P, Q and R with nothing left over.

Each solved image sits in a large GF(2) null space (dimensions 21, 37 and 31 for the three pairs), meaning there are many distinct encodings that still decode to the same two words. A local search over those null spaces found a triple that is mutually consistent while keeping the number of black modules low, which matters for the next step.

Fitting the 244-cell budget with an ILP

The densest consistent cube P AND Q AND R holds roughly 1800 voxels, and the checker caps the total at 244. I need a minimal set of voxels that still projects exactly to P, Q and R. That is a three-dimensional set cover: each filled voxel (i,j,k) covers one module of P (at (j,k)), one of Q (at (i,k)) and one of R (at (i,j)), and I want the fewest voxels that cover every black module of all three silhouettes.

I solved it optimally with an ILP (integer linear program, an optimisation where the variables are forced to be whole numbers) using PuLP with the CBC solver: a 0/1 variable per allowed voxel {(i,j,k) : P[j][k] AND Q[i][k] AND R[i][j]}, one covering constraint per black module of each silhouette, and the objective to minimise the voxel count. The optimum was 242 voxels, which fits under 244 with the projections exact. The per-slice spread of those 242 is uneven, from 2 cells in one slice to 18 in another, which is what a cover minimiser produces rather than anything hand-balanced.

The painting

buildfinal.py writes the 441-line painting, 21 characters per line, with 242 #. The handed-out solution.txt is that file, and the counts above (441 lines, 242 filled cells, every line 21 wide) are what I verified from it. The first 21 lines are the i = 0 slice:

.#...................
...........#.........
...#.................
..#..................
......#.........#....
........#............
..................#..
.....................
...............#.....
.....................
.....................
#....................
.....................
.....................
.................#...
....................#
....#................
..........#..........
...................#.
..............#......
.....#...............

A single slice looks like noise, which is the point: the structure only appears once the cube is collapsed along an axis into one of the QR codes shown earlier. The remaining 420 lines are the other 20 slices.

Running server.py locally with this file on stdin and a placeholder in the FLAG environment variable prints The curator smiles. and Correct!, so the checker accepts it. Piping the same file to the live service over TLS during the competition returned the flag, clipped here to its prefix, FortID{Th3_CuB3_15_47....

Notes for next time

Recognising the library before reversing anything by hand turned a scary stripped binary into a much smaller question: how is a known decoder wired up? The .rodata strings named quirc on sight, and I could re-confirm that this session straight from the file. The one fact the whole exploit rests on, that quirc reads a mirror as a transpose, and quirc’s exact module sampling, came from dumping buffers in gdb during the solve rather than from the spec, which was faster and left no room to guess wrong. After that, each sub-problem had a standard tool: the QR padding freedom was GF(2) linear algebra, the cube from three shadows was a silhouette-consistency question, and the # budget was an ILP set cover.

Why six words and not one

SIMON SAYS GIVE ME THE FLAG is 27 characters, which needs a version-2 (25x25) QR code. That cannot exist inside a 21x21 projection, so the phrase is split into the six whitespace-separated tokens the %s %s %s %s %s %s join expects, each a small version-1 code on one face of the cube. “Simon says, give me the flag” is also the author winking at the player.

Defensive note

Validating untrusted input by round-tripping it through a full C image and QR library inside a checker is risky on a real system: decoders like this have had memory-safety bugs, and here the checker runs attacker-controlled images on every submission. A checker should parse the minimal structure it actually needs rather than invoking a whole decoder on arbitrary input. For a CTF toy it is fine, and it makes for a far more interesting puzzle than a plain string compare.