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.
╭─face@0xff ~/ctf/fcsc/2023/reverse/picasso
╰─$ file picasso
picasso: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=6821f8
a80706b51ecc2b3d5da5bbc3c59a8e8868, for GNU/Linux 3.2.0, stripped
Reverse engineering
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 (x,y) couples, with x∈{0,…,5} and y∈{0,…,3}.
There are two central parts in the verification algorithm, that should be solved in reverse order.
In the first part, each (x,y) couple acts on a certain array of 54 elements, which I call initial_state.
k = 0;
qmemcpy(v23, &initial_state, sizeof(v23));
printf("Password: ");
fflush(stdout);
__isoc99_scanf("%24s", s);
while ( strlen(s) > k )
{
idx = strchr("abcdefghjklmnpqrstuvwxyz", s[k]);
if ( !idx )
{
v5 = "Nope!";
goto ERR;
}
y = (idx - "abcdefghjklmnpqrstuvwxyz") % 4;
permutation = &permutations[54 * ((idx - "abcdefghjklmnpqrstuvwxyz") / 4)];
while ( y > 0 )
{
y--;
qmemcpy(v24, v23, sizeof(v24));
for ( i = 0LL; i != 54; ++i )
v23[i] = v24[permutation[i]];
}
++k;
}
More precisely, for each "move", the x value selects a permutation (the array permutations consists of 6 distinct permutations of {0,…,53}). The y value is the number of times this permutation should be applied on the state.
The states are arrays of values in {0,…,15}, therefore I chose to represent them using hexadecimal nibbles. The initial state looks like this:
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:
initial_grid = 0x3DA8E0915F2C4B67;
j = 0;
while ( 1 )
{
nibble = permutated_state[j];
valid_moves_ptr = valid_moves;
m = 60;
while ( nibble != ((initial_grid >> m) & 0xF) )
{
LABEL_19:
m -= 4;
valid_moves_ptr += 5;
if ( m == -4 )
goto ERR;
}
v15 = valid_moves_ptr;
do
{
mask = *v15;
if ( !*v15 )
goto LABEL_19;
++v15;
}
while ( (initial_grid & (15 * mask)) != 0 );
transition = (nibble << m) ^ (mask * nibble);
if ( initial_grid == transition )
goto ERR;
if ( ++j == 54 )
break;
initial_grid ^= transition;
}
if ( (transition ^ initial_grid) == 0x123456789ABCDEF0 )
{
puts("Win!");
/* ... */
}
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.
Solving the second puzzle
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 {0,…,15} to 0x123456789ABCDEF0 was something I knew very well: the fifteen puzzle.
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.
For this reason, the program keeps track of a 5×16 matrix of bitmasks, which I called valid_moves, that looks like the following in hexadecimal:
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:
valid_moves_ptr = valid_moves;
m = 60;
while ( nibble != ((initial_grid >> m) & 0xF) )
{
m -= 4;
valid_moves_ptr += 5;
if ( m == -4 )
goto ERR;
}
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 "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.
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 (∀P, P4=P).
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:
9 C F j m p TWZS YRUX 6 3 0i f c
g d a 2 5 8KNQJ PILO r o l B E H
2581 7036RST 9AB abc IJK
OPQ ghi FGH XYZlork qjmp
ILOBEHA G9CFl k j 8 7 6 TWZ
XUR 0 1 2p q r cfib hadg QNK
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 9×6 grids. Let's take the three first permutations for example.
---------
9 C F
j m p
TWZS YRUX
6 3 0i
f c
---------
g d a
2 5 8
KNQJ PILO
r o l
B E H
---------
2581 7036
RST
9AB
abc
IJK
---------
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 3×3 block. Here's for the first permutation, where I replaced fixed points with underscores for clarity:
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 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:
D 3 2
E F 9
7 E D
5 9 1 6 3 2 4 3 D E B D
6 A B 7 2 8 4 C 3 1 A 1
2 5 C E 7 4 F 2 A 5 9 1
F 6 E
4 4 B
4 B F
->
6 3 2
7 F 9
E E D
1 B C F 3 2 4 3 D E B 7
9 A 5 4 2 8 4 C 3 1 A E
5 6 2 4 7 4 F 2 A 5 9 D
1 6 E
1 4 B
D B F
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.
U
LFRB
D
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:
E 5 4
B F E
D 3 5
D 9 2 4 E D D 9 2 1 4 2
1 A 3 9 2 6 1 C 7 6 A 3
1 4 5 F B E F B E 4 2 6
A 7 C
8 4 3
7 B F
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:
F D B
U U F
D F U
U R L B U L F L L U R R
F L F D F D L R B L B R
R U D F R B D B D L L B
R B R
B D D
U U F
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!
>>>> cubestring = "FDBUUFDFUFLLLRBDBDBULDFDFRBRBRBDDUUFURLFLFRUDURRLBRLLB"
>>>> sv.solve(cubestring)
depth 14 done in 0.14 s, 111513 nodes generated, about 779279 nodes/s
depth 15 done in 0.81 s, 1520577 nodes generated, about 1884035 nodes/s
depth 16 done in 8.45 s, 20361912 nodes generated, about 2410972 nodes/s
depth 17 done in 131.11 s, 273355368 nodes generated, about 2084905 nodes/s
depth 18 done in 30.93 s, 77918135 nodes generated, about 2518900 nodes/s
total time: 171.53 s, nodes generated: 373276100
'U1 F2 R2 U2 R1 L2 D1 L3 U3 B1 L1 D2 F1 R2 F1 L3 U2 R2 (18f*)'
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:
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!
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 . 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 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 by Herbert Kociemba.
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 , 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.
Does it ring a bell now? Yup: it's a . 6 faces, each face has 3×3 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.
For the solving part, I chose to use this , 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 ).
