Dynamic Maze Path Finder
I encountered one CTF challenge, where the key to the flag was the sequence of letters, which represented the moves from the starting point:
- ‘R’ – Right
- ‘L’ – Left
- ‘D’ – Down
- ‘U’ – Up
So the key should be something like this: DDLRLLULU….
Example of the maze:
Example of the Random Maze Generator created in JavaScript..
So far so good, but there were two catches:
1) You should find and submit the answer in less than 45 s
2) After the countdown, you could refresh the page but the maze will change and with that as well the key.
One thing was also important, that the starting and the finishing point of the maze was always the same:
- Starting point: X: 1, Y:0
- Finishing point: X:79, Y:40
How to start this challenge? Firstly, I didn’t know where to begin, but with a bit of researching, reverse engineering, scripting and some of my IT skills put into the practice I solved the path/key of the maze to capture the flag. I bet that this may not be the most “elegant” solution, but it took me to the end.
Disclaimer: As you see the maze is a matrix of 81×41, that’s why the code in the snippets is omitted and I put the full HTML and BTS code in the attachment below the code.
Source code of the page
I checked the source code of the page to find the HTML code of the maze, which looked like something like this (I used just the code relative to the maze):
<div>■<font style='color:white'>☺</font>■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■<br>■ ■ ■ ■ ■ ■ ■ ■ &
<!-- code omitted -->
■ ■<br>■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■<font style='color:red'>♥</font>■<br></span></div>
Transformation to a Binary matrix
The I needed to convert the ■ into 1‘s and into 0‘s, because I wanted to use the Breadth-first search algorithm with a Phyton script, that I found it online, and slightly modify it. 1’s are represeting the walls and the 0’s are representing the empty space. For the starting and endping point I’ve considered a 0 as well. I saved the HTML code into a file.txt and then use the replace Python script:
# Read in the file
with open('/maze/file.txt', 'r') as file :
filedata = file.read()
# Replace the target string
filedata = filedata.replace('<div>■<font style=\'color:white\'>☺</font>', '[1,0,')
filedata = filedata.replace('■<br>', '1],\n[')
filedata = filedata.replace('■', '1,')
filedata = filedata.replace(' ', '0,')
filedata = filedata.replace('<font style=\'color:red\'>♥</font>', '0,')
filedata = filedata.replace('[</span></div>', '')
# Write the file out again
with open('/maze/file.txt', 'w') as file:
file.write(filedata)Which gave me the following matrix (omitted):
[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1],
[1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1],
[1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],
BTS script
And this matrix I copyed into the maze script (the end and start variables are inverted).
from PIL import Image, ImageDraw
images = []
a = [
[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,1],
[1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1],
[1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1],
[1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],
]
zoom = 20
borders = 6
start = 40,79 #actual end
end = 0,1 #actual start
def make_step(k):
for i in range(len(m)):
for j in range(len(m[i])):
if m[i][j] == k:
if i>0 and m[i-1][j] == 0 and a[i-1][j] == 0:
m[i-1][j] = k + 1
if j>0 and m[i][j-1] == 0 and a[i][j-1] == 0:
m[i][j-1] = k + 1
if i<len(m)-1 and m[i+1][j] == 0 and a[i+1][j] == 0:
m[i+1][j] = k + 1
if j<len(m[i])-1 and m[i][j+1] == 0 and a[i][j+1] == 0:
m[i][j+1] = k + 1
def print_m(m):
for i in range(len(m)):
for j in range(len(m[i])):
print( str(m[i][j]).ljust(2),end=' ')
print()
def draw_matrix(a,m, the_path = []):
im = Image.new('RGB', (zoom * len(a[0]), zoom * len(a)), (255, 255, 255))
draw = ImageDraw.Draw(im)
for i in range(len(a)):
for j in range(len(a[i])):
color = (255, 255, 255)
r = 0
if a[i][j] == 1:
color = (0, 0, 0)
if i == start[0] and j == start[1]:
color = (0, 255, 0)
r = borders
if i == end[0] and j == end[1]:
color = (0, 255, 0)
r = borders
draw.rectangle((j*zoom+r, i*zoom+r, j*zoom+zoom-r-1, i*zoom+zoom-r-1), fill=color)
if m[i][j] > 0:
r = borders
draw.ellipse((j * zoom + r, i * zoom + r, j * zoom + zoom - r - 1, i * zoom + zoom - r - 1),
fill=(255,0,0))
for u in range(len(the_path)-1):
y = the_path[u][0]*zoom + int(zoom/2)
x = the_path[u][1]*zoom + int(zoom/2)
y1 = the_path[u+1][0]*zoom + int(zoom/2)
x1 = the_path[u+1][1]*zoom + int(zoom/2)
draw.line((x,y,x1,y1), fill=(255, 0,0), width=5)
draw.rectangle((0, 0, zoom * len(a[0]), zoom * len(a)), outline=(0,255,0), width=2)
images.append(im)
m = []
for i in range(len(a)):
m.append([])
for j in range(len(a[i])):
m[-1].append(0)
i,j = start
m[i][j] = 1
k = 0
while m[end[0]][end[1]] == 0:
k += 1
make_step(k)
draw_matrix(a, m)
i, j = end
k = m[i][j]
the_path =[(i, j)]
while k > 1:
if i > 0 and m[i - 1][j] == k-1:
i, j = i-1, j
the_path.append('G')
k-=1
elif j > 0 and m[i][j - 1] == k-1:
i, j = i, j-1
the_path.append('L')
k-=1
elif i < len(m) - 1 and m[i + 1][j] == k-1:
i, j = i+1, j
the_path.append('D')
k-=1
elif j < len(m[i]) - 1 and m[i][j + 1] == k-1:
i, j = i, j+1
the_path.append('R')
k -= 1
#print_m(m)
print(the_path)
images[0].save('maze.gif',
save_all=True, append_images=images[1:],
optimize=False, duration=1, loop=0)
The script that I used is also “drawing” the path (with different tries) of the algorithm, but I won’t focus on that part of the output. Probably without this, the script would be even faster.
Output:
[(0, 1), 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'G', 'G', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'R', 'R', 'R', 'G', 'G', 'R', 'R', 'R', 'R', 'R', 'R', 'G', 'G', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'L', 'L', 'G', 'G', 'L', 'L', 'L', 'L', 'D', 'D', 'D', 'D', 'L', 'L', 'G', 'G', 'L', 'L', 'D', 'D', 'L', 'L', 'D', 'D', 'R', 'R', 'D', 'D', 'L', 'L', 'R', 'R', 'R', 'R', 'R', 'G', 'G', 'R', 'R', 'G', 'G', 'R', 'R', 'D', 'D', 'R', 'R', 'G', 'G', 'R', 'R', 'D', 'D', 'D', 'D', 'D']Cleaning the output
The path was correct, but I needed to make clean this output to be fast in copying the desired key. So I copyed the upper output and saved it in file1.txt and used the script replace1.py:
# Read in the file
with open('/maze/file1.txt', 'r') as file1 :
filedata = file1.read()
# Replace the target string
filedata = filedata.replace('[(0, 1), \'', ' ')
filedata = filedata.replace('\', \'', ' ')
filedata = filedata.replace('\']', ' ')
filedata = filedata.replace(' ', '')
# Write the file out again
with open('maze/file1.txt', 'w') as file1:
file1.write(filedata)And the end I got the key:
DDDDDDDDDDDRRGGRRRRDDRRRRGGRRRRRRGGRRDDDDDDLLGGLLLLDDDDLLGGLLDDLLDDRRDDLLRRRRRGGRRGGRRDDRRGGRRDDDDDIf you wouldn’t be under the time pressure and having a static maze, you could also manually write down the moves, but most probably you would make at least one mistke, becasue the maze was too big for a manual operation. Not to consider the time you would spend… Really learnt a lot from challange: BTS algorithm, find/replace script, reverse engeneering and bringing different pieces (of code) together.
Steps towards solutions
During this hands-on I got the confimration how (Python) scripting is powerful and how (basic) understanding of programming, can help you, to solve complex problems.
To recap the steps that I made:
- Found the HTML source code of the Maze.
- Copy it into a .txt file and convert it into a Binary Matrix, with the replace script.
- Then I put the Binary Matrix into the Python script, that find the path, based on the Breadth-first search algorithm.
- The output gave me the letters of the needed moves for the correct path, which I needed to “clean” it from spaces, quotes, etc. and used the replace script for the second time.
- In less than 45s I had the key to solve the CTF.
Resources:
[1] Featured Image
