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:

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

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:

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

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

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:

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