A disturbing lack of taste. Just another WordPress site

PCTF 2012 – The Game Writeup

During the weekend we had a lot of fun with many of the PCTF challs, althought we were a bit dissapointed with the lack of web-based exploitation challenges [which, incidentally, as a websec team, severely limited our performance ;P].

Either way, there were also some interesting non-websec challenges, namely "The Game".

The Game worked like this:

You connected to a port on their gameservers, and the "game" asked you the following:

You have gotten 0 of 75
Choice 1 = 92c16e01df933c0e8b4d164e28364a9070
Choice 2 = 725d88cb65043a82efd6487dede693678a
Which one is bigger? (1 or 2)

After some experimenting, we realised that the values in the choices were in fact transcendent large "variable" names - each one had a numeric value, but that value had no correlation to the name of the variable [which incidentally was made to look like a hash - leading to quite a lot of confusion in the beginning].

Instead of going all out and programming something, I decided to sit and theoretically go through the steps. The most obvious solution, which was also my first thought, was to create a big dictionary/list/array with all the values, then with every new piece of information move the corresponding value up and down the list, until we get a near accurate represantation of the hierarchy of values. At the time I came up with some strange explanation as to why the approach would fail, but as I now write this writeup I realise that my failure scenario depended on the game giving contradictory statements, which would not have happened. Either way, this is the first solution, which I did not implement for said reason, but which I think would work [and would be fairly much easier to implement than my solution].

a) Let's say we shorten the variables to x, y, qand z. Now we get a question regarding q and x, and we guess it. We either answer correctly, or incorrectly, and from that we learn whether q is greater than x [q > x]. If q now is greater than x, then we can add to the following to our list [from smallest to greatest]:

list = [x, q]

Now, we get more info, and we learn that z is smaller than q [z < q]. Immediately we have a problem - should we place z before or after x? For the time being, we can just generally give a rule saying to place it at the "middle" - now we have:

list = [x, z, q]

Now we get even more info - y is greater than x [y > x]- we do the same thing

list = [x, z, y, q]

Now, one last piece of info - y is greater than q [y > q].

list = [x, z, q, y]

As more information is given, the list also becomes more accurate, and for every increase in accuracy you can just also start guessing answers using the list. After a while, you will have a very low error rate!

Now, my solution was a bit more complicated. In essence, it relies on creating a list with all the "relationships" between the variables/hashes. After you have enough of these relationships, you can use them to compute "chains" between two "unknown" hashes - which you do not know the relationship between. Here is a quick explanation:

If x > y, and y > q, then you can immediately figure out that x > q. This approach only works if the "chain" consists entirely of less than alternatively greater than "links". The issue with this approach is that as you get more relationships [in this case many thousands], the chains can become very long. The algorithm I implemented to search for these chains unfortunately went down the full length of every "branch" in the relationship tree, first going down "increasing" [greater than] branches, then "decreasing" [smaller than] branches. This meant that to find a chain that was decreasing, it would first have to compute through all the increasing chains, and check if it finds anything. A better approach (I assume, at least), would have been to implement a width-first chain-searching algorithm - ie looking through each "level" completely, then moving onto the next one [looking through all 1-length chains first, then all 2-length chains].

All in all, my implementation was not exactly very efficient, but due to lack of time the only "efficiency" patch I had time to implement was a limit on the length of the chains, and a few lines to "re-add" the ends of the chain to the relations table for the beginning of the chain, in an attempt to make look-ups faster. [This may actually have increased the lookup time - didn't have time to run any tests or do any calculations on it].

You could obviously also compute and apply a statistical approach to the challenge - for example; if x is the smallest "number" we assume we know, then the chance of a completely unknown number being smaller than x is smaller than the chance of said number being greater than x. If anyone wants to do this, or even just implement some math into this [how many "relations" would you need to be able to accurately predict answer with an accuracy of x%? what is the optimum chain length? what is the optimum solution (least requests)?], feel free to do so! (read: please do it!)

Here is a quick copy and paste of the script - fairly unadultered from the one I used during the competition, haven't had time to install any code-parsing highlighter yet, will do that soon. If you want highlights - check it out here on pastebin instead [http://pastebin.com/RtLFGWpc]

 

import socket
import pickle

HOST = '23.22.16.34'    # The remote host
PORT = 6969              # The same port as used by the server

# Too lazy to be consistent, just gave some variables their default values here!
previous_answer = []
relations = {}
previous_answer.append('Nope')
previous_answer.append('Nope')

def opensocket():
	s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	s.connect((HOST, PORT))
	return s

def senddata(s, answer=1):
	s.sendall(str(answer) + "\n")

def recdata(s):
	data = []
	data.append(s.recv(256))
	data.append(s.recv(256))
	data = ''.join(data)
	#print data
	return data

def getnext(relations, curr, type, current_answer, level):
	if not relations[curr][type]:
		#print "No level " + str(level) + " neighbours!"
		return 0
	for x in relations[curr][type]:
		if(x == current_answer[1]):
			#print "FOUND CHAIN!"
			return 1
			break
		else:
			if(level < 6):	#Make the longest chains 5! 				if(getnext(relations, x, type, current_answer, (level+1)) == 1): 					return 1 					break 	return 0 	 def maprelations(relations, current_answer): 	 	continuebool = 1 	try: 		relations[current_answer[0]] 	except KeyError: 		#print "No firstlevel neighbours" 		continuebool = 0 		return 0 	if(continuebool == 1): 		for x in relations[current_answer[0]]['greater']: 			if(x == current_answer[1]): 				#print "FOUND CHAIN!" 				return 1 				break 			else: 				if(getnext(relations, x, 'greater', current_answer, 1) == 1): 					relations[current_answer[0]]['greater'].insert(0,current_answer[1]) 					relations[current_answer[1]]['smaller'].insert(0,current_answer[0]) 					return 1 		for x in relations[current_answer[0]]['smaller']: 			if(x == current_answer[1]): 				#print "FOUND CHAIN!" 				return 2 				break 			else: 				if(getnext(relations, x, 'smaller', current_answer, 1) == 1): 					relations[current_answer[0]]['smaller'].insert(0,current_answer[1]) 					relations[current_answer[1]]['greater'].insert(0,current_answer[0]) 					return 2 		#print "No n-level neighbours" 		return 0 		 def parseresponse(s, response, first=0): 	global previous_answer 	global relations 	current_answer = [] 	current_answer.append(0) 	current_answer.append(0) 	 	#print response 	response = response.split("\n") 	 	if(previous_answer[0] == 'Nope'): 		 		current_answer[0] = response[1][11:] 		current_answer[1] = response[2][11:] 	 	elif(previous_answer[0] == 'Known'): 		 		current_answer[0] = response[4][11:] 		current_answer[1] = response[5][11:] 		print "\n+++++++++++++++++\nSanity check: We were - '" + str(response[0]) + ":" + response[1] + "'\n+++++++++++++++++\n" 		#Sanity check, we should not have to use this to get info! 	 	else: 		 		current_answer[0] = response[4][11:] 		current_answer[1] = response[5][11:] 		#Now we put the answer to memory! 		#print "Current record is: '" + response[3] + "'!" 		#print "Previous guess was - '" + response[1] + "'" 		print  "\n+++++++++++++++++\nHad to guess, and I guessed: " + response[1] + "\n+++++++++++++++++\n" 		if(response[1] == 'Wrong  '): 			bigger = 0 		else: 			bigger = 1 		 		try: 			relations[previous_answer[0]] 		except KeyError: 			relations[previous_answer[0]] = {} 			relations[previous_answer[0]]['greater'] = [] 			relations[previous_answer[0]]['smaller'] = [] 			 		try: 			relations[previous_answer[1]] 		except KeyError: 			relations[previous_answer[1]] = {} 			relations[previous_answer[1]]['greater'] = [] 			relations[previous_answer[1]]['smaller'] = [] 		 		#print "[DEBUG] Saving New Relations!" 		 		if (bigger == 1): 			#print "[DEBUG] 1 is bigger than 2!" 			relations[previous_answer[0]]['greater'].insert(0,previous_answer[1]) 			relations[previous_answer[1]]['smaller'].insert(0,previous_answer[0]) 		else: 			#print "[DEBUG] 1 is smaller than 2!" 			relations[previous_answer[0]]['smaller'].insert(0,previous_answer[1]) 			relations[previous_answer[1]]['greater'].insert(0,previous_answer[0]) 	 	guess = maprelations(relations, current_answer) 	 	if(guess>0):
		previous_answer[0] = 'Known'
		return guess
	else:
		previous_answer = current_answer
		return 1

socket = opensocket()
result = parseresponse(socket, recdata(socket),1)

x = 1 #Starting iteration!

#Load old relations!
pkl_file = open('relations.pkl', 'rb')
relations = pickle.load(pkl_file)
pkl_file.close()

#print relations

try:
	while 1:
		print "[DEBUG] Iteration:" + str(x)
		senddata(socket, result)
		result = parseresponse(socket, recdata(socket))
		x=x+1

except KeyboardInterrupt:
	#Save relations!
	output = open('relations.pkl', 'wb')
	pickle.dump(relations, output)
	output.close()
	socket.close()