mrn00b0t

Interfacing between technophile and technophobe

TG20 – Game of Keys – Reversing (PYTHON)

This is how I got the flag in TG:HACK 2020 Reverse Engineering Challenge “Game of Keys”

Note: This isn’t quick, nor is it elegant. I’m a complete n00b at hacking/Python/Linux/reversing, so I took the time to not only try and understand how the code worked, but build a solution using python too.

You begin the challenge with a compiled python file keygame.pyc and a wordlist, wordlist.txt.

The wordlist contains 4 digit alphanumeric strings (pattern possibly created using crunch 4 4 -t @@%@).

Let’s have a look inside the python file. (If you prefer to run strange files before looking at them, that’s your business :-))

First let’s decompile it:

uncompyle -o . keygame.pyc

This creates a decompiled python file keygame.py

# uncompyle6 version 3.6.5
# Python bytecode 3.7 (3394)
# Decompiled from: Python 3.7.7 (default, Apr 1 2020, 13:48:52)
# [GCC 9.3.0]
# Embedded file name: keygame.py
# Size of source mod 2**32: 1496 bytes
import base64 from itertools import cycle
class myGame:
def __init__(self, xdim=4, ydim=4):
    self.x = xdim
    self.y = ydim
    self.matrix = []
    for i in range(self.x):
        row = []
        for j in range(self.y):
            row.append(0)

        self.matrix.append(row)

def make_keys(self, *args, **kwargs):
    words = []
    with open('wordlist.txt') as (f):
        for line in f:
            words.append(line.strip())

        for i in range(self.x):
            for j in range(self.y):
                self.matrix[j][i] = words[(i + j)]

    keyArray = []
    keyArray.append(self.matrix[args[0]][args[1]])
    keyArray.append(self.matrix[args[2]][args[3]])
    key = ''
    for k in keyArray:
        key = key.strip() + str(k).strip()

    print(key)
    return key

def checkdata(self, key):
    f = base64.b64decode(b'NSYDUhoVWQ8SQVcOAAYRFQkORA4FQVMDQQ5fQhUEWUYMDl4MHA==')
    data = f.decode('ascii')
    c = ''.join((chr(ord(c) ^ ord(k)) for c, k in zip(data, cycle(key))))
    print('%s ^ %s = %s' % (data, key, c))

if name__ == '__main':
    mgame = myGame(25, 25)
    x = input('input a number: ')
    y = input('input a number: ')
    x1 = input('input a number: ')
    y1 = input('input a number: ')
    data = mgame.make_keys(int(x), int(y), int(x1), int(y1))             
    mgame.checkdata(data)

Now I’m not even going to pretend I know all the programming lingo. I just try to understand what stuff does.

In essence, the class section defines what will happen when an instance of the game is played.

The ‘main‘ section then gathers the relevant information from the user required to run the instance.

The class (myGame) can be broken down into 3 sections:

  1. init (I imagine this is how each instance sets itself up with user provided data)
  2. make_keys (creates a method? function? that can be used in the instance)
  3. checkdata (creates a method? function? that can be used in the instance)

Going step by step through init, we establish that it takes variables x,y and makes a matrix of size x * y filled with 0s. By default it creates a 4*4 matrix if no arguments are supplied.

make_keys appears to produce a key from some manipulation of wordlist.txt and the matrix created by init

checkdata appears to contain a fixed string which is then decoded in a process involving the key from make_keys

Well that’s very handy because we now know that the flag is encoded in the string:

NSYDUhoVWQ8SQVcOAAYRFQkORA4FQVMDQQ5fQhUEWUYMDl4MHA==

Let’s open a python interpreter on the command line and actually step through checkdata.

>>>import base64     #we need this library to operate next line
>>>f = base64.b64decode(b'NSYDUhoVWQ8SQVcOAAYRFQkORA4FQVMDQQ5fQhUEWUYMDl4MHA==')      #the line from keygame.py that does something to what we think holds the key
>>>f      #shows us whats now in f
b'5&\x03R\x1a\x15Y\x0f\x12AW\x0e\x00\x06\x11\x15\t\x0eD\x0e\x05AS\x03A\x0e_B\x15\x04YF\x0c\x0e^\x0c\x1c'      #this is what's in f
>>>data = f.decode('ascii')      #from keygame.py, does something to what's in f
>>>data      #show us what you did!
'5&\x03R\x1a\x15Y\x0f\x12AW\x0e\x00\x06\x11\x15\t\x0eD\x0e\x05AS\x03A\x0e_B\x15\x04YF\x0c\x0e^\x0c\x1c' #ok so pretty much all it did was format it to remove the leading b

Don’t close the interpreter or you lose your variables.

Now one thing we should note here. So far as we moved through those lines in the interpreter we didn’t introduce any input. So that means the value data is static for every instance of the game.

The next line, however, is going to introduce the key variable, which relies on make_keys. If we look in the main section we can see make_keys is used and receives arguments from user input – therefore we know that the value of key is going to change depending on what the user enters as input.


Before we worry too much about that, let’s go back to the interpreter.
We want to figure out what this line does:

c = ''.join((chr(ord(c) ^ ord(k)) for c, k in zip(data, cycle(key)))) 


We can see that there is an inline for loop contained in that line of code, so let’s start to the right of it.

In the interpreter:

>>>from itertools import cycle      #we need to import cycle from the library to use it
>>>key = 'abcdef'      #let's just give key a known value to try and figure out what happens
>>>zipped = zip(data, cycle(key))      #we will see what this does below
>>>list (zipped)      # we have to use list instead of just the variable name, because it's a list!
[('5', 'a'), ('&', 'b'), ('\x03', 'c'), ('R', 'd'), ('\x1a', 'e'), ('\x15', 'f'), ('Y', 'a'), ('\x0f', 'b'),…..]

OK let’s figure out what that did by comparing what was held in the data variable (which is static) and the key.


If we look closely we can see that zip has created a list of paired items; it has taken, in order, each individual value of data and paired it, in order, with a letter from key.


Cycle was used to move through each character of key one at a time. Also, because data has more values than there were characters in key, once it iterated through a to f, it started at a again and so on until it ran out of values from data.

So what is this “for” loop doing? It is selecting every single “pair” in that zipped data in turn and doing something with it. Let’s figure out what.

The first thing it does to the pair is run ord command against each. What’s that? A quick Google tells us that ord will return the Unicode point of the argument.

Let’s see what that actually means by working on our first pair of values for c and k, ‘5’ and ‘a’.

Try it in the interpreter.

>>>ord('5')
53
>>>ord('a')
97

So we get back two numeric values which, if we look them up on a Unicode table, correspond with the characters 5 and a.

According to the code, the next thing it will do is to XOR those values (denoted by the ^). Let’s give that a go with our figures.

>>>53^97
84

So that will result in 84 being passed into the chr command. What does that do? Well, this is basically the reverse of ord, pretty much. It gives us back the character that corresponds to that Unicode point.

>>>chr(84)
'T'

So 84 is the Unicode point for the letter ‘T’. That means that ‘T’ is going to be passed into ”.join to give us a value. It’s a bit misleading that they called that value ‘c’ here – it is seperate from the c that is operating within that inline for loop.

Let’s give it a go and find out what we get:

>>>c = ''.join('T')
>>>c
'T'

OK so it added ‘T’ to the c variable. But we know that this .join is going to run for every pair of c,k in the zip. Given the name of the command, it makes sense that it is going to “join” those values for every pair to the first, rather than overwrite it, until it finishes. Until it produces a string that very probably looks like the flag! But we need the right key…

Fortunately, we know that all flags for this set of challenges start TG20{ – we can therefore figure out the first five characters of the key just by reversing what we just did.

So we know that the key is XORed against the fixed data string to produce the Unicode value of each out character. This is done as a XOR b = c. Handily, if you know two out of 3 values for a,b and c in that equation, you can reverse it.

We know the first five values of the flag are:

T G 2 0 {


The Unicode points are:

84 71 50 48 123

We know the first five fixed data string values are:

5 & \x03 R \x1a


The Unicode points are:

53 38 3 82 26

(You can calculate these using ord() in the interpreter!)

That means that the first 5 values used in the key can be calculated. To reverse an XOR you just XOR the two known values.

We do the following:

84 ^ 53 = 97
71 ^ 38 = 97
50 ^ 3 = 49
48 ^ 82 = 98
123 ^ 26 = 97

Convert from Unicode (use chr() in the interpreter!):

a a 1 b a

Great! so we now know the following things about the key:

The first five characters.
It must be at least 4 characters long (before it starts repeating)
We need the correct value of key to decode the flag

So next let’s figure out how the key value is generated. We figured out earlier that make_keys creates the key by a combination wordlist.txt, a matrix generated by the instance, and user input.

Let’s look at the matrix first. It’s defined in init:

 def init(self, xdim=4, ydim=4):
     self.x = xdim
     self.y = ydim
     self.matrix = []
     for i in range(self.x):
          row = []
          for j in range(self.y):
               row.append(0)

          self.matrix.append(row)

We could step through this in the interpreter with the default values, but let’s head on down to main and see what gets generated for an instance.

mgame = myGame(25, 25)

So we can see that the matrix parameters are hardcoded and unaffected by user input. By stepping through the interpreter, we can generate the matrix used by the program:

>>>x = 25      #sets x to 25
>>>y = 25      # sets y to 25
>>>matrix = []      #sets matrix to an empty array
>>>for i in range(x):
…      row = []
…      for j in range(y):
…           row.append(0)
…      matrix.append(row)      #populates the matrix with 25 rows and columns, each with a value of 0
…
>>>list(matrix)
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,…….]]

You’ll see that the code has set up a matrix of 25 arrays. each of which contains 25 values of 0.

Let’s look at make_keys. We will break it into two pieces.

 words = []
with open('wordlist.txt') as (f):
     for line in f:
          words.append(line.strip())

     for i in range(self.x):
            for j in range(self.y):
                self.matrix[j][i] = words[(i + j)]

Clearly, this code snippet is going to open up the wordlist.txt document, but what does it actually do? Let’s find out.

>>>words = []      # creates an empty array words
>>>with open('wordlist.txt') as (f):      #opens wordlist.txt, and refers to it as f from now on
…      for line in f:      #iterates through every line of wordlist.txt and performs the below on it
…           words.append(line.strip())      #removes formattting such as newlines (\n) from each line and appends each string to the array word
…
>>>list (words)      #let's have a look!
…………'zz9r', 'zz9s', 'zz9t', 'zz9u', 'zz9v', 'zz9w', 'zz9x', 'zz9y', 'zz9z', '']

Yikes! that was a lot of data in words! But you should be able to see that words is just an array that contains every single entry in wordlist.txt. All this piece of code has done is pull that data from wordlist.txt into the program so we can use it. Let’s carry on.

>>>for i in range(x):      #don't forget, the value of x at this point is 25, as it was hardcoded.
…      for j in range(y):      #again, y at this point is 25 because it was hardcoded.
…           matrix[j][i] = words[(i+j)]      #populates our 25x25 matrix with data from words
…
>>>list(matrix)
[['aa0a', 'aa0b', 'aa0c', 'aa0d', 'aa0e', 'aa0f', 'aa0g', 'aa0h',……, 'aa1w']]

So our 25 x 25 matrix is now full of data from wordlist.txt. Now ask yourself a question – have we used ANY user input data to generate the matrix up to this point? No, we haven’t. It was all hardcoded or from the fixed file wordlist.txt. That means that the matrix for EVERY instance is the same up until this point.

Let’s have a look at the next bit of code:

keyArray = []
keyArray.append(self.matrix[args[0]][args[1]])
keyArray.append(self.matrix[args[2]][args[3]])
key = ''
for k in keyArray:
     key = key.strip() + str(k).strip()
print(key)
return key

Here’s where the user comes in. Those 4 args[] are the four inputs the user is prompted to provide. Let’s just use 1, 2, 3, and 4 for now.

>>>keyArray = []      # creates and empty array keyArray
>>>keyArray.append(matrix[1][2])      #gets the string located at position [2] in array [1] in matrix (don't forget count starts at 0!) and puts it in keyArray
>>>list(keyArray)      #let's see what's in there
['aa0d']

We carry on:

>>>keyArray.append(matrix[3][4])      #gets the string located at position [4] in array [3] in matrix and appends it to keyArray
>>>list(keyArray)      #let's have another look in keyArray now
['aa0d', 'aa0h']

So far so good. The code has grabbed two strings from positions in matrix that are defined by the 4 user inputs. What happens next?

>>>key = ''      #create variable key as an empty string
>>>for k in keyArray:      #for every value in keyArray, in other words two
…      key = key.strip() + str(k).strip()      #strip any formatting from whatever is in key and concatenate with the value grabbed from keyArray
…
>>>key
'aa0daa0h'

There we have a key. Let’s recap what else we’ve learned.

The key will be a fixed length of 8 characters
The key is selected by grabbing a pair of 4 character strings from the FIXED array matrix (it’s hardcoded, remember?) and sticking them together
SIDE NOTE – since the matrix array is 25 x 25, the user can only input values from 0 to 24, otherwise the program will throw an error.

We also know that the key we are looking for begins with aa1ba

So at this point I perhaps got a bit over enthusiastic. Since we know how to generate the key, and we know the source from which it is generated, could we:


Generate all possible keys that start with aa1b (the 5th character is a red herring because every string in matrix starts with a)
Feed them into the decoder checkdata automatically so we can search the results.

There’s almost certainly easier ways to do this with Python but I am also a Linux n00b so I thought I’d give that a go.

So first of all I copied and pasted the raw value of the array matrix into a file called matrixlist

>>>list(matrix)      # this will get it back on screen for you.

It’s horrible. It’s like the whole array on a single line. Let’s sort that out.

user@user:~$ cat matrixlist | tr ',' '\n' > newline

This reads matrixlist, replaces all the commas with newlines (\n) and saves to a file called newline.

If we open that we can see that all the 4 character strings are on their own line but we still have [] and ‘ in there.Tidy those up as follows:

user@user:~$ cat newline | tr -d \[\]\' > clean

This reads newline and then deletes all [, ] and ‘ characters, saving the result to clean. If you open clean, you’ll hopefully find it contains a series of 4 character strings and nothing else. What you may also notice is that there are a lot of duplicates. We already know the first 4 characters of the key, so we only need to concatenate with unique 4 character values. Let’s get rid of duplicates.

user@user:~$ sort clean | uniq | 'sed '/ //g' > matrixlist

This sorts clean, removes duplicates, and because sort seems to add a random space in front of every line, reformats it before overwriting matrixlist

If you now open the new improved matrixlist, we will not only see that everything is formatted nicely, but also that the number of entries has dropped dramatically to something that will fit on a screen. This is the number of keys we are going to generate! Still quite a lot though. Can we get it smaller?

Well, if we look at data again (or zipped if it is still available) we should be able to work out that it contains code for 37 characters. This means the flag is 37 characters long. We know the key starts with aa1ba and is 8 characters long. When data is zipped with the key, we cycle through key. If we get to the end before we finish zipping, we carry on from the start of key again until we are done. Therefore the key is used 37 / 8 = 4 mod 5 (5 remaining). So that means the last character of data is zipped with the 5th character of the key which is a.

That’s a shame: if it had been mod 6,7 or 8 we could have narrowed it further. Never mind.

So next we need to add aa1b to the start of each line in the cleaned up matrixlist.

Let’s do that with Python just to switch things up.

Exit any open interpreter using exit() and start a fresh one.

>>>h = open('keylist','a')      #creates and opens a new file called keylist with append (not write!) privilege
>>>with open('matrixlist') as (g):      #opens our matrixlist document and refers to it as g from now on.
…      for line in g:      #iterates through every line in matrixlist
…           key = 'aa1b' + line.strip()+'\n'      #concatenates aa1b with the contents of each line in matrixlist, formatted and then newlined after each
…           h.write(key)      #writes the new concatenated string back to the document keylist
… 
>>>h.close()      #closes keylist (the with command closes matrixlist automatically when it completes)
>>>g.close()      #closes matrixlist (just in case)
>>>exit()      #exits interpreter to be super sure

It was getting late and for some reason when I was typing the above to test, it seemed it didn’t always write to keylist – suspect I needed more Haribo.

If we now open keylist we should see a nice list ready to go! So let’s code our auto decoder. No sense in reinventing the wheel, a lot of the code has been done for us.

Open a new file and call it yourfile.py

Add the following code to the file:

!/usr/bin/python3 #defines this as a python file
import base64
from itertools import cycle
f = base64.b64decode(b'NSYDUhoVWQ8SQVcOAAYRFQkORA4FQVMDQQ5fQhUEWUYMDl4MHA==')
data = f.decode('ascii')
with open('keylist') as (g):
     for line in g:
          line = line.strip()
          c = ''.join((chr(ord(c)^ord(k)) for c,k in zip(data, cycle(line))))
          print ('Key: %s Decoded String %s' % (line,c))

You should know what each of those lines does – if not just read back through the article again.

Now run the file from command line:

user@user:~$ python3 yourfile.py

You’ll get a screen full of possibles, but only one of them is correct in English (albeit with a bit of “l33tspeak”)

++++++SNIP++++++
Key: aa1baa1d Decoded String: TG20{thks flag qhould bg on teh"moon}
Key: aa1baa1e Decoded String: TG20{thjs flag phould bf on teh#moon}
Key: aa1baa1f Decoded String: TG20{this flag should be on teh moon} <------ It's this one!
Key: aa1baa1g Decoded String: TG20{thhs flag rhould bd on teh!moon} 
Key: aa1baa1h Decoded String: TG20{thgs flag }hould bk on teh.moon}
Key: aa1baa1i Decoded String: TG20{thfs flag |hould bj on teh/moon}
++++++SNIP++++++

So there we go, we got the flag, and the key was aa1baa1f.

No doubt there’s about a gazillion easier, neater and better coded ways of doing things, but I’m a n00b, and whilst I may have got to the flag the long way, I sure learned a lot while I did it.

Hopefully you did too!

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: