PoliCTF 2017

PoliCTF 2017 - Tower

11 Jul 2017

Case Notes

You are entering a Lab where you will be the experiment

nc tower.chall.polictf.it 31337

Recon

Unfortunately I only started writing this writeup one day after the challenge has closed, so there isn’t anything that I can show. For those that did not attempt this challenge, the maze looks something like the following (but a way larger one in the challenge)

 _ _ _ _ _ _ _ _
|  _     _      |
|  _ _ _ _  |   |
|_ _        |   |
|   |   |  _|   |
|_ _ _ _ _|_ _ _| 

(I know it looks horrible, I’m actually not very sure if the challenge looks like this, you get the idea)

The basic rules of the game are

We start at (0, 0), which is the cell at the bottom left
We use the keys w, a, s, d to move around
The | and _ characters indicate a wall, which you cannot bump into or you will lose
You need to reach the given coordinates (x, y)

However, if we carefully inspect the maze, one move sideways (left or right) actually changes our position by 2 characters, as we can see that each row in the maze is in the pattern of ['_' or ' ']['|' or ' ']['_' or ' ']['|' or ' ']..., which means every second character in the row tells us whether we can move sideways. So, we need to take care of this.

Moving vertically still changes our vertical position by 1 character so that does not pose a problem. But, to implement such a grid (or maze) in an array, the index of 0 gives us the topmost string, but in this case we want the bottom to be 0, not the top, since (0, 0) is at the bottom left of the maze, so that is another thing we need to take note of.

To one who is familiar with the Depth/Breadth First Search algorithm, this challenge is pretty straightforward.

Depth First Search

I’ll be implementing the Depth First Search (DFS) algorithm to solve this challenge. If you are already familiar with DFS, you may skip through to the solution (actually there is not much point reading this writeup since the implementation is pretty straightforward).

If you are not familiar with DFS, I recommend watching this short animation here, or read up more about it if you are interested, but you can read a less detailed guide of it here.

I’ll explain it in terms of a grid (with x, y coordinates), for the sake of the challenge, instead of the linked nodes implementation in the animation.

Motivation

First, we need to know what is DFS trying to achieve, in order to use it. Simply put, DFS is a recursive algorithm that allows us to traverse through all possible nodes (in this case the cells) in a graph (in this case the maze), without revisiting visited nodes.

Breadth First Search is similar but I will not explain it here for the sake of discussion.

With this, we are able to do a lot of things. In the case of solving the maze, we can visit all possible cells in the maze and tell whether it is somewhere we want to be, and through that obtaining our list of directions to move in.

Alright here’s a hopefully simple and easy to understand implementation of DFS.

Implementation

First, lets have a look at this pseudocode, assuming we have a grid like the maze given in the challenge

dfs(x, y):
	
    // 1. check if we've been here before
    if visited(x, y):
        // do something, often we'll just return
        return

    visited(x, y) = true;

    // 2. some base cases to handle, for example
    if x < 0 || y < 0:
        return -1
    if cell(x, y) == destination:
        return 1
    ...

    // 3. with this loop we are able to call dfs with (x-1, y), (x+1, y), (x, y-1), (x, y+1)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for i in range(len(dx)):
        result = dfs(x + dx[i], y + dy[i])
        // do something with the result

    // 4. return something
    return something

The code above can be splitted into a few sections.

Check if visited

Since we’ll be traversing throught the grid, we want to make sure we don’t visit the same point again, because there is no point doing so and this may waste a lot of time.

Base cases

Before we proceed to visit the neighbouring nodes, we want to make sure if we want to proceed. For example if we are outside the grid then we should probably not visit our neighbouring nodes. Or if we are at our destination, we may wanna return true to let the caller know.

Visit neighbouring nodes

What we do here is just calling dfs() on our neighbouring nodes. The basic idea is our neighbour will call dfs() on its neighbours, its neighbours calling on their neighbours, calling on their neighbours, on their neighbours, ..., until we hit one of our base cases that asks the cell to stop visiting other nodes already.

Return something

After all our calls to dfs() have returned, we have to decide what to do with their returned results, and return something to the whoever that called dfs() on us.

Solution

Above is a very summarized example on how to use DFS. I still recommend reading up on DFS and BFS for a better understanding of the algorithms.

My solution essentially contains implementation of DFS to solve the challenge in python, and some helper functions to address the concerns mentioned earlier.

Converting coordinates to indices

As mentioned earlier, our perceived coordinates is not equal to the index we’ll be using to lookup on the grid. For sideways, we will move by 2 characters every time. Whereas for vertical movement, the index to retrieve the row starts with 0 from the top, but we want it to start from the bottom.

# converts our perceived position to index in the array
def coordToIndex(grid, x, y):
    return (2 * x + 1, len(grid) - y - 1)

getCell()

Since we have to use grid[y][x] to retrieve the row first, then the character of the selected column, instead of grid[x][y], to prevent using it wrongly by instinct, I used the following helper function.

# gets content of cell in (x, y)
# used with coordToIndex
def getCell(grid, x, y):
    return grid[y][x]

dfs

Below is my implementation of dfs to solve the challenge.

def dfs(grid, x, y, targetX, targetY):
    index = coordToIndex(grid, x, y)
    i_x = index[0]
    i_y = index[1]

    if (x, y) in solved:
        return False

    solved.append((x, y))

    if x < 0 or x >= len(grid[0]) / 2 - 1:
        return False

    if y < 0 or y >= len(grid):
        return False

    if x == targetX and y == targetY:
        return " "

    # go left
    if not getCell(grid, i_x - 1, i_y) == '|':
        result = dfs(grid, x - 1, y, targetX, targetY)
        if result:
            return 'a' + result

    # go right
    if not getCell(grid, i_x + 1, i_y) == '|':
        result = dfs(grid, x + 1, y, targetX, targetY)
        if result:
            return 'd' + result

    # go up
    if not getCell(grid, i_x, i_y - 1) == '_':
        result = dfs(grid, x, y + 1, targetX, targetY)
        if result:
            return 'w' + result

    # go down
    if not getCell(grid, i_x, i_y) == '_':
        result = dfs(grid, x, y - 1, targetX, targetY)
        if result:
            return 's' + result

    return False

1) Initiate variables i_x and i_y generated by coordToIndex(x, y)

2) Before doing anything we check if we have visited this cell before.

3) We check if the cell is outside of the grid and return False if so.

4) If we have reached our destination, return an empty string which evaluates to True and can be appended to our list of directions (you’ll understand why in the next step).

5) Try to visit the neighbouring cells in all directions with dfs() if there is no wall blocking, and handle the return value

If False, it means that neighbouring node is useless (or all 4 of that neighbour’s neighbours are useless)
If we get a string with arbitrary length, it will evaluate as True in an if statement. That string will contain the directions to reach the destination from that neighbour cell, so we just prepend the string with the direction to get to that cell and return the string.
Hence if we get an empty string its means it takes 0 steps to reach the destination from our neighbour, since our neighbour is the destination.

6) Return False in the end because if we do not return anything after traversing all 4 directions, it means every direction is useless, which means this cell is useless.

Complete solution

Finally, we piece everything together and use pwntools to connect to the remote server and retrieve the strings to get our maze and destination.

from pwn import *

solved = []

# gets content of cell in (x, y) 
# used with coordToIndex
def getCell(grid, x, y):
	return grid[y][x]

# converts our perceived position to index in the array
def coordToIndex(grid, x, y):
	return (2 * x + 1, len(grid) - y - 1)

def dfs(grid, x, y, targetX, targetY):
	index = coordToIndex(grid, x, y)
	i_x = index[0]
	i_y = index[1]

	if (x, y) in solved:
		return False

	solved.append((x, y))

	if x < 0 or x >= len(grid[0]) / 2 - 1:
		return False

	if y < 0 or y >= len(grid):
		return False

	if x == targetX and y == targetY:
		return " "

 #	print (x, y)

	# go left
	if not getCell(grid, i_x - 1, i_y) == '|':
		left = dfs(grid, x - 1, y, targetX, targetY)
		if left:
			return 'a' + left

	# go right
	if not getCell(grid, i_x + 1, i_y) == '|':
		right = dfs(grid, x + 1, y, targetX, targetY)
		if right:
			return 'd' + right
	
	# go up
	if not getCell(grid, i_x, i_y - 1) == '_':
		up = dfs(grid, x, y + 1, targetX, targetY)
		if up:
			return 'w' + up
	
	# go down
	if not getCell(grid, i_x, i_y) == '_':
		down = dfs(grid, x, y - 1, targetX, targetY)
		if down:
			return 's' + down
	
	return False

r = remote("tower.chall.polictf.it", 31337)

grid = []

r.recvline()
line = r.recvline()

while not line[:5] == 'start':
	grid.append(line)
	# print line[:-1]
	line = r.recvline()

start = line[:-1].split(': ')[1].split(', ')
line = r.recvline()
end = line[:-1].split(': ')[1].split(', ')

"""
index = coordToIndex(grid, len(grid[0]) / 2 - 2, 0)
l = list(grid[index[1]])
l[index[0]] = 'X'
grid[index[1]] = "".join(l)

index = coordToIndex(grid, int(end[0]), int(end[1]))
l = list(grid[index[1]])
l[index[0]] = '#'
grid[index[1]] = "".join(l)
"""
"""
for y in range(len(grid)):
	for x in range(len(grid[0]) / 2):
		index = coordToIndex(grid, x, len(grid) - y - 1)
		sys.stdout.write(getCell(grid, index[0] - 1, index[1]))
		sys.stdout.write(getCell(grid, index[0], index[1]))
	print ""
"""
r.recvline()
r.recvline()

solution = dfs(grid, int(start[0]), int(start[1]), int(end[0]), int(end[1]))
print solution
r.sendline(solution)
r.interactive()

Running the script gives us flag{Does_Runn1ng_r4ndom_m4z3s_make_you_h4ppy!?!?!?}

Unfortunately, as I only started writing this writeup one day after the competition has ended, I was unable to connect to the server to solve the maze and get the flag again, so I can’t provide any evidence that my code works but you’ll just have to take my word for it.

I hope this writeup successfully (I really hope so) helped those who are not familiar with Depth First Search to gain more insight about it.