En un ajetreado fin de semana con un monton de asuntos pendientes adicionales, finalmente pude dedicar unas pocas horas de tiempo a las conocidas clasificatorias para el DEFCON20 CTF. Es como una maldición, siempre que he querido participar, sale algo imprevisto y quedan los deseos insatisfechos. Este año casi sucede lo mismo: propuestas urgentes para clientes, preparativos de viaje, etc. Menos mal que este año no pudieron conmigo. Participar en un equipo de una sóla persona fue divertido, pero para el proximo año definitivamente necesito más gente. Si estás interesado en formar un equipo o si tienen espacio en el suyo escríbeme por aquí.Uno de los problemas que "disfruté" mucho resolviendo fue /urandom 300. El encabezado decía algo así:
"... Aquí encontrarás tu examen final de la clase online de Algoritmos de Stanford... 140.197.217.155:5601... Password: d0d2ac189db36e15"
Al conectarnos e introducir el password, obtenemos el siguiente mensaje:
Here come 100000 uint16_t, please tell me how to sort them into
ascending order by sending me pairs of indices to exchange, one
per line, in the format: <index1>:<index2>
For example to exchange elements 123 and 9821 you should send:
123:9821
Valid indices are in the range 0..99999 inclusive. Send a blank
line when you are done. If you correctly sort the array in
sufficiently few moves I will give you a key!
You have about 10 seconds to finish, and a 5 minute wait between
succesive connections.
y luego en efecto venía el río de 100 mil números que hay que ordenar. La teoría detrás de la solución la saqué de aquí. Básicamente consiste en encontrar "subgrafos embebidos" en el arreglo de índices oredenados versus el arreglo original. Luego la solución es simplemente hacer swaps de los elementos dentro de esos subgrafos. En consecuencia, mi solución terminó siendo así:
1.- Enviar password, leer intro, leer 100 mil numeros y colocarlos en un diccionario (para facilitar el siguiente paso).
2.- Ordenar el diccionario anterior de acuerdo a los valores y crear un arreglo con los indices de los numeros originales.
3.- Crear los subgrafos embebidos inspeccionando el arreglo de indices con valores ordenados.
4.- Crear la solución de swaps de acuerdo a los subgrafos embebidos generados.
5.- Enviar la solución.
Hasta ahí todo parece perfecto. Lástima que entre la teoría y la práctica, siempre hay mucha diferencia.
El primer problema encontrado fue mi ISP. Recordemos que desde el inicio de la conexión, hasta enviar toda la respuesta, no pueden pasar más de 10 segundos. Las soluciones típicas resultaron ser de 1.2 megas, aproximadamente 90 mil swaps (como era de esperarse en un arreglo aleatorio de números). Empujar 1.2 megas por una conexión de 512 Kbps upstream, si mis cálculos son correctos, en el mejor de los casos: 19.2 segundos. Gracias CANTV.
La conexión simplemente moría antes de que mi script pudiera enviar la solución completa.
Así que el primer paso fue conseguir un shell con una conexión decente. Gracias a mis colegas (Freddy) siempre dispuestos a ayudar a un amigo!
Luego de una conexión decente, todo el intercambio duraba menos de 3 segundos. Sin embargo, el siguiente problema fue un mensaje como el siguiente:
"... Felicitaciones, tus comandos han producido un arreglo ordenado correctamente. Sin embargo, has utilizado demasiados intercambios. Que tengas mejor suerte la proxima vez..."
Este es el "momento WTF". ¿Cómo es eso que "mejor suerte"? mi algoritmo es determinístico! aquí no hay nada de suerte. A pesar de que el mensaje de "mejor suerte" estaba obviamente dirigido a "fastidiarte", en efecto fue bastante útil. Al meditar unos minutos sobre cómo la suerte no podía influir me di cuenta del problema!
En mi solución, por flojo o por apurado, (no importa, mismo resultado), utilicé una libreria de python para ordenar el arreglo original. En consecuencia, era posible que si en el arreglo original había algún número repetido, el algoritmo de ordenamiento podría intercambiar posiciones de números iguales que no eran necesarias, sobre todo si la posición del número repetido ya estaba en la posición ordenada final. Entonces la suerte SI! tenía que ver. Mi algoritmo fallaría cuando los anteriores eventos coincidían. Sabiendo que en una elección de números aleatorios esos eventos juntos no deberían ser tan frecuentes, simplemente ejecuté mi solución varias veces. Despues de 2 mensajes de falla, a la tercera fue la vencida:
"Congratulations, your final array is sorted correctly.
Here is your key: a7482ddfb82601fdc392b67836883dcc"
UPDATE: Algunos me han pedido ver código, asi que he decidido postearlo. Advertencia: Esto es lo que pasa cuando programas apurado. Código muy horrible sigue (lol):
#! /usr/bin/python -u
import socket,operator,time
SERVER_HOST = 'localhost'
SERVER_PORT = 10000
#SERVER_HOST = "140.197.217.155"
#SERVER_PORT = 5601
PASSWORD = 'd0d2ac189db36e15'
def show_time(start):
res = time.time()
print "elapsed:",str(res - start)
return res
def send_msg(s,m):
s.send(m+"\x0a")
def recv_msg(s):
c = "d"
r = ""
while 1:
c = s.recv(1)
if not c:
break
r += c
return r
c = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
c.connect((SERVER_HOST,SERVER_PORT))
start_t = show_time(time.time())
p = c.recv(10)
print p,
send_msg(c,PASSWORD)
print PASSWORD
header = c.recv(0x1F8)
print header
start_t = show_time(start_t)
numbers = ""
for rr in xrange(100000):
numbers += c.recv(2)
print "length(numbers):", len(numbers)
start_t = show_time(start_t)
lista = {}
for x in xrange(100000):
try:
# raw = c.recv(2).encode('hex')
raw = numbers[2*x:2*x+2].encode('hex')
network_byte_order = int(raw,16)
# print "received:",raw
num = socket.ntohs(network_byte_order)
except :
print "Raw:",raw
print "network_byte_order:",network_byte_order
print "Total:",x
raise Exception("Connection Closed")
lista[x] = num
#lista = {0:3,1:2,2:4,3:0,4:1,5:5} # Check really small case.
print "length lista:",len(lista)
#print lista
start_t = show_time(start_t)
print "started sorting"
sorted_x = sorted(lista.iteritems(),key=operator.itemgetter(1))
sorted_indices = [x[0] for x in sorted_x]
print "ended sorting"
start_t = show_time(start_t)
print "constructing sol"
indices = [False for r in xrange(100000)]
res = ""
for count in xrange(len(lista)):
if indices[count]:
continue
base = count
current = count
indices[current] = True
next_i = sorted_indices[current]
indices[next_i] = True
while next_i != base:
# print str(current)+":"+str(next_i)
res += str(current)+":"+str(next_i)+"\x0a"
current = next_i
next_i = sorted_indices[current]
indices[next_i] = True
# print "End of embeded subgraph"
start_t = show_time(start_t)
print "sending answer"
try:
c.send(res+"\x0a")
except socket.error, (value,message):
print "oops didnt unload all:",message
start_t = show_time(start_t)
print "answer:",recv_msg(c)
