Picasso (reverse)
Last updated
Last updated
Picasso was a hard reverse challenge from FCSC 2023, which verged on the more puzzly side of the spectrum.
We were given a tiny ELF file (15 Ko) and asked to find a valid entry.
The reverse engineering part of the challenge was definitely the easiest part. There is only one (!) function of interest, and it is rather small --- everything is here.
At first glance of the code, here are the main takeaways:
The input is a 24-character string with lower case letters from the alphabet (minus o and i) that encode couples, with and .
There are two central parts in the verification algorithm, that should be solved in reverse order.
In the first part, each couple acts on a certain array of 54 elements, which I call initial_state.
We will take a closer look at the set of permutations later.
In the second part of the algorithm, our newly permutated state is fed to another loop:
This time around, we have another quantity, 0x3DA8E0915F2C4B67, which I called initial_grid. This 64-bit integer basically undergoes permutations as well, and the goal is for it to reach 0x123456789ABCDEF0.
I immediately thought of this puzzle for a very particular reason: I made a challenge centered around it for ECW CTF 2021, which writeup you can find on my blog. The idea was basically that there was one process per cell, and the moves were encoded using a communication protocol through pipes between adjacent cells.
In this challenge, the fifteen puzzle is encoded in a form that is a bit easier to comprehend. Each grid state is represented by a 64-bit integer where each hexadecimal nibble gives the value of a cell (0 is the hole).
The 54-nibble long array that is output from the first puzzle encodes the different moves to play on the grid. There are only two valid moves for each grid state: for instance, in the image above, the valid moves are 13 and 7.
Let's take an example. When the first move is selected (nibble = permutated_state[j]), the program then looks for this value in the grid state:
Finding the move's position in the grid state also brings the valid_moves array to a certain row index. For instance, imagine that the first nibble move is "D": it's the second cell in the following initial state.
The selected row of bitmasks is:
The "1" bits encode all the possible hole positions for our move! In our case, the hole ("0") is right below the cell we want to move ("D"), and the third bitmask allows that. Note: I'm not sure why each bitmask row store 5 bitmasks instead of 4, the last one being always null.
Once the move has been identified and deemed valid, a transition mask is crafted. It basically permutes the two cells in the grid state.
In order to solve this part, we should find a solution to this instance of the fifteen puzzle that is exactly 54 moves long (which turns out to be the optimal solution length). I used the program 15-Puzzle Optimal Solver by Herbert Kociemba.
This gives us a solution, that is, written in hexadecimal:
We can now come back on the first puzzle! We know that we want to go from a certain initial state to a target state in 24 moves.
We have a set of 6 permutations at our disposal, and each permutation can be repeated up to three times in a row.
The set of permutations is the following:
Unfortunately, at this moment, I didn't investigate the permutations much further. I spent countless hours trying to solve the problem as a generic "go from A to B using a set of permutations" problem. I mostly experimented with the IDA* algorithm, but coming up with a decent heuristic proved to be difficult. Several times I found a sequence of moves that got me quite close to the target, but little did I know that I was actually very far.
At some point, I came back on the permutations and tried to visualize them from another angle. I mapped each integer from 0 to 53 to a character in the following (arbitrary) charset:
Then, I wrote down the six permutations, replacing the fixed points with spaces:
Actually, it is even easier to visualize the Rubik's cube simply by applying the different permutations to the initial state. If we look at the action of the first permutation:
We split that into six faces:
We can identify the face that was rotated one quarter counter-clockwise: it's the fourth one. Performing this with each permutation, and also visualizing the permutations on the adjacent faces, we are able to successfully reconstruct the cube's layout.
For instance, the first permutation is best visualized like this:
The cube net is shown here as the following, where U is Up, L is Left, F is Front, R is Right, B is Back and D is Down.
Using this notation, we find that the state arrays in the program are stored as:
We also find that the permutations are, in order, counter-clockwise rotations of L, R, U, D, F, B.
Now, we know that we want to solve the cube for this target:
This layout is what we would consider the solved cube (imagine if each facet was mapped to one color out of six). Since each facet is unique (they can be uniquely determined by their neighbours, depending on their nature: center, corner, edge), we can map each face in the solved cube to unique, disjoint sets of facets.
For each face, I chose the following notation:
X-Y means the X facet belongs to the face and has one neighbour Y on another facet (edge);
X-YZ means the X facet belongs to the face and has two neighbours Y and Z on two other facets (corner);
X-ABCD means the X facet is the center of the face.
Therefore, for each face, we obtain a set of unique facets using our notation by reading the target cube:
We can now remap the initial cube by identifying each facet and which "face color" they are! This gives this:
I did this whole process by hand; this was a bit tedious and required some concentration, but at last we managed to remap the problem into a "normal" looking cube that we can now feed to an existing solver!
For the solving part, I chose to use this optimal Python solver, written by none other than... again, Herbert Kociemba. The world of permutation puzzles is a small one!
The solver works by first generating several look-up tables in around 15 minutes, that take up several hundreds of megabytes. Then, solving a scrambled cube is as easy as calling the solve method and waiting about three minutes (using pypy).
Given how computationally heavy the problem of optimally solving a Rubik's cube instance is, we understand why our former IDA* attempt did not give any result.
The solver yields an optimal solution in 18 moves, which is under 24: great!
All we have to do now is to map the moves back to our set of permutations, and construct the input string. Since the binary wants exactly 24 moves, we can pad our solution with "null" rotations (for instance, permutation 0 performed 0 times). This gives the following string:
Feed this input to the server, and we won!
Even though it was more "puzzle" that "reverse", I thought this challenge was excellent. It required a lot of intuition and rigor.
I found the combination of the two puzzles to be very seamless and elegant. It's crazy how much complexity and puzzles one can pack into such a tiny binary and function!
More precisely, for each "move", the value selects a permutation (the array permutations consists of 6 distinct permutations of ). The value is the number of times this permutation should be applied on the state.
The states are arrays of values in , therefore I chose to represent them using hexadecimal nibbles. The initial state looks like this:
When I first opened the binary in IDA, the second puzzle was definitely the quickest one to catch my attention. Going from a permutation of to was something I knew very well: the fifteen puzzle.
For this reason, the program keeps track of a matrix of bitmasks, which I called valid_moves, that looks like the following in hexadecimal:
Each bitmask can be seen as a matrix:
I thought the permutations looked a bit specific. There are a lot of fixed points, and the only non-trivial cycles are of length 4, which is an interesting property (, ).
Still a bit cryptic, but we can see interesting patterns that makes us want to visualize the permutations in two dimensions. Since length is 54, we could rearrange them into grids. Let's take the three first permutations for example.
Starts looking better... but not quite there. It looks like there are still some kinds of column patterns appearing. Let's split each row into a block. Here's for the first permutation, where I replaced fixed points with underscores for clarity:
Does it ring a bell now? Yup: it's a Rubik's cube. 6 faces, each face has facets. Each permutation rotates one face (here, counter-clockwise). The repetition of a permutation 1 to 3 times is how many times you want to rotate a face. In the above permutation, we can effectively see that the rotation applies to the fourth face, that there are 4 other faces which are impacted by the rotation, and that there is an opposite face which is not impacted at all.
