P'HackCTF 2021 - Maze challenge write-up
4 min read

P'HackCTF 2021 - Maze challenge write-up

P'HackCTF 2021 - Maze challenge write-up

A-Maze-Ing

A strange server wants to put you to the test.
Be up to the challenge.

Server : a-maze-ing.phack.fr:4242
Author : @Pdrooo

Write Up

http://a-maze-ing.phack.fr:4242/

We retrieve the maze from /chall (GET) and send the correct path to /chall (POST). The /flag endpoint is just a joke.

Let's print the maze :

#!/usr/bin/env python3
from requests import get
from json import loads

URL_CHALL = "http://a-maze-ing.phack.fr:4242/chall"

req_json = loads(get(URL_CHALL).text)
token = req_json["token"]
maze = req_json["solveMe"]

print("Token :", token)
print("Maze :", maze)
$ python3 solve.py 
Token : 4c0dff7c367f478392098fe2a5cb2be2
Maze : ######################x      #           ######## ### ####### ##     #   #   #     ## ### ### ### # ###### # #     #   #     ## # ############### ## #     #   #       ## ### # # # # ##### ##     #   #   #     ################ ######   #         #     ## # ### ### ####### ## #     #   #     # ## ####### ### ### # ##       #   # # #   ## ##### ### # # ###### #   # #   #     # ## ### # ######### # ##     #            $######################

Hmm the maze looks like nothing, maybe it's a square ?? Let's print it again like a square :

#!/usr/bin/env python3
from math import sqrt

[...]

print("Token :", token)
print("Maze :")

side_len = int(sqrt(len(maze)))
for i in range(side_len):
    print(maze[i*side_len:i*side_len+side_len])
$ python3 solve.py 
Token : c9b1c4b5ac5943c6bebb710451e72f64
Maze :
#####################
#x#     #       #   #
# # # # # ##### # # #
# # # # # #   #   # #
# ### ### ### ##### #
#   #   #     #     #
### ### # ##### ### #
# #   #   #   # #   #
# ### # ### # # # ###
#   # #   # #   # # #
# ### ##### ##### # #
#     #     #   #   #
# ##### ##### ##### #
#   #   #         # #
### # ########### # #
# #   #           # #
# ##### ### ####### #
#       #   #   #   #
# ### ####### # # ###
#   #         #    $#
#####################

Yes, much better now ! The person 'x' needs to escape the police and go to the '$' position.

Let's use the networkx librairy to solve this problem.
To start, let's transform the maze into a 2D array.

side_len = int(sqrt(len(maze)))
maze_array = []
for i in range(side_len):
    maze_array.append(list(maze[i*side_len:i*side_len+side_len]))

Then, make a function to find the start and end coordinates.

def find_pos(maze_array, char):
    for i in range(len(maze_array)):
        for j in range(len(maze_array[i])):
            if maze_array[i][j] == char:
                return (i, j)

start_pos = find_pos(maze_array, 'x')
end_pos = find_pos(maze_array, '$')

Let's create the maze in networkx as a graph :

G = nx.Graph()

for i in range(side_len):
    for j in range(side_len):
        G.add_node((i,j))
        
        if i > 0: G.add_edge((i-1, j), (i, j))
        if j > 0: G.add_edge((i, j), (i, j-1))
        if i < size-1: G.add_edge((i, j), (i+1, j))
        if j < size-1: G.add_edge((i, j), (i, j+1))

for i in range(side_len):
    for j in range(side_len):
        if maze_array[i][j] == '#':
            G.remove_node((i, j))

All cases are "nodes" and the path between them are "edges".
First we add the nodes to the graph with the path to their neighbor nodes. Then we remove the node which represents the wall, '#'.

For permormance reason we can only keep this two lines because if we let the four lines as before, you will have duplicate edges.

        if i > 0: G.add_edge((i-1, j), (i, j))
        if j > 0: G.add_edge((i, j), (i, j-1))

Once we are done with that, networkx will find the correct path between the start and the final position :

old_pos = None
path = ""
for point in nx.algorithms.astar_path(G, start_pos, end_pos):
    if old_pos is not None:
        if point[0] < old_pos[0]: # +1 Down, -1 up
            path += "↑"
        elif point[0] > old_pos[0]:
            path += "↓"
        if point[1] < old_pos[1]: # +1 Right, -1 Left
            path += "←"
        elif point[1] > old_pos[1]:
            path += "→"

    old_pos = point

print("PATH :", path)

You just need to send the path to /chall (POST) and you get the flag !

Final script :

#!/usr/bin/env python3
from math import sqrt
from requests import get, post
from json import loads
import networkx as nx

URL_CHALL = "http://a-maze-ing.phack.fr:4242/chall"

def send_solution(solution):
    req = post(URL_CHALL, json=solution)
    print(req.text)

def find_pos(maze_array, char):
    for i in range(len(maze_array)):
        for j in range(len(maze_array[i])):
            if maze_array[i][j] == char:
                return (i, j)

def print_maze(maze_array):
    for i in range(len(maze_array)):
        print("".join(maze_array[i]))

req_json = loads(get(URL_CHALL).text)
token = req_json["token"]
maze = req_json["solveMe"]

print("TOKEN :", token)
size = int(sqrt(len(maze)))

maze_array = []
for i in range(size):
    maze_array.append(list(maze[i * size : i * size + size]))

assert len(maze_array) == size
for i in range(len(maze_array)):
    assert len(maze_array[i]) == size

G = nx.Graph()
for i in range(size):
    for j in range(size):
        G.add_node((i, j))

        if i > 0:
            G.add_edge((i-1, j), (i, j))
        if j > 0:
            G.add_edge((i, j), (i, j-1))

for i in range(size):
    for j in range(size):
        if maze_array[i][j] == "#":
            G.remove_node((i, j))

print_maze(maze_array)
start_pos = find_pos(maze_array, "x")
end_pos = find_pos(maze_array, "$")
print("START :", start_pos, "END :", end_pos)
old_pos = None
path = ""
for point in nx.algorithms.astar_path(G, start_pos, end_pos):
    if old_pos is not None:
        if point[0] < old_pos[0]:  # +1 Down, -1 up
            path += "↑"
        elif point[0] > old_pos[0]:
            path += "↓"
        if point[1] < old_pos[1]:  # +1 Right, -1 Left
            path += "←"
        elif point[1] > old_pos[1]:
            path += "→"

    old_pos = point

print("PATH :", path)

solution = {"token": token, "solution": path}

send_solution(solution)

Execution :

$ python3 solve.py 
TOKEN : d95c9659af8d4b57940180264735ad10
#####################
#x#       #         #
# ####### # ##### # #
# #       #   #   # #
# # ######### # ### #
# #           # # # #
# ### ######### # # #
#   #     #   # #   #
### ####### # # # ###
# #   #     #   # # #
# ### # ######### # #
#   # #       # #   #
# ### # ##### # ### #
#   # # #   # #   # #
### # ### # # # # # #
#   #   # #   # # # #
# ##### # ##### ### #
# #   # # #   #   # #
# # # # # # ### # # #
#   #     #     #  $#
#####################
START : (1, 1) END : (19, 19)
PATH : ↓↓↓↓↓↓→→↓↓→→↓↓↓↓↓↓→→↓↓↓↓→→↑↑↑↑↑↑→→↓↓→→↑↑↑↑←←←←←←↑↑→→→→↑↑→→↓↓→→↑↑↑↑↑↑→→↑↑→→↓↓↓↓↓↓←←↓↓↓↓→→↓↓↓↓↓↓↓↓
Congrats ! The flag is PHACK{M4zEs_4Re_7rUly_4m@zIng}

Flag : PHACK{M4zEs_4Re_7rUly_4m@zIng}

Enjoying these posts? Subscribe for more