Follow the white rabbit CTF – The Maze

Rabbits are afraid of Mazes.
This time our rabbit is lost and he is looking for his carrot, so you must help him.
In order to scape from the maze you must submit the whole string of movements the rabbit needs to make to reach his goal. Good Luck!
http://dev2.ctf.followthewhiterabbit.es:8008

 

Otra vez estamos limitados en tiempo, pero en este caso tenemos que resolver un laberinto, introducir las intrucciones para resolverlo y resolver un recaptcha, todo en menos de 30 segundos. Vamos a ello.

Como en este caso tenemos un recaptcha no podemos automatizar todo como en el caso del QR así que tendremos que ser rápidos para conseguir meter la solución y resolver el recaptcha. Pero vamos a ir por partes, lo primero que hice fue copiarme el código fuente de la página para hacer pruebas. Pero vamos a ir poco a poco.

Lo primero fue encontrar una manera eficaz de resolver el laberinto, en este caso el algoritmo A* es de lo mejor que pude encontrar, esta web me ayudo mucho:

http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

De paso obtenemos el algoritmo ya en python el cual tendremos que adaptar para nuestras necesidades, de paso le añadí un “parser” un poco cutre para que leyera el código de la página de un archivo y se encargara de poner el laberinto en un formato que el algoritmo entendiera. El resultado fue este script:

import heapq


class Cell(object):
    def __init__(self, x, y, reachable):
        """Initialize new cell.

        @param reachable is cell reachable? not a wall?
        @param x cell x coordinate
        @param y cell y coordinate
        @param g cost to move from the starting cell to this cell.
        @param h estimation of the cost to move from this cell
                 to the ending cell.
        @param f f = g + h
        """
        self.reachable = reachable
        self.x = x
        self.y = y
        self.parent = None
        self.g = 0
        self.h = 0
        self.f = 0


class AStar(object):
    def __init__(self):
        # open list
        self.opened = []
        heapq.heapify(self.opened)
        # visited cells list
        self.closed = set()
        # grid cells
        self.cells = []
        self.grid_height = None
        self.grid_width = None

    def init_grid(self, width, height, walls, start, end):
        """Prepare grid cells, walls.

        @param width grid's width.
        @param height grid's height.
        @param walls list of wall x,y tuples.
        @param start grid starting point x,y tuple.
        @param end grid ending point x,y tuple.
        """
        self.grid_height = height
        self.grid_width = width
        for x in range(self.grid_width):
            for y in range(self.grid_height):
                if (x, y) in walls:
                    reachable = False
                else:
                    reachable = True
                self.cells.append(Cell(x, y, reachable))
        self.start = self.get_cell(*start)
        self.end = self.get_cell(*end)

    def get_heuristic(self, cell):
        """Compute the heuristic value H for a cell.

        Distance between this cell and the ending cell multiply by 10.

        @returns heuristic value H
        """
        return 10 * (abs(cell.x - self.end.x) + abs(cell.y - self.end.y))

    def get_cell(self, x, y):
        """Returns a cell from the cells list.

        @param x cell x coordinate
        @param y cell y coordinate
        @returns cell
        """
        return self.cells[x * self.grid_height + y]

    def get_adjacent_cells(self, cell):
        """Returns adjacent cells to a cell.

        Clockwise starting from the one on the right.

        @param cell get adjacent cells for this cell
        @returns adjacent cells list.
        """
        cells = []
        if cell.x < self.grid_width-1:
            cells.append(self.get_cell(cell.x+1, cell.y))
        if cell.y > 0:
            cells.append(self.get_cell(cell.x, cell.y-1))
        if cell.x > 0:
            cells.append(self.get_cell(cell.x-1, cell.y))
        if cell.y < self.grid_height-1:
            cells.append(self.get_cell(cell.x, cell.y+1))
        return cells

    def get_path(self):
        cell = self.end
        path = [(cell.x, cell.y)]
        while cell.parent is not self.start:
            cell = cell.parent
            path.append((cell.x, cell.y))

        path.append((self.start.x, self.start.y))
        path.reverse()
        return path

    def update_cell(self, adj, cell):
        """Update adjacent cell.

        @param adj adjacent cell to current cell
        @param cell current cell being processed
        """
        adj.g = cell.g + 10
        adj.h = self.get_heuristic(adj)
        adj.parent = cell
        adj.f = adj.h + adj.g

    def solve(self):
        """Solve maze, find path to ending cell.

        @returns path or None if not found.
        """
        # add starting cell to open heap queue
        heapq.heappush(self.opened, (self.start.f, self.start))
        while len(self.opened):
            # pop cell from heap queue
            f, cell = heapq.heappop(self.opened)
            # add cell to closed list so we don't process it twice
            self.closed.add(cell)
            # if ending cell, return found path
            if cell is self.end:
                return self.get_path()
            # get adjacent cells for cell
            adj_cells = self.get_adjacent_cells(cell)
            for adj_cell in adj_cells:
                if adj_cell.reachable and adj_cell not in self.closed:
                    if (adj_cell.f, adj_cell) in self.opened:
                        # if adj cell in open list, check if current path is
                        # better than the one previously found
                        # for this adj cell.
                        if adj_cell.g > cell.g + 10:
                            self.update_cell(adj_cell, cell)
                    else:
                        self.update_cell(adj_cell, cell)
                        # add adj cell to open list
                        heapq.heappush(self.opened, (adj_cell.f, adj_cell))

import numpy
f=open("maze","rb").read()
maze=f.split("font>")[1].split("<font")[0]

maze=maze.split("<br>")
maze_final=[]
for i in maze:
    maze_final.append(i.encode("hex").replace("e296a0","1").replace("266e6273703b","0"))

maze_final[0]=maze_final[0][:1]+"01"+maze_final[0][1:]
tam=len(maze_final)-1
maze_final[tam]=maze_final[tam][1:]+"10"+maze_final[tam][:1]

line=0

dic_maze=[]
for i in maze_final:
    column=0
    for x in i:
        if x == "1":
            dic_maze.append((line,column))
        column+=1
    line+=1
#walls=tuple(dic_maze)
walls=dic_maze
maze = AStar()
maze.init_grid(37, 101, walls, (0,1), (36,99))
direcciones=maze.solve()
buff=direcciones[0]
dirs=""
for i in direcciones[1:]:
    if list(numpy.subtract(i,buff)) == [1,0]:
        dirs+="D"
    elif list(numpy.subtract(i,buff)) == [-1,0]:
        dirs+="U"
    elif list(numpy.subtract(i,buff)) == [0,1]:
        dirs+="R"
    elif listn(umpy.subtract(i,buff)) == [0,-1]:
        dirs+="L"
    buff=i
print dirs

Para evitar tener que andar seleccionando y copiando en la consola lo que hice fue utilizar xclip para que me lo copiara directamente al portapapeles y asi en cuanto el script terminara solamente tendría que copiar y resolver el captcha. Al final termine ejecuntandolo así:

nano maze; python a_star_path_finding.py | xclip -selection clipboard

Con nano y el inspect de chrome abiertos recargaba la página copiaba el código a nano y lo guardaba, y ya automaticamente el script lo resolvía y me copiaba el resultado al portapapeles, dejandonos aun ¡¡29 segundos para resolver el recaptcha!! A eso le llamo yo un conejo rápido.

Si todo fue bien este será el resultado con la flag:

Ahí podemos ver la flag:

fwhibbit{M4z3_S0lv3d_by_Sm4rt_R4bb1t}

Esta entrada fue publicada en ctf, dev, fwhibbit-ctf, python, writeups. Guarda el enlace permanente.

Deja un comentario