GCHQ Quiz Grinch: 2

***Contains spoilers, obviously.***

As I mentioned previously, the GCHQ (Government Communications Headquarters) released a hilariously infuriating Christmas card, which consisted of a logic puzzle, which once solved, led to more puzzles, which led to more puzzles, and so on. I cheated to complete Part 2. And, here’s how you can cheat to complete Part 4.

Part 4 consists of three series of numbers. These numbers, back to back, create an IP address to access Part 5. Three numbers to make one IP address. Hmmm, an IP address contains four numbers. One of the numbers must be a decimal. So, I’m looking for two integers and one float, but I’m not sure which.

If you look at the source code, there is a hash function that is used to verify that the answers are correct. Basically, it concatenates the three inputs, performs some one-way computations, returns two answers, and checks if they match two other, known numbers. So, you could work out the correct answers (if you’re smart enough), ooooooooor you could try all possible answers (which is what I did).

There are a few ways to constrain the list of possible answers, which will cut down on the computation time. All IP address components are integers between 0 and 255. Also, I took a guess that the first component was between 0-128 – a Class A IP address. The hash function takes 3 inputs, separated by null characters (“\0”). That means I need to separate 4 integers by two null characters and one period (representing a decimal), but I don’t know in which place the decimal should be. There are three possibilities for that.

So, in all, there are 128 * 256 * 256 * 256 * 3 possibilities (first, second, third, fourth IP components, and decimal placements) to inspect. That’s a grand total of 6,442,450,944 combinations to evaluate. Even for Python, that’s a lot of comparisons, but it can be done. It takes about 0.115s to run 128*3 comparisons, about 29.5s to run 128*256*3 comparisons. To complete our six billion comparisons, it will take approximately 22.5 days. Luckily, the final answer is located fairly early in the sequence, so the final run time is about 8.7 days.

Here’s the script I used:

import ctypes, sys, cProfile

def hsh(dat):
    resultA = 3141592654
    resultB = 1234567890
    for i in range(2):
        initA = resultA
        initB = resultB
        for j in range(len(dat)):
            resultA += ord(dat.lower()[j])
            resultB = ctypes.c_int((resultA * 31) ^ resultB).value
            tmp = resultA & resultA
            resultA = resultB & resultB
            resultB = tmp
        resultA = ctypes.c_int(resultA ^ initA).value
        resultB = ctypes.c_int(resultB ^ initB).value
    return [resultA, resultB]

dot_config = [['.','\0','\0'],['\0','.','\0'],['\0','\0','.']]

def findIP():
    for x in range(128):
        for y in range(256):
            for z in range(256):
                for a in range(256):
                    for dots in dot_config:    
                        res = hsh("".join([str(x), dots[0], str(y), dots[1], str(z), dots[2], str(a)]))
                        if (res[0]==1824745082) and (res[1]==560037081):
                            print ([str(x), dots[0], str(y), dots[1], str(z), dots[2], str(a)])
                            sys.exit()
            print (x, y, z, a, res[0], res[1])
    
cProfile.runctx('findIP()',None,locals())

 

And, the final answers: 52, 30.87, 208

The quiz is for charity, so don’t forget to donate here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s