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
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 aaccumulative_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
fireshellteampor el CTF, realmente se disfrutó. - PENSAR ANTES DE CODEAR
Adiós <3