f4d3

f4d3

InfoSec enthusiast | pwn | RE | CTF | BugBounty

fireshell{dungeon escape}

Dungeon escape V2 writeup (PPC)

Hola! Este fin de semana, participamos como equipo en el CTF organizado por fireshellsecurity, obteniendo un piola, 7mo lugar

scoreboard

El CTF en general estuvo entretenido, 24hrs de diversos retos, incluyendo misc QUEST's de discord, que luego de haber fallado resolviéndolo, fue muy interesante leer el writeup.

Summary

Al conectarse por netcat al servidor, este respondía el banner, la explicación del desafío y el espacio para comenzar a jugar:


                +++     Fireshell CTF - DUNGEON ESCAPE     +++

 [+] After being caught committing crimes, you were locked up in a really strange
     dungeon. You found out that the jailer is corrupt and after negotiating
     with him, he showed to you a map with all the paths and the necessary time
     to cross each one, and explained to you how the dungeon works. In some
     parts of the dungeon, there are some doors that only open periodically. The
     map looks something like this:

                4              +-+      1
        +----------------------+3+-------------+
       +-+                     +-+             |
       |C|                              2     +++     4
       +++                  +-----------------+7+--------------------+
        |           3      +-+                +-+                    |
        +------------------+4|        12                            +++
                           +-+--------------------------------------+E|
                                                                    +-+

 [+] All doors start at time zero together and if a door has time equals to 3,
     this door will open only at times 0, 3, 6, 9, ... So if you reach a door
     before it is open, you will need to wait until the door is open.

 [+] So, with a map you organized the infos like the following: first it will be
     the number of doors and the number of paths. Second it will be a list with
     the time of all doors. After that each line will contains a path with the
     time needed to walk this path. For the last it will be the position of your
     cell (C) and the postion where it is the exit (E).

 [+] The jailer said that if you find out the minimum time from your cell to the
     exit, he will set you free. In the example, the minimum time is 11.

 [+] Type 'start' for try to runaway:

5 6         doors/paths
1 4 3 7 1   time of all doors
1 2 3       path / time needed
1 3 4
2 4 2
3 4 1
2 5 12
4 5 4
1 5

En pocas palabras:

  • Eres un prisionero el cual necesita llegar por el camino más corto posible a la salida, y la salida sólo se abrirá si efectivamente tomaste el camino más corto, en cada cambio de camino (nodo), habrán puertas, con tiempos de apertura respectivos, las cuales solo se abrirán en múltiplos de determinado tiempo, si se logra llegar en el mínimo tiempo posible a la salida Exit, se logrará pasar al siguiente desafío.

Al leerlo en primera instancia, estaba claro que era un problema de grafos, podríamos interpretar cada puerta como un nodo y cada camino, como la conexión respectiva.

Cuando recién lo leí, me lancé de cabeza a conseguir los path's posibles (DFS), y luego calcular el tiempo, lo malo, es que mi solución moría en el intento 20, cláramente no iba por ahí.
Luego, pensando con la cabeza un poco más fría, la solución siempre estuvo al frente, es un problema de Grafos con pesos, el cual se podrá representar y solucionar con dijkstra, el problema, es que el sistema de pesos aquí no es el usual (las puertas añaden un poco de dificultad), pero, el peso acumulado, podría ser representado de la siguiente manera:

  • Si se llega a una puerta con un peso :

  • Esto implicará que sí o sí tendremos que esperar a la próxima apertura de puerta, por lo tanto el peso vendría a ser accumulative_weight = door_time.

  • Si llegamos a una puerta con un peso:

  • Implicará que sí o sí tendremos que esperar a la próxima apertura de la puerta, siendo la próxima apertura, el múltimo de door_time, más próximo a accumulative_weight, lo hice de la manera más garka que se me ocurrió, traducido a esto:

Solución

  • El primer objetivo es codear un disjktra:

def dijkstra(edges,start,target,doors):

    # Make lal distances inf and the start to 0
    distances = {vertex: float('inf') for vertex in edges}
    distances[start] = 0

    pq = [(0,start)]
    # Starting dijkstra
    while len(pq) > 0:
        current_distance, current_vertex = heapq.heappop(pq)
        # Just proccess the vertex the first time that is removed
        #
        if current_distance > distances[current_vertex]:
            # We move to one node
            continue
        for neigh, weight in edges[current_vertex].items():
            distance = current_distance + weight
            # Just consideer this path if is the better one that already found
            if distance < distances[neigh]:
                distances[neigh] = distance
                heapq.heappush(pq, (distance, neigh))

    return distances

De aquí, debemos tener especial cuidado con los pesos, aplicando los 2 puntos que dije anteriormente, por lo que cambiaría a la siguiente forma:

def dijkstra(edges,start,target,doors):

    # Make lal distances inf and the start to 0
    distances = {vertex: float('inf') for vertex in edges}
    distances[start] = 0

    pq = [(0,start)]
    # Starting dijkstra
    while len(pq) > 0:
        current_distance, current_vertex = heapq.heappop(pq)
        # Just proccess the vertex the first time that is removed
        #
        if current_distance > distances[current_vertex]:
            # We move to one node
            continue
        for neigh, weight in edges[current_vertex].items():
            distance = manual(current_distance + weight, doors[neigh-1])
            #distance = current_distance + weight
            # Just consideer this path if is the better one that already found
            if distance < distances[neigh]:
                distances[neigh] = distance
                heapq.heappush(pq, (distance, neigh))

    return distances

  • Ahora, lo que queda, es sólo interactuar con el servicio remoto:


import heapq
from pwn import *


def manual(number,base):
    ret = base
    if base >= number:
        return base
    for k in range(number/base, number/base + 10):
        ret = base*k
        if ret >= number:
            return int(ret)


def dijkstra(edges,start,target,doors):

    # Make lal distances inf and the start to 0
    distances = {vertex: float('inf') for vertex in edges}
    distances[start] = 0

    pq = [(0,start)]
    # Starting dijkstra
    while len(pq) > 0:
        current_distance, current_vertex = heapq.heappop(pq)
        # Just proccess the vertex the first time that is removed
        #
        if current_distance > distances[current_vertex]:
            # We move to one node
            continue
        for neigh, weight in edges[current_vertex].items():
            # the 2 points that I said
            distance = manual(current_distance + weight, doors[neigh-1])
            #distance = current_distance + weight
            # Just consideer this path if is the better one that already found
            if distance < distances[neigh]:
                distances[neigh] = distance
                heapq.heappush(pq, (distance, neigh))

    return distances



print "---* Dungeon escape Solution (dijkstra version) *---"


c = remote('142.93.113.55', 31085)


received = c.recvuntil('runaway:')

c.send('start')
c.recvline()
print c.recvline()
print c.recvline()
print c.recvline()

while True:
    doors_paths = c.recvline().strip().split(' ')
    time_of_doors = c.recvline().strip().split(' ')
    time_of_doors = map(int,time_of_doors)
    paths = []
    just_graph = {}
    for_nx = []
    a_m = {}
    newone = {}
    for j in range(int(doors_paths[1])):
        line = c.recvline().strip().split(' ')
        line = map(int, line)
        s,t,w = line
        if s not in newone:
            newone[s] = {}
        if t not in newone:
            newone[t] = {}
        newone[s][t] = w
        newone[t][s] = w
        paths.append((line[0], line[1], line[2]))

    C,E = map(int,c.recvline().strip().split(' '))
    print """doors and paths {}
    time of doors {}
    paths {}
    C,E {} {}""".format(doors_paths, time_of_doors, paths, C,E)

    result =  dijkstra(newone,C,E,time_of_doors)[E]

    print "better time is: {}".format(result)
    #exit(1)
    c.sendline(str(int(result)))

    print c.recvline()
    print c.recvline()
    print c.recvline()
    print c.recvline()

Con esto, pasamos de buena manera hasta el final challenge, obteniendo así, la flag:

Conclusión

  • Gracias a fireshellteam por el CTF, realmente se disfrutó.
  • PENSAR ANTES DE CODEAR

Adiós <3