# 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]

```
'''
PCTF - The Game solution by iPw for Tasteless!
'''
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()
```