Intro
Shifty is a cool game which requires you to reorder the cells within a table by rotating the columns (rotate up) and rows (rotate left).
The best way to describe it is by showing the first output you receive when connecting to the game server (nc 138.68.67.161 60006):
Welcome! Level 1 Your target: 0 1 2 A 0 1 2 B 3 4 5 C 6 7 8 Current board: 0 1 2 A 8 6 1 B 3 2 4 C 5 0 7 Enter 0-2 or A-C:
In the UI we are required to give the column or the row we wish to rotate up or left. We can send more than one rotation command and separate the commands using “,”.
For example, running the command ‘B’ from the previous output will give:
0 1 2 A 8 6 1 B 2 4 3 C 5 0 7
The multiple commands (separated by “,”) not unlimited. We found out pretty early we can separate long multiple commands using ‘\n’. The server will run all the commands and this will be faster than sending commands and wait for the prompt before sending the next ones.
After each command the server will send us the current board state.
The levels
Level 1 – 3 x 3 matrix to solve.
Level 2 – 12 x 12 matrix to solve.
Level 3 – 5 x 5 matrix without getting the board state after each command.
Level 4 – 4 x 4 matrix with randomized commands. Rotating A might rotate B instead. The randomized commands will change column to column and row to other row. Row will not be changed to column and vice verse. The randomized commands are defined at the beginning of the level and are not changed after defining them.
Level 5 – 4 x 4 matrix and both randomized commands and hidden state.
How to solve each level
Level 1
This was the naive solution which turned out to be too slow for the next levels. We give it anyway.
At first we implemented backtracking algorithm in C to solve the board. We decided to do it in C to control the memory allocations (to be none), reduce memory usage and increase solving speed. We wrapped the call to the process using python script to control the communication with the server using pwntools. We also decided to send the data from the python code to the c code using argv of main so we will not have to reallocate and memcpy it on the native code.
Run the code:
make shifty ./shifty 3 3 861324507 012345678
Level 2
At level 2 we realized everything we did in the first level is useless as backtracking is too slow for 12 x 12.
We decided to split the solution to two parts – solve all the rows but the last one and then solve the last row. We were able to split this mission to 2 persons.
For better performance we used numpy.
For the algorithms:
- Rotate down means to rotate up the height of the matrix minus one times.
- Rotate right means to rotate left the width of the matrix minus one times.
The top (size-1) rows
The rows except the last one were solved cell by cell. When trying to solve one cell, the expected number should be in that cell is called “working number”.
The algorithm:
- Assumes all the smaller numbers to the working number are set in their places.
- If the working number is on the correct row then we move it to the row below (without destroying the previous numbers):
- Shift down its column.
- Shift left the working number once.
- Shift up its previous column. Notice this column dont contain the working number anymore.
- Shift left the working number until it reaches to the column left of its target column.
- Shift down the target column until the previously placed numbers in that column is one row above the working number.
- Shift right the row of the working number.
- Shift up the working number column until the working number is in its place.
Example:
0 1 2 3 A 00 01 02 03 B 04 07 08 05 C 14 09 13 15 D 06 12 11 10
- We have all number up to 4 in its place. the working number is 5.
2.1. Shift down 5 once
0 1 2 3 A 00 01 02 10 B 04 07 08 03 C 14 09 13 05 D 06 12 11 15
2.2. Shift left number 5 once
0 1 2 3 A 00 01 02 10 B 04 07 08 03 C 09 13 05 14 D 06 12 11 15
2.3. Shift up column 3
0 1 2 3 A 00 01 02 03 B 04 07 08 14 C 09 13 05 15 D 06 12 11 10
- Shift left number 5 twice
0 1 2 3 A 00 01 02 03 B 04 07 08 14 C 05 15 09 13 D 06 12 11 10
- Shift down column 1
0 1 2 3 A 00 12 02 03 B 04 01 08 14 C 05 07 09 13 D 06 15 11 10
- Shift right row C
0 1 2 3 A 00 12 02 03 B 04 01 08 14 C 13 05 07 09 D 06 15 11 10
- Shift up column 1
0 1 2 3 A 00 01 02 03 B 04 05 08 14 C 13 15 07 09 D 06 12 11 10
Woohoo, number 5 is in its place.
The last row
- For each cell in the lowest row
1. Call the topmost-rightmost valuebad_val.
2. Find the leftmost invalid located cell in the matrix. Call itexist_val.
3. Find the cell which should be on the first invalid location. Call itmin_val.
4. Rotatemin_valto the rightmost cell.
5. Rotate up the leftmost column.
6. Rotateexist_valto the rightmost cell.
7. Rotate down the rightmost column.
8. Rotatemin_valto its right location.
9. If the topmost-rightmost value is notbad_val.
1. If the rightmost at the bottom value isbad_val.
1 Rotate right.
2. Rotate up.
3. Rotatebad_valinto the bottom rightmost.
4. Rotate down.
10. Rotatemin_valto its right location.
FixLastRow will be executed twice because calling it once does not cover all cases.
Execution example:
Current board:
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 03 B 04 05 06 07 C 08 09 10 11 D 12 15 13 14
- bad_val is 3
- The first exist_val is 15
- min_val is in column 2
- rotate the last row to the right
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 03 B 04 05 06 07 C 08 09 10 11 D 14 12 15 13
- rotate up column 3
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 07 B 04 05 06 11 C 08 09 10 13 D 14 12 15 03
- rotate 15 into column 3.
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 07 B 04 05 06 11 C 08 09 10 13 D 03 14 12 15
- rotate down column 3. now 13 is near 12.
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 15 B 04 05 06 07 C 08 09 10 11 D 03 14 12 13
- rotate 13 to its place
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 15 B 04 05 06 07 C 08 09 10 11 D 12 13 03 14
9.
- rotate up column 3
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 07 B 04 05 06 11 C 08 09 10 14 D 12 13 03 15
- rotate 3 to column 3
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 07 B 04 05 06 11 C 08 09 10 14 D 15 12 13 03
- rotate down colum 3
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 03 B 04 05 06 07 C 08 09 10 11 D 15 12 13 14
- rotate 13 back to its location
Enter 0-3 or A-D: 0 1 2 3 A 00 01 02 03 B 04 05 06 07 C 08 09 10 11 D 12 13 14 15
Woohoo, the last row is now ok.
Level 3
There is nothing special of this level. We don’t really need to know the current board each time because the operations effect are known and initial board is known.
Level 4
First try each operation and remember how it effect the board. Then reverse-map all the needed operation when inserted as input.
Level 5
This level is combining both level 3 and level 4. Because we can’t tell what each operation is doing we cannot use the method we used in level 4.
In this level we had to iterate over all the possible operation permutations. We solved the board for each permutation and sent the solution to the server. After sending the solution we waited for one second to receive the “Congrats!” string. If we got it then the flag was sent to us along it. If we did not receive this string we sent the reverse operations of the current assumed permutation and then sent the operations of the next permutation.
The reverse of commands is doing the same operations backwards where each command is multiplied by the size of the matrix minus one.
The code
Final solution
Execute:
python -i shifty.py
shifty.py
from itertools import permutations, product
import math
import numpy as np
import pwnlib
import pwn
def main():
row_mapping = ["a","b","c","d", "e", "f", "g", "h", "i", "j", "k", "l"]
col_mapping = [str(x) for x in range(12)]
import pwn
x = pwn.remote("138.68.67.161", 60006)
print("Level 1")
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping)
assert found_solution
print("Level 2")
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping)
assert found_solution
print("Level 3")
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping)
assert found_solution
print("Level 4")
row_mapping, col_mapping, current_board = find_mapping(x)
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping, \
current_board=current_board)
assert found_solution
print("Level 5")
size = len(current_board)
possible_columns = [str(x) for x in range(size)]
possible_rows = [chr(ord('a') + i) for i in range(size)]
found_solution = False
current_board = parse_current_board(x)
tries = math.factorial(size) ** 2
map_permutations = product(permutations(possible_columns, size), \
permutations(possible_rows, size))
for i, (col_mapping, row_mapping) in enumerate(map_permutations):
print("try " + str(i) + " / " + str(tries))
instructions, found_solution = \
negotitate_solution(x, row_mapping=row_mapping, col_mapping=col_mapping, \
current_board=current_board, timeout=1)
if found_solution:
print('found_solution')
break
instructions = reverse_instructions(instructions, size)
send_instructions(x, instructions)
x.interactive()
def solve_matrix(current_matrix, row_mapping, col_mapping):
instructions = ""
C = np.array(current_matrix)
size = len(current_matrix[0])
def RotateUp(mat):
nonlocal instructions
mat[:,size-1] = np.roll(mat[:,size-1],-1)
instructions += col_mapping[size-1]+","
return mat
def RotateDown(mat):
nonlocal instructions
for i in range(size-1):
mat[:,size-1] = np.roll(mat[:,size-1],-1)
instructions += col_mapping[size-1]+","
return mat
def RotateLeft(mat):
nonlocal instructions
mat[size-1] = np.roll(mat[size-1],-1)
instructions += row_mapping[size-1]+","
return mat
def RotateRight(mat):
nonlocal instructions
for i in range(size-1):
mat[size-1] = np.roll(mat[size-1],-1)
instructions += row_mapping[size-1]+","
return mat
def FixLastRow(mat):
last_line = mat[-1]
min_val = min(last_line)
i = 0
while i < size:
while i < size and min_val == mat[-1][i]:
i += 1
min_val += 1
if i == size:
break
exist_val = mat[-1][i]
while mat[-1][-1] != min_val:
mat = RotateLeft(mat)
mat = RotateUp(mat)
bad_val = mat[-1][-1]
while mat[-1][-1] != exist_val:
mat = RotateLeft(mat)
mat = RotateDown(mat)
while mat[-1][i] != min_val:
mat = RotateLeft(mat)
if mat[0][-1] != bad_val:
if mat[-1][-1] == bad_val:
mat = RotateRight(mat)
mat = RotateUp(mat)
while mat[-1][-1] != bad_val:
mat = RotateLeft(mat)
while mat[0][-1] != bad_val:
mat = RotateUp(mat)
while mat[-1][i] != min_val:
mat = RotateLeft(mat)
return mat
def ShiftCol(C, steps, col):
for i in range(steps):
C[:,col] = np.roll(C[:,col],-1)
return C
def ShiftRow(C, steps, row):
for i in range(steps):
C[row] = np.roll(C[row],-1)
return C
def GetCurrentPlace(C,num):
c_row = np.argwhere(C==num)[0][0]
c_col = np.argwhere(C==num)[0][1]
return c_row, c_col
def GetTargetPlace(size, num):
t_row = math.floor(num/size)
t_col = num%size
return t_row, t_col
def SolveOne(num, C):
nonlocal instructions
NEW_C = C
instruction = ""
size = len(C[0])
t_row, t_col = GetTargetPlace(size, num)
c_row, c_col = GetCurrentPlace(C, num)
if t_row == c_row and t_col == c_col:
instructions += instruction
return NEW_C
if t_row == c_row:
instruction += (col_mapping[c_col] + ",") * (size-1)
NEW_C = ShiftCol(NEW_C, size-1, c_col)
instruction += row_mapping[c_row+1] + ","
NEW_C = ShiftRow(NEW_C, 1, (c_row+1)%size)
instruction += col_mapping[c_col] + ","
NEW_C = ShiftCol(NEW_C, 1, c_col)
c_row += 1
c_col -= 1
if t_col == c_col:
instruction += row_mapping[c_row] + ","
NEW_C = ShiftRow(NEW_C, 1, c_row)
c_col -= 1
"""vertical"""
vertical_scroll = t_row + size - c_row
instruction += (col_mapping[t_col] + ",") * vertical_scroll
NEW_C = ShiftCol(NEW_C, vertical_scroll, t_col)
"""horizontal"""
if c_col > t_col:
horizontal_scroll = c_col - t_col
else:
horizontal_scroll = c_col + (size - t_col)
instruction += (row_mapping[c_row] + ",") * horizontal_scroll
NEW_C = ShiftRow(NEW_C, horizontal_scroll, c_row%size)
"""back vertical"""
instruction += (col_mapping[t_col] + ",") * (size - vertical_scroll)
NEW_C = ShiftCol(NEW_C, size - vertical_scroll, t_col)
instructions += instruction
return NEW_C
size = len(C[0])
for j in range(0, size * (size - 1)):
C = SolveOne(j,C)
instructions += "\n"
C = FixLastRow(C)
C = FixLastRow(C)
return C, instructions
def find_mapping(x):
current_board = parse_current_board(x)
size = len(current_board)
row_mapping = [None,]*size
col_mapping = [None,]*size
prev_board = current_board
for i in range(size):
x.sendline(str(i))
x.recvuntil("\n")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
current_board = parse_matrix(board)
col_mapping[find_col_change(prev_board, current_board)] = str(i)
prev_board = current_board
for i in range(size):
x.sendline(chr(ord('A') + i))
x.recvuntil("\n")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
current_board = parse_matrix(board)
row_mapping[find_row_change(prev_board, current_board)] = chr(ord('A') + i)
prev_board = current_board
return row_mapping, col_mapping, current_board
def reverse_instructions(ins, s):
return ''.join([(s-1) * (x + ",") for x in ins.split(",")[::-1]])
def find_col_change(prev, current):
return next(i for i, (x, y) in enumerate(zip(zip(*prev), zip(*current))) if x != y)
def find_row_change(prev, current):
return next(i for i, (x, y) in enumerate(zip(prev, current)) if x != y)
def parse_matrix(b):
return [[int(x) for x in l.split()[1:]] for l in b.splitlines() if l != b'']
def parse_current_board(x):
x.recvuntil("Your target:\n\n ")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
target_board = parse_matrix(board)
x.recvuntil("Current board:\n\n ")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
current_board = parse_matrix(board)
return current_board
def send_instructions(x, instructions):
instructions = instructions.strip(",")
x.recvuntil("Enter ")
x.recvuntil(": ")
for line in instructions.splitlines():
x.sendline(line)
def negotitate_solution(x, col_mapping, row_mapping, current_board=None, \
timeout=pwnlib.timeout.Timeout.default):
if current_board is None:
current_board = parse_current_board(x)
resolved_matrix, instructions = solve_matrix(current_board, row_mapping, col_mapping)
s = len(resolved_matrix)
assert all(resolved_matrix.reshape(s*s)==np.arange(s*s))
send_instructions(x, instructions)
y = x.recvuntil("Congrats!", timeout=timeout)
return instructions, b'Congrats!' in y
if __name__ == "__main__":
main()
Initial, useless c code:
Make:
make shifty
shifty.c:
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
void shift_row(char *mat, int row, int col_size, int row_size) {
char *r = &mat[row*col_size];
char last = r[0];
r += col_size-1;
for (int i = 0 ; i < col_size; ++i, --r) {
char l = *r;
*r = last;
last = l;
}
}
void shift_col(char *mat, int col, int col_size, int row_size) {
char *c = &mat[col];
char last = c[0];
c += col_size * (row_size-1);
for (int i = 0 ; i < row_size; i += 1, c-=col_size) {
char l = *c;
*c = last;
last = l;
}
}
void shiftback_row(char *mat, int row, int col_size, int row_size) {
char *r = &mat[row*col_size];
char last = r[col_size-1];
for (int i = 0 ; i < col_size; ++i, ++r) {
char l = *r;
*r = last;
last = l;
}
}
void shiftback_col(char *mat, int col, int col_size, int row_size) {
char *c = &mat[col];
char last = c[col_size * (row_size-1)];
for (int i = 0 ; i < row_size; i += 1, c+=col_size) {
char l = *c;
*c = last;
last = l;
}
}
void print_mat(char *mat, int col_size, int row_size) {
return;
for (int i = 0; i < col_size; ++i) {
for (int j = 0; j < row_size; ++j, ++mat) {
printf("%03d ", *mat);
}
printf("\n");
}
}
int check_solution(char *current, char *target, int col_size, int row_size) {
return !memcmp(current, target, row_size * col_size);
}
int solve_mat(char *current, char *target, int col_size, int row_size, int steps_left) {
if (check_solution(current, target, col_size, row_size)) {
return 1;
}
if (steps_left == 0) {
return 0;
}
steps_left--;
for (int i = 0; i < col_size; ++i) {
shift_row(current, i, col_size, row_size);
if (solve_mat(current, target, col_size, row_size, steps_left)) {
printf("%d,", i);
return 1;
}
shiftback_row(current, i, col_size, row_size);
}
for (int i = 0; i < row_size; ++i) {
shift_col(current, i, col_size, row_size);
if (solve_mat(current, target, col_size, row_size, steps_left)) {
printf("%c,", 'A' + i);
return 1;
}
shiftback_col(current, i, col_size, row_size);
}
return 0;
}
int main(int argc, char**argv) {
int col_size = atoi(argv[1]);
int row_size = atoi(argv[2]);
char *current = argv[3];
char *target = argv[4];
print_mat(current, col_size, row_size);
for (int i = 0; i < 1 << 16; ++i) {
if (solve_mat(current, target, col_size, row_size, i)) {
print_mat(current, col_size, row_size);
printf("\n");
return 0;
}
}
return 1;
}
Output example
> python -i shifty.py
Opening connection to 138.68.67.161 on port 60006
Opening connection to 138.68.67.161 on port 60006: Trying 138.68.67.161 [+] Opening connection to 138.68.67.161 on port 60006: Done Level 1 Level 2 Level 3 Level 4 Level 5 try 0 / 576 try 1 / 576 try 2 / 576 try 3 / 576 try 4 / 576 try 5 / 576 try 6 / 576 try 7 / 576 found_solution [*] Switching to interactive mode HackTM{you_sp1n_me_r1ght_r0und_b4by_round_r0und} [*] Got EOF while reading in interactive