PHDays CTF Quals 2012 –
Misc 400

Für diese interessante Aufgabe (Misc 400) gab es nicht viele Informationen:

PHDays CTF 2012 - Misc 400 - task description

Als erstes bietet es sich an, sich mit Hilfe von netcat einen Überblick über die Aufgabe zu verschaffen. Nachdem man sich mit ctf.phdays.com:1165 verbunden hat, bekommt man folgende Ausgabe:

Hi there! Stupid CAPTCHA: enter your name, user61758

Hier ist verlangt, user61758 als Antowort zurück zu geben, da sich sonst das Programm beendet. Jetzt muss man eine gewisse Zeit warten, bis sich der Server wieder meldet. Ob diese Wartezeit beabsichtigt oder der Server einfach nur ausgelastet war, weiss ich leider nicht.

Der Server antwortet mit einem Labyrinth, das aus 50 solcher Ebenen besteht:

PHDays CTF 2012 - Misc 400 - maze

Danach fordert uns der Server auf:

“Find a path between (…, …, …) and (…, …, …)”

Die Aufgabe bestand also darin, einen Pfad von Punkt A nach Punkt B zu finden. Dafür habe ich ein Skript geschrieben, welches das Labyrinth parst und dann auch löst.

#!/usr/bin/env python2.6

import socket
import re
import time

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("ctf.phdays.com", 1165))

line = sock.recv(1024)
username = line.strip().split(',')[1].strip()
sock.sendall("%s\n"%(username))

model = []
moves = []

count = 1
def run(sock):
	global model
	global moves
	global count

	print(count)
	count = count +1
	print("Wait for answer...")
	buff = ""
	last = False
	while True:
		line = sock.recv(1024)	
		if not line:
			continue

		if "You win!" in line:				
			exit(1)

		buff+=line
		if "Find" in line:				
			if re.match(r".*\((\d+), (\d+), (\d+)\) and \((\d+), (\d+), (\d+)\):*",line.strip().split("\r\n")[-1]):				
				break
			else:				
				last = True
		elif last == True:
			break

	for line in buff.split("\r\n"):		

		if "layer" in line:			
			model.append([])
			continue

		if "Find" in line:						
			m = re.match(r".*?(\d+), (\d+), (\d+).*and.*?(\d+), (\d+), (\d+).*",line.strip())
			start_layer, start_x, start_y = (int(m.group(1)),int(m.group(2)),int(m.group(3)))
			end_layer, end_x, end_y = (int(m.group(4)),int(m.group(5)),int(m.group(6)))
			break

		model[-1].append([])
		for i in range(0, len(line.strip('\r\n')),2):	
			value = line[i]
			if value == ' ':
				value = "1"	
			model[-1][-1].append(value)

	model[end_layer][end_x][end_y] = "2"	

	print("[DEBUG] Start (%s,%s,%s)"%(start_layer, start_x, start_y))
	print("[DEBUG] Ende (%s,%s,%s)"%(end_layer, end_x, end_y))
	search(start_layer, start_x, start_y)
	result =""

	for a,b,c in reversed(moves):		
		result +="(%s,%s,%s)"%(a,b,c)
		model[a][b](c) = "X"

	result += "(%s,%s,%s)"%(end_layer,end_x, end_y)	
	model[end_layer][end_x][end_y] = "X"

	getkey(model)

	print("Sending result....")
	sock.sendall("%s\n"%(result))

	model = []
	moves = []
	result=""

def getkey(model):
	cur = layeror(model[0], model[1])
	for i in range(3,len(model)):
		cur = layeror(cur, model[i])
	printlayer(cur)	
	print("########################################")

def printlayer(layer):
	for i in range(len(layer)):
		print(" ".join(layer[i]))

def layeror(layer1, layer2):	
	resultlayer = []
	for i in range(len(layer1)):
		resultlayer.append([])
		for j in range(len(layer2)):
			resultlayer[i].append("X" if (layer1[i][j] =="X" or layer2[i][j]=="X") else " ")
	return resultlayer

def search(layer,x,y):
	global model
	global moves
	if model[layer][x][y] == "2":		
		return True
	elif model[layer][x][y] == "=":
		return False
	elif model[layer][x][y] == "3":		
		return False

	model[layer][x][y] = "3"

	if ((layer < len(model)-1 and search(layer+1,x,y)) or (layer > 0 and search(layer-1,x,y))
		or (x < len(model[0])-1 and search(layer,x+1,y)) or  (x > 0 and search(layer,x-1,y))
		or (y < len(model[0][0])-1 and search(layer,x,y+1)) or  (y > 0 and search(layer,x,y-1))):
		moves.append((layer,x,y))
		return True
	try:
		moves.remove((layer,x,y))
	except:
		pass
	return False

while True:
	run(sock)

if __name__ == '__main__':	
	pass

Die Lösung wird im Format (a0_x,a0_y,a0_z)(a1_x,a1_y,a1_z)…(aN_x,aN_y,aN_z) erwartet, wobei sich die Schritte nur in genau einer Koordinate unterscheiden dürfen. Um die Aufgabe zu lösen, muss man genau 16 mal ein Labyrinth lösen. Wenn man das geschafft hat, bekommt man als Antwort vom Server:

“You win! How do you like the flag? ;)

Wer nun denkt, es sei endlich geschafft, hat weit gefehlt. Nachdem ich realisiert habe, das die Aufgabe noch nicht gelöst war, habe ich mir Gedanken gemacht, wie es weiter gehen kann. Verschiedene Berechnungen von Koordinatentupeln und Umrechnungen von Schrittanzahlen je Durchgang führen ins Nichts. Manchmal hilft es, sich mit anderen Aufgaben zu beschäftigen und ein wenig Abstand zu bekommen. Oft bekommt man neue Ideen, wenn man sich dann erneut mit dieser beschäftigt. Mir ist aufgefallen, dass es einen Hinweis zu dieser Aufgabe gibt:

PHDays CTF 2012 - Misc 400 - hint

Auch dieser Hinweis ist anfangs keine große Hilfe. Doch mit der Zeit kommt auch die Erleuchtung :-). Da mein Skript schon die ganze Zeit den Weg speichert, den ich pro Labyrinth gegangen bin,  war es sehr schnell umsetzbar, diese grafisch abzubilden (von oben betrachtet) und auszugeben, wie in dieser Ausgabedatei zu sehen ist.

PHDays CTF 2012 - Misc 400 - path finding letters

Es ist sicherlich kein Zufall, das sehr deutlich Buchstaben zu sehen sind. Anstatt ein Skript zu schreiben, welches nun den Raum des Labyrinthes transofrmiert, kann man diese Aufgabe dem Server überlassen, der dies mit jedem Durchlauf selbst durchführt :-)

Nun muss das Skript einfach mehrmals ausgeführt werden, damit man genung Transformationen mitbekommen hat, um alle Buchstaben zu bekommen. Da für das Lösen der Aufgabe immer genau 16 Durchläufe erforderlich sind, ist davon auszugehen, dass auch die Flag aus 16 Buchstaben besteht und die Rheinfolge von 1 bis 16 auch schon feststeht. Danach muss man nur noch die Logfiles durchgehen, und die Flag zusammensetzen.

Flag: NOF3ARNO3XITHER3

Leave a Reply

Your email address will not be published. Required fields are marked *