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 = ''    # 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 = {}

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 = ''.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
            if(level < 6):  #Make the longest chains 5!
                if(getnext(relations, x, type, current_answer, (level+1)) == 1):
                    return 1
    return 0

def maprelations(relations, current_answer):

    continuebool = 1
    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
                if(getnext(relations, x, 'greater', current_answer, 1) == 1):
                    return 1
        for x in relations[current_answer[0]]['smaller']:
            if(x == current_answer[1]):
                #print "FOUND CHAIN!"
                return 2
                if(getnext(relations, x, 'smaller', current_answer, 1) == 1):
                    return 2
        #print "No n-level neighbours"
        return 0

def parseresponse(s, response, first=0):
    global previous_answer
    global relations
    current_answer = []

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


        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
            bigger = 1

        except KeyError:
            relations[previous_answer[0]] = {}
            relations[previous_answer[0]]['greater'] = []
            relations[previous_answer[0]]['smaller'] = []

        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!"
            #print "[DEBUG] 1 is smaller than 2!"

    guess = maprelations(relations, current_answer)

        previous_answer[0] = 'Known'
        return guess
        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)

#print relations

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

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