Shifty (misc)

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:

  1. Assumes all the smaller numbers to the working number are set in their places.
  2. If the working number is on the correct row then we move it to the row below (without destroying the previous numbers):
    1. Shift down its column.
    2. Shift left the working number once.
    3. Shift up its previous column. Notice this column dont contain the working number anymore.
  3. Shift left the working number until it reaches to the column left of its target column.
  4. Shift down the target column until the previously placed numbers in that column is one row above the working number.
  5. Shift right the row of the working number.
  6. 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
  1. 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
  1. 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
  1. 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
  1. 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
  1. 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

  1. For each cell in the lowest row
    1. Call the topmost-rightmost value bad_val.
    2. Find the leftmost invalid located cell in the matrix. Call it exist_val.
    3. Find the cell which should be on the first invalid location. Call it min_val.
    4. Rotate min_val to the rightmost cell.
    5. Rotate up the leftmost column.
    6. Rotate exist_val to the rightmost cell.
    7. Rotate down the rightmost column.
    8. Rotate min_val to its right location.
    9. If the topmost-rightmost value is not bad_val.
    1. If the rightmost at the bottom value is bad_val.
    1 Rotate right.
    2. Rotate up.
    3. Rotate bad_val into the bottom rightmost.
    4. Rotate down.
    10. Rotate min_val to 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
  1. bad_val is 3
  2. The first exist_val is 15
  3. min_val is in column 2
  4. 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
  1. 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
  1. 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
  1. 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
  1. 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.

  1. 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
  1. 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
  1. 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
  1. 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

[x]

Opening connection to 138.68.67.161 on port 60006

[x]

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