[CTF] WU - Dwarf Fortress! 🏰

Difficulty Level : Hard

Challenge Category : Web

Description :

Trapped in a dark, abandoned mine, your mission is to find the exit. Use the cryptic map and solve puzzles hidden in the tunnels. Beware of false leads—only a sharp mind will uncover the way out. Can you escape?Solution Steps

Solution Steps

Step 1: Understand the Problem

1. The maze is represented as a grid-based PNG image.
2. Each cell in the grid represents:
   • Path: Navigable.
   • Wall: A barrier that can only be breached using a limited number of demolition charges.
   • Start/End: Defined entry and exit points on the left and right edges of the maze.
3. The solution involves:
   • Downloading the PNG.
   • Parsing the maze into a grid representation.
   • Navigating from the start to the exit using a recursive search algorithm.
   • Submitting the solution back to the server.

Step 2: Implement the Solver

The solution involves a Python script (exploit.py) to automate the entire process.

Key Components of the Script

1. Maze Representation:

   • The maze is represented as a grid, with each cell derived from the PNG image using Pillow (PIL).

2. Recursive Maze Solver:

   • The solver checks all valid moves from the current position:
     • North, South, East, West.
     • Breaches walls if demolition charges are available.
   • It uses a depth-first search approach to find a solution path.

3. Wall Breaching:

   • The solver tracks the number of demolition charges remaining.
   • Walls are breached if no other paths are available.

4. Submission:

   • The solution is submitted to the server via a POST request.

Step 3: Script Walkthrough

Main Functions

1. Retrieve the Maze:

   def get_chall():
       r = requests.get(f"{URL}{UPLOAD}")
       COOKIES = r.cookies
       chall_buffer = io.BytesIO(r.content)
       chall_img = Image.open(chall_buffer)
       return chall_img
   

2. Parse Start/Exit Points:

   def get_start_cell():
       for cell_y in range(HEIGHT):
           if CHALL_PNG[cell_to_pixel(0), cell_to_pixel(cell_y)] != BACKGROUND_COLOR:
               return (0, cell_y)
       return None
   
   def get_exit_cell():
       for cell_y in range(WIDTH)[::-1]:
           if CHALL_PNG[cell_to_pixel(HEIGHT - 1), cell_to_pixel(cell_y)] != BACKGROUND_COLOR:
               return (HEIGHT - 1, cell_y)
       return None
   

3. Recursive Solver:

   def explore(cell_x, cell_y, path, visited, breacher_count):
       if cell_x == EXIT_CELL[0] and cell_y == EXIT_CELL[1]:
           return path
   
       neighbors = get_neighbors(cell_x, cell_y, path[-1] if path else '', visited, breacher_count)
       for neighbor in neighbors:
           new_path = explore(*neighbor)
           if new_path:
               return new_path
   
       return None
   

4. Test Solution:

   def test_solution(solution):
       r = requests.post(URL, data={POST_TAG: solution}, cookies=COOKIES)
       flag = re.search(FLAG_REGEX, r.text)
       return html.unescape(flag.group(1)) if flag else None
   

Step 4: Run the Script

1. Save the script as exploit.py.
2. Execute it with the target IP and port:

   python3 exploit.py <target_ip> <port>
   

exploit.py :

#!/usr/bin/python3

import requests
import sys
import re
import time
import io
import html

from PIL import Image

URL = None
UPLOAD = '/challenge_accepted'

COOKIES = None
POST_TAG = 'maze_solution'
FLAG_REGEX = 'The flag is: (.+)'

WIDTH = 80
HEIGHT = 80
CELL_SIZE = 50

BACKGROUND_COLOR = (255, 255, 255)
WALL_COLOR = (0, 0, 0)

CHALL_PNG = None
EXIT_CELL = (None, None)

BREACHER_COUNT = 1

def get_chall():
    '''
    Retrieve the chall PNG file.
    We do it in memory in order to be fastest (we only have a limited amount of seconds).
    '''
    global COOKIES

    r = requests.get("%s%s" % (URL,UPLOAD))
    COOKIES = r.cookies

    chall_buffer = io.BytesIO(r.content)

    chall_img = Image.open(chall_buffer)

    return chall_img

def get_start_cell():
    '''
    Returns the starting cell.
    '''

    # The starting cell is always on the left side of the maze (and in the top side of the maze).
    for cell_y in range(HEIGHT):
        pixel_x = cell_to_pixel(0)
        pixel_y = cell_to_pixel(cell_y)

        if CHALL_PNG[pixel_x,pixel_y] != BACKGROUND_COLOR:
            return (0,cell_y)

    return None

def get_exit_cell():
    '''
    Returns the exit cell.
    '''

    # The exit cell is always on the right side of the maze (and in the bottom side of the maze).
    for cell_y in range(WIDTH)[::-1]:
        pixel_x = cell_to_pixel(HEIGHT-1)
        pixel_y = cell_to_pixel(cell_y)

        if CHALL_PNG[pixel_x,pixel_y] != BACKGROUND_COLOR:
            return (HEIGHT-1,cell_y)

    return None

def get_neighbors(cell_x, cell_y, last_move, visited, breacher_count):
    '''
    Returns the possible neighbors and ignore the last move.
    '''

    neighbors = []   
    offset = CELL_SIZE//2

    # Check north wall
    if (cell_x, cell_y - 1) not in visited:
        if last_move != 's' and CHALL_PNG[cell_to_pixel(cell_x), cell_to_pixel(cell_y) - offset] != WALL_COLOR:
            neighbors += [(cell_x, cell_y - 1, 'n', visited|{(cell_x, cell_y - 1)}, breacher_count)]
        elif breacher_count > 0 and (cell_y - 1) >= 0:
            neighbors += [(cell_x, cell_y - 1, 'bn', visited|{(cell_x, cell_y - 1)}, breacher_count - 1)]

    # Check south wall
    if (cell_x, cell_y + 1) not in visited:
        if last_move != 'n' and CHALL_PNG[cell_to_pixel(cell_x), cell_to_pixel(cell_y) + offset - 1] != WALL_COLOR:
            neighbors += [(cell_x, cell_y + 1, 's', visited|{(cell_x, cell_y + 1)}, breacher_count)]
        elif breacher_count > 0 and (cell_y + 1) < HEIGHT :
            neighbors += [(cell_x, cell_y + 1, 'bs', visited|{(cell_x, cell_y + 1)}, breacher_count - 1)]

    # Check east wall
    if (cell_x + 1, cell_y) not in visited:
        if last_move != 'w' and CHALL_PNG[cell_to_pixel(cell_x) + offset - 1, cell_to_pixel(cell_y)] != WALL_COLOR:
            neighbors += [(cell_x + 1, cell_y, 'e', visited|{(cell_x + 1, cell_y)}, breacher_count)]
        elif breacher_count > 0 and (cell_x + 1) < WIDTH:
            neighbors += [(cell_x + 1, cell_y, 'be', visited|{(cell_x + 1, cell_y)}, breacher_count - 1)]

    # Check west wall
    if (cell_x - 1, cell_y) not in visited:
        if last_move != 'e' and CHALL_PNG[cell_to_pixel(cell_x) - offset, cell_to_pixel(cell_y)] != WALL_COLOR:
            neighbors += [(cell_x - 1, cell_y, 'w', visited|{(cell_x - 1, cell_y)}, breacher_count)]
        elif breacher_count > 0 and (cell_x - 1) >= 0:
            neighbors += [(cell_x - 1, cell_y, 'bw', visited|{(cell_x - 1, cell_y)}, breacher_count - 1)]

    return neighbors

def cell_to_pixel(cell_coord):
    '''
    Cell value to PNG coordinate.
    '''

    return CELL_SIZE//2 + cell_coord*CELL_SIZE

def pixel_to_cell(pixel_coord):
    '''
    Value in the PNG file to cell coordinate.
    '''

    return pixel_coord//CELL_SIZE

def test_solution(solution):
    '''
    Test a solution and grab the flag.
    '''

    r = requests.post(URL, data={POST_TAG:solution}, cookies=COOKIES)

    flag = re.search(FLAG_REGEX, r.text)
    if flag != None:
        return html.unescape(flag.group(1))

    return None

def explore(cell_x, cell_y, path, visited, breacher_count):
    '''
    Recursively explore the maze until a path is found.
    '''
    solution = None

    last_move = ''
    if len(path) > 0:
        last_move = path[-1]

    # Test if we are on the exit cell
    if cell_x == EXIT_CELL[0] and cell_y == EXIT_CELL[1]:
        return path

    neighbors = get_neighbors(cell_x, cell_y, last_move, visited, breacher_count)
    for (new_cell_x, new_cell_y, move, new_visited, new_breacher_count) in neighbors:
        tmp = explore(new_cell_x, new_cell_y, "%s%s" % (path, move), new_visited, new_breacher_count)
        if tmp != None:
            return tmp

    return solution

def exploit():
    '''
    Main function used to exploit the challenge.
    '''
    global CHALL_PNG
    global EXIT_CELL

    start_time = time.time()

    img = get_chall()
    #img.show()

    CHALL_PNG = img.load()

    # Get the starting and exit cells
    (start_cell_x,start_cell_y) = get_start_cell()
    EXIT_CELL = get_exit_cell()

    # In order to avoid : "RuntimeError: maximum recursion depth exceeded"
    sys.setrecursionlimit(WIDTH * HEIGHT)

    solution = explore(start_cell_x, start_cell_y, '', set(), BREACHER_COUNT)

    print("Solution: %s" % solution)

    print("Time elapsed: %s" % (time.time() - start_time))

    return test_solution(solution)

def main():
    global URL

    if len(sys.argv) != 3 and len(sys.argv) != 4:
        print("Usage: %s <target_ip> <port>" % sys.argv[0])
        exit(1)

    URL = "http://%s:%s" % (sys.argv[1], sys.argv[2])

    flag = exploit()

    print("Khazuk, Khazuk-ha! The flag is: %s" % flag)

if __name__=='__main__':
    main()