# 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 a a r``

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

``F(T(a[n], flag[n]), ... F(T(a, flag), F(T(a, flag), 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*flag + a*flag + 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}`.