A Plaid Puzzle

We have a Puzzlescript puzzle that we should solve, where the visible part just lets us input a flag and check if it is correct. Examining the source shows a large invisible board of symbols above the flag – the puzzle, after starting the check, looks something like the following:

.F...
.AAAR
.AAAR
CAAAR
 fff

The f’s are flag characters, A’s and R’s are random symbols from two different sets of 64 symbols (let’s label the sets A and R), and F and C are special symbols. We win if, after applying the rules, F and C are adjacent.

There are several types of rules:

[ A_47 | char15 ] -> [ L_46 | char15 ] again: converts an A-type symbol to an L-type symbol (a third set of 64 different symbols) based on an adjacent flag character,
right [ L_21 | R_25 ] -> [ R_17 | ] again: converts a pair LR to an R and empty space,
symbols fall down if the tile below them is empty, and
there is a single symbol in R (let’s call it Rt) that disappears when next to C.

For convenience, let’s label the function that maps (A, char) -> L as T(a,c), and the function that maps (L, R) -> R as F(l,r). We can see that, if we label the elements of a row as

a[n] ... a[2] a[1] a[0] r

the entire row will disappear if it is finally reduced to Rt, i.e.

F(T(a[n], flag[n]), ... F(T(a[1], flag[1]), F(T(a[0], flag[0]), r))) = Rt

It is useful to take a second look at the structure of the functions F and T. If we do this, we will see that F(l, F(l, r)) = r for all l and r, and that there exists an l0 such that F(l0, r) = r for all r. Therefore, if the sets L and R were equal, we could conclude that the group (L, T) is isomorphic to bit-strings of length 6 with xor as the group operator.

Similarly, looking at T shows that we can find a0 and c0 such that T(a0, c) = l0 and T(a, c0) = l0 for all a and c. For all a other than a0, T(a, c1) != T(a, c2), and similarly for c’s. This all strongly hints that we are dealing with a finite field that is most likely GF(2^6), with T as the multiplication operator and F as the addition, with the added complication that each element can be written in four different ways, as an element of L, R, A or a flag character.

This means that, if we can find mappings from all four of these sets to some set X, we could define a field (X, +, *), where + is F and * is T, in which our condition for a row to disappear is:

a[n]*flag[n] + ... + a[1]*flag[1] + a[0]*flag[0] + r = Rt

Assume that we know the elements of R, C (the set of characters) and A that map to the relevant neutral elements of the field: r0, c1 and a1. We can then build the entire mapping as:

for R, choose arbitrary different elements,
for L: l -> l + r0,
for A: a -> a * c1,
for C: c -> c * a1.

For each guess of these three values, we build the field, check that it reasonable (for each set, all elements map to different field elements; it is consistent with the rules given; field axioms hold), and then solve the set of linear equations given by the rows to find the flag.

This returns several candidate flags (though this might be due to a missing check in my implementation), but it is easy to filter the candidates for the one matching the flag format: PCTF{CTFs4R3Ju5TPuzZLeHUnTSWi7hM0reCoMPut3R5}.