bi0sCTF 2024 — A Block and a Hard Place
Are you the Far Lands because you're a Maze? Or are you a Maze because you're the Far Lands?
We're given a terminal prompt that looks like this:
It looks like we're blindly navigating some sort of "maze", with walls blocking regular movement between certain cells.
As a first order of business, we should probably map out what this maze looks like. We can represent each maze position as a 2x2 grid, where the right and bottom two cells represent whether there is a wall to the right or bottom of the cell, respectively:
Code:
1.. .X .. .X
2.. .X XX XX(we don't need to check for left or top walls as we'll have already found them when iterating over other positions.)
Then, writing a python script to map out the maze's walls, printing one row of the maze at a time,[^1]
Code (py):
1import pwn
2import numpy as np
3
4conn = pwn.remote('13.201.224.182', 32545)
5SIZE = 36 * 2
6
7
8def print_buf(grid: np.ndarray):
9 for row in grid:
10 print(''.join('█' if e else ' ' for e in row))
11
12
13def goto_top():
14 while True:
15 conn.sendlineafter(b'> ', b'w')
16 if conn.recvline().decode().strip() != 'Moved!':
17 conn.sendlineafter(b'> ', b'W')
18 if conn.recvline().decode().strip() != 'Jumped over a wall!':
19 break
20
21
22def goto_left():
23 while True:
24 conn.sendlineafter(b'> ', b'a')
25 if conn.recvline().decode().strip() != 'Moved!':
26 conn.sendlineafter(b'> ', b'A')
27 if conn.recvline().decode().strip() != 'Jumped over a wall!':
28 return
29
30
31def check_floor(x: int, grid: np.ndarray):
32 conn.sendlineafter(b'> ', b's')
33 if conn.recvline().decode().strip() != 'Moved!':
34 grid[1, x] = 1
35 grid[1, x + 1] = 1
36 else:
37 conn.sendlineafter(b'> ', b'w')
38
39
40def map_line_right():
41 grid = np.zeros((2, SIZE), dtype=np.uint8)
42 x = 0
43
44 while True:
45 check_floor(x, grid)
46
47 conn.sendlineafter(b'> ', b'd')
48 if conn.recvline().decode().strip() != 'Moved!':
49 conn.sendlineafter(b'> ', b'D')
50
51 if conn.recvline().decode().strip() != 'Jumped over a wall!':
52 conn.sendlineafter(b'> ', b's')
53 print_buf(grid)
54 return
55 else:
56 grid[0, x + 1] = 1
57 grid[1, x + 1] = 1
58
59 x += 2
60
61
62def map_line_left():
63 grid = np.zeros((2, SIZE), dtype=np.uint8)
64 x = SIZE
65
66 while True:
67 check_floor(x, grid)
68
69 conn.sendlineafter(b'> ', b'a')
70 if conn.recvline().decode().strip() != 'Moved!':
71 conn.sendlineafter(b'> ', b'A')
72
73 if conn.recvline().decode().strip() != 'Jumped over a wall!':
74 conn.sendlineafter(b'> ', b's')
75 print_buf(grid)
76 return
77 else:
78 grid[0, x - 1] = 1
79 grid[1, x - 1] = 1
80
81 x -= 2
82
83
84goto_top()
85goto_left()
86
87# Skip top padding
88for i in range(3):
89 conn.sendlineafter(b'> ', b's')
90
91for i in range(0, SIZE, 2):
92 map_line_right()
93 map_line_left()[^1]: A bit sloppy, but we're somewhat forced to print the buffer before reading the next line instead of printing it all at the end because traversing the maze takes so long the connection times out (crashing the program) before the entire process is done.
we get
Code:
1
2 ██████████████ ████ ██ ████ ████████ ██████████████
3 █ █ █ █ █ █ █ █ █ █ █ █
4 █ ██████████ █ █ ██ █ █████ █ █ ██████ █ ██████████ █
5 █ █ █ █ █ █ █ █ █ █ █ █ █ █
6 █ █ ██████ █ █ █ █ ██ ██████████ █ █ █ ██████ █ █
7 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
8 █ █ █ █ █ █ █ ███████ ██ ███ ██ █ █ █ █ █ █
9 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
10 █ █ █ █ █ █ █ █████ ██ ███ ████ ███ █ █ █ █ █ █
11 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
12 █ █ ███████ █ █ █████ ███ █ ███ █ █ ███████ █ █
13 █ █ █ █ █ █ █ █ █ █
14 █ ███████████ █ ██ █ ██ ████ ██ ██ ██ █ ███████████ █
15 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
16 ███████████████ █ ███ █████████ █ █ █ █████ ███████████████
17 █ █ █ █ █ █ █ █
18 ██ ██ ████ █ ██ █ █ ██ █ █ ████████ ██████████
19 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
20 ██ ███ █ █████ █ █████ █ █ ██ █ ███ ███ ██ ██
21 █ █ █ █ █ █ █ █ █ █
22 █████ ████████ █ ████ ██ █ █ ███ ███████ ██ ██████ █
23 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
24 ██ █████████ ███ ██ █████ █████ ████████ ███ █████ ███
25 █ █ █ █ █ █ █ █
26 █ ██████ ██████ █ ██████ ████ █ ██████ ████ █ ████
27 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
28 ███ █ █████ ██ ███ █ ███ ██ ███ █ ███ ██ ███
29 █ █ █ █ █ █ █ █
30 ██ █ ███████ ██ █ ████ ██ █ ████ ██
31 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
32 ██ ███ █ ████ ███ ███ █ █████ ██ █ ███ █████ ██████
33 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
34 █ █ ██████ ███████ █ ██ ███ █████ ███ █ ███ █ █████
35 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
36 ███████████████ ██ █████████ ██████ ██ █ ███████ █ ████
37 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
38 ███ █ █ ██ ███ ██████ ████ █ ███ █ █ █ ███
39 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
40 ██████ ███ ██ █ █ █ ███ ███ ████ ██ ██ ███ ██
41 █ █ █ █ █ █ █ █ █ █ █ █ █ █
42 ██████████████ ███ ███ █ ██ ████ ███ ███████ █████ ████
43 █ █ █ █ █ █ █ █ █ █ █ █
44 █████ ███████ ██ ████ █ █ █ ██ ██ ██████ ███ █
45 █ █ █ █ █ █ █ █ █ █ █ █
46 ██████████████ █████████ █████ █ █ █████ █ ██ █ ██ ███
47 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
48 █ ██████████ █ ██████ █ ████████ ██ █ █ ███ █ ███ ██
49 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
50 █ █ ██████ █ █ ███ █ █ █ █ █ ████ █ █ ███████ ████
51 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
52 █ █ █ █ █ █ ██████ █ █████ ███ █ ████ ██ ██ █████
53 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
54 █ █ █ █ █ █ ███ █ ████ █ ██ ██ ███████████ ███ ████
55 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
56 █ █ ███████ █ █ ██ █████ █ █ █ █ ███ ██ █████ █ █████
57 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
58 █ ███████████ █ █████ █████████ █ █ █ ██ █ ███ ████
59 █ █ █ █ █ █ █ █ █ █ █ █ █ █
60 ███████████████ ███ ███ █████ ███ ███ ███Looks a bit like a QR code, doesn't it? 🤔
First, though, we need to fix up all of the top-left corners which got messed up by the traversal algorithm. Doing so yields
Code:
1
2 ███████████████ █████ ███ █████ █████████ ███████████████
3 █ █ █ █ █ █ █ █ █ █ █ █
4 █ ███████████ █ █ ███ █ █████ █ █ ███████ █ ███████████ █
5 █ █ █ █ █ █ █ █ █ █ █ █ █ █
6 █ █ ███████ █ █ █ █ ███ ███████████ █ █ █ ███████ █ █
7 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
8 █ █ █ █ █ █ █ ███████ ███ ███ ███ █ █ █ █ █ █
9 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
10 █ █ █ █ █ █ █ █████ ███ ███ █████ ███ █ █ █ █ █ █
11 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
12 █ █ ███████ █ █ █████ ███ █ ███ █ █ ███████ █ █
13 █ █ █ █ █ █ █ █ █ █
14 █ ███████████ █ ███ █ ███ █████ ███ ███ ███ █ ███████████ █
15 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
16 ███████████████ █ ███ █████████ █ █ █ █████ ███████████████
17 █ █ █ █ █ █ █ █
18 ███ ███ █████ █ ███ █ █ ███ █ █ █████████ ███████████
19 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
20 ███ ███ █ █████ █ █████ █ █ ███ █ ███ ███ ███ ███
21 █ █ █ █ █ █ █ █ █ █
22 █████ █████████ █ █████ ███ █ █ ███ ███████ ███ ███████ █
23 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
24 ███ █████████ ███ ███ █████ █████ █████████ ███ █████ ███
25 █ █ █ █ █ █ █ █
26 █ ███████ ███████ █ ███████ █████ █ ███████ █████ █ █████
27 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
28 ███ █ █████ ███ ███ █ ███ ███ ███ █ ███ ███ ███
29 █ █ █ █ █ █ █ █
30 ███ █ ███████ ███ █ █████ ███ █ █████ ███
31 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
32 ███ ███ █ █████ ███ ███ █ █████ ███ █ ███ █████ ███████
33 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
34 █ █ ███████ ███████ █ ███ ███ █████ ███ █ ███ █ █████
35 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
36 ███████████████ ███ █████████ ███████ ███ █ ███████ █ █████
37 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
38 ███ █ █ ███ ███ ███████ █████ █ ███ █ █ █ ███
39 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
40 ███████ ███ ███ █ █ █ ███ ███ █████ ███ ███ ███ ███
41 █ █ █ █ █ █ █ █ █ █ █ █ █ █
42 ███████████████ ███ ███ █ ███ █████ ███ ███████ █████ █████
43 █ █ █ █ █ █ █ █ █ █ █ █
44 █████ ███████ ███ █████ █ █ █ ███ ███ ███████ ███ █
45 █ █ █ █ █ █ █ █ █ █ █ █
46 ███████████████ █████████ █████ █ █ █████ █ ███ █ ███ ███
47 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
48 █ ███████████ █ ███████ █ █████████ ███ █ █ ███ █ ███ ███
49 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
50 █ █ ███████ █ █ ███ █ █ █ █ █ █████ █ █ ███████ █████
51 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
52 █ █ █ █ █ █ ███████ █ █████ ███ █ █████ ███ ███ █████
53 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
54 █ █ █ █ █ █ ███ █ █████ █ ███ ███ ███████████ ███ █████
55 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
56 █ █ ███████ █ █ ███ █████ █ █ █ █ ███ ███ █████ █ █████
57 █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
58 █ ███████████ █ █████ █████████ █ █ █ ███ █ ███ █████
59 █ █ █ █ █ █ █ █ █ █ █ █ █ █
60 ███████████████ ███ ███ █████ ███ ███ ███Resizing the image in Photoshop to make the corner boxes more square-like, we get an interesting pattern that looks like this:
<p align="center"> <img src="https://gist.github.com/assets/60120929/e9d7885e-0836-4e5e-958b-653ec5ae846d" width="600px"> </p>The key realization here is that the corners of a valid QR code should consist of a single ring around solid block of black:
<p align="center"> <img src="https://gist.github.com/assets/60120929/7414e9dd-0823-4118-9d52-f0fd287e7489" width="300px"> </p>Because the walls lie between cells, it's clear now that the walls of the maze separate regions of different color in the QR code. Then, this challenge turns into a sort of "A/B coloring" problem solvable with the following routine:
- Keep a state tracking the current "color": white/black (or filled/unfilled)
- Iterate over all cells, painting each cell the current color.
- When the program hits a wall in the maze while iterating, swap the current color.
Modifying our traversal script with the given algorithm,
Code (py):
1import pwn
2
3conn = pwn.remote('13.201.224.182', 32323)
4fill = False
5
6
7def goto_top():
8 while True:
9 conn.sendlineafter(b'> ', b'w')
10 if conn.recvline().decode().strip() != 'Moved!':
11 conn.sendlineafter(b'> ', b'W')
12 if conn.recvline().decode().strip() != 'Jumped over a wall!':
13 break
14
15
16def goto_left():
17 while True:
18 conn.sendlineafter(b'> ', b'a')
19 if conn.recvline().decode().strip() != 'Moved!':
20 conn.sendlineafter(b'> ', b'A')
21 if conn.recvline().decode().strip() != 'Jumped over a wall!':
22 return
23
24
25def map_line_right() -> str:
26 global fill
27 ret = ''
28
29 while True:
30 conn.sendlineafter(b'> ', b'd')
31 ret += '█' if fill else ' '
32
33 if conn.recvline().decode().strip() != 'Moved!':
34 conn.sendlineafter(b'> ', b'D')
35
36 if conn.recvline().decode().strip() != 'Jumped over a wall!':
37 conn.sendlineafter(b'> ', b's')
38 return ret
39 else:
40 fill = not fill
41
42
43def map_line_left() -> str:
44 global fill
45 ret = ''
46
47 while True:
48 conn.sendlineafter(b'> ', b'a')
49 ret += '█' if fill else ' '
50
51 if conn.recvline().decode().strip() != 'Moved!':
52 conn.sendlineafter(b'> ', b'A')
53
54 if conn.recvline().decode().strip() != 'Jumped over a wall!':
55 conn.sendlineafter(b'> ', b's')
56 return ret[::-1]
57 else:
58 fill = not fill
59
60
61goto_top()
62goto_left()
63
64# Skip top padding
65for i in range(4):
66 conn.sendlineafter(b'> ', b's')
67
68while True:
69 print(map_line_right())
70 print(map_line_left())we get
Code:
1 ███████ ██ █ ██ ████ ███████
2 █ █ █ █████ █ █ █
3 █ ███ █ █ ██ ██ █ ███ █
4 █ ███ █ ██ ████ █ █ ███ █
5 █ ███ █ ████ █ █ █ ███ █
6 █ █ ████ █ █
7 ███████ █ █ █ █ █ █ █ ███████
8 ████ █ █ ██
9 █ █ ██ ███ █ ██ █ ███ █████
10 ████ ██████ █ ███████ ██
11 █ ███ █ █ █ ██ █ █ █ █
12 ███ ███ ███ ███
13 █ █ ███ █ █ ██ █ █ ██ █
14 ██ █ ███ ███
15 █ ███ █ █ ██ █ █ ██ █ █
16 █ ██ ███ ███ ██ ██ █ █
17 █ ██ ██ █ █ ███████ ███ ██
18 █ █ ███ ███ █ █ █ █
19 █ █ █ █ █ █ ███ █
20 ██ ██ █ █ █ █ █
21 ██ ███ ███ █ ███████████ █
22 ██ █ █ █ ██ ████
23 ███████ ██ ██ ██ █ █ █ ███
24 █ █ ██ █ █ ██ █ ████
25 █ ███ █ █ █ █ █ █ ███████ █
26 █ ███ █ █ ██ ████ █ █ ██ ██
27 █ ███ █ █ █ █ █ █ █ ███ █
28 █ █ █ ██ █ ██ ███ ████
29 ███████ █ █ ██ █ █ █ which we can scan to get the flag.
Code:
1bi0sctf{cZrfONl+bGtGiKWMnnR5Sg==}