## 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()

## printf(“Hello %s”, `echo ‘World’`);

Hi, we are going to release writeups, info, and news on this blog!

Stay tuned!

//iPw