In this post we continue on the topic of FRA challenges. This challenge^mirror is quite different from the previous. Here to goal is to analyze and answer questions about a game written in python together with a network log from the application. The application is a game which very similar to the classic 1943: The Battle of Midway. So what's the challenge? Encryption! Parts of the communication is encrypted using either xor, longxor or RC4. The challenge also poses some questions like: "What color is the airplane", "which objects are moving" and a few other questions about the game. One thing that makes this challenge interesting is that I think that there are "intended" methods for solving the sub-challenges, which might not always be what I did. I will try to present my solutions and what I think the intended solutions is.

If you just want to check out the videos of the game play using the different keys, you can watch them here (spoiler alert): No keys, XOR key, XOR and longxor keys, All keys.

Overview

Before we start analyzing everything, if we just run the code we get the following image of the game. We see some ocean and a few numbers. Interesting.

If we extract the data from the TCP communication in the network log we get some interesting JSON encoded data:

{u'function': u'object', u'encoding': u'none', 
  u'data': u'{"y": 0, "x": 5, "tile": 75, "z": 1, "id": 1000}', u'md5': u'76...'}, 
{u'function': u'object', u'encoding': u'xor',    
  u'data': u"9`;`xbptznb`:`xbsqnb`6+.'`xbtwnb`8`xbrnb`+&`xbsvvu?", u'md5': u'c3...'}
{u'function': u'tile', u'encoding': u'longxor',  
  u'data': u'=N\x1b\x00\x13\x03...', md5': u'48...'}

Here are some examples of different functions like object and tile, as well as, encodings like xor and longxor.

Let's skip the functions for now and focus on how to break the encryption. The client code contains the following lines:

if j['encoding']=='longxor':
  decoded=''.join([chr(ord(j['data'][i]) ^ ord(self.longxor_key[i % len(self.longxor_key)])) 
                    for i in range(len(j['data']))])
elif j['encoding']=='xor':
  decoded=''.join([chr(ord(i) ^ ord(self.xor_key[0])) for i in j['data']])
elif j['encoding']=='rc4':
  C=ARC4.new(self.rc4_key)
  decoded=C.decrypt(j['data'].decode('base64'))
else:
  decoded=j['data']

We also have the following lines for reading the crypto keys:

f=open('crypto.txt', 'r')
self.xor_key=f.readline()
self.longxor_key=f.readline().strip()
self.rc4_key=f.readline().strip()

At this point I didn't think about the questions in the challenge but rather just focus on cracking the keys. So lets get cracking.

XOR (⊕)

The first, and easiest, to crack is the XOR key. XOR actually has perfect secrecy making it very strong¹, unless the of course the key is poorly chosen. For perfect secrecy the key must be the same length as the plaintext which is usually unfeasible. RC4 tries to solve this as we will see later. To crack the XOR, we note that only the first byte of the key is used, self.xor_key[0]. If we know the ciphertext and the plaintext then it is easy to calculate the key as:

key = cipher ⊕ plaintext

If we look at the first XOR message we have:

{u'function': u'object', u'encoding': u'xor',  u'data': u"9`;`xbp...", u'md5': u'c3...''}

The function here is object, we can compare this to a plaintext message of the same function.

{u'function': u'object', u'encoding': u'none', u'data': u'{"y": 0, ...', u'md5': u'76...'}

Since everything is JSON encoded it seems reasonable to guess that the first character should be {. In that case we get:

key = '9' ⊕ '{' = ord('9') ^ ord('{') = 66 = 'B' 

Using this we can decrypt the full message and get the following message, which seems reasonable. {"y": 268, "x": 13, "tile": 65, "z": 0, "id": 1447} More importantly, we have the md5 hash to verify that the decrypted message is indeed correct.

I believe this was the intended method of solving this part. However, since we have the md5 hash we could simply use brute force to test all keys of length 1.

Now with the xor key we get some more ocean and a few more numbers.

Long xor (⊕⊕⊕)

Next up is longxor. It's very similar to XOR, the only difference being that the key is of unknown length. To find the length of the key, or at least a multiple, we could try to calculate the Index of coincidence². However, in this case it didn't seem necessary.

Same as before we look for a ciphertext and plaintext, this time the function is tile. Below is an example of a tile message. Important to note is that it contains constant headers such as bgcolors, colors, pixels, etc. and dynamic data in the form or color codes, ranging from 0 to 7.

{"bgcolors": [[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]], "colors": [[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]], "number": 65, "pixels": [[" ", " ", " ", " ", " ", "_", " ", " ", " ", " ", " ", " ", " ", " ", "_"], [" ", " ", "_", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " ", " ", " ", " ", "_", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "_", " ", " ", " "], [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "], [" ", " ", "_", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " ", "_", " ", " ", " ", " ", " ", " ", " ", "_"], [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "_", " ", " "], ["_", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "], [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "_", " ", " ", " ", " "]]

As we can see below, tiles seem to start with {"bgcolors": [[ followed by a comma separated list of integers.

Cipher:   = N \x1 b \x00 \x13 \x03 \r \x01 \x01 \x00 R _ L ...
Plain:    { " b   g c     o    l   o  r    s    "    : [ [ ...
Key (⊕):  F l y   g p     l    a   n  s    s    p    e l P

The partial key FlygplansspelP seems good as it makes sense in Swedish (Eng. Aircraft game P). The problem is that we don't see any repetition in the key. Clearly we need more plaintext, but how? We could guess some numbers for the bgcolors. Better yet, we can use some other headers in the tile messages, e.g: ]], "colors": [[. This small plaintext is called a crib which we use in a crib-dragging³ attack on the cipher. If you're interested in the historical impact of this method I would recommend Computerphile's epic on the Enigma.

Alright, so using ]], "colors": [[ we try to xor this with the plaintext at different offsets. Using this we find the partial key angFlygplansspel. Combining this with the previous partial key FlygplansspelP we sadly still don't have an overlap. Trying FlygplansspelPang does not work. Let's pick a new crib, e.g. , "pixels": [[. Now we get: elPangPangFlyg. Putting it all together:

FlygplansspelP
                  angFlygplansspel
           elPangPangFlyg

We got it! FlygplansspelPangPang.

Now we can finally see some planes, clouds and islands.

RC4

So we have cracked XOR using a 1 byte key, as well as a harder 21 byte key. However, using similar methods we would now effectively have to crack an infinitely long key, not good.

If you're not familiar, RC4 uses a key to generate a pseudo-random keystream, which in turn is used for the XOR. The big flaw in this application is that the same key stream is used for all messages, i.e. without a nonce. This means that if we can extract part of the keystream from a tile message then this can be used to decrypt an object_update message. As it turns out, RC4 is only used for tile and object_update messages. With this in mind, there are two things we can try to crack, the RC4 key or the xor keystream. Let's start with the keystream.

Cracking the keystream

Although we don't have any exact plaintext, we can still use crib-dragging and analyze the structure of the result. We take a tile cipher message c_t and an object_update cipher message c_o. Then we generate 8 possible plaintexts (one for each color), p_i=0..7 of the form {"bgcolors": [0..7. Finally we analyze:
plain = (pi ⊕ ct) ⊕ co = keystream ⊕ co
Below are the 8 plains we get using the different numbers:

0: {"y": 256, "x": 35
1: {"y": 256, "x":!35
2: {"y": 256, "x":"35
3: {"y": 256, "x":#35
4: {"y": 256, "x":$35
5: {"y": 256, "x":%35
6: {"y": 256, "x":&35
7: {"y": 256, "x":'35

Only the first one (p₀) generates a possibly valid JSON. We update our plaintexts to {"bgcolors": [0, 0..7 and repeat the process. Each step gives us 3 more plaintext characters which for the message combination I picked was enough to always find just one valid candidate. Until the last step where we get 8 valid candidates. Here we can simply use the md5 hash to see which one is correct.

Now we can use the keystream, '0xc1', '0x17', '0x52', '0x36', '0xbb', ..., to decrypt the other object_update messages and answer the final question "which objects are moving?".

I'm not sure if it's possible to cracking the full stream to decrypt the tile messages. On possbility is to XOR the ciphers with each other to gain some more information. For example, to calculate the first background color we could xor two ciphers, which is the same as xoring the plaintexts.

{"bgcolors": [[7
{"bgcolors": [[3
0000000000000004

From this we can tell that the XOR between the background colors is 4. This limits the search to 8 possibilities instead of 64. An improvement, but a slow and tedious method. Instead, we can try to crack the RC4 key.

The RC4 key

This might be out of scope, as it is not required to answer any of the questions and the method is a bit uninteresting. Nevertheless, we want to explore every avenue. The key insight is that we can check the md5 hash to test if we get have the correct RC4 key. Sure, but the key could be anything right? Yes, but if we check the client code we have the following line:

# generate rc4 key
self.rc4_key=''.join(random.sample(string.uppercase, 7))

The key is just 7 uppercase letters, e.g. ABCDEFG. Using the code below we can brute force the key. But is it feasible? Using the naive implementation, I could check about 250000 keys per second. In total we need to check about 8 billion keys (26^7), which should take about 9 hours. Of course we could improve this in multiple ways, but as Donald Knuth says, "premature optimization is the root of all evil" and 9 hours is well within the time frame of this challenge. Good night see you tomorrow!

for rc4_key in product(string.uppercase, repeat = 7):
  C=ARC4.new("".join(rc4_key))
  decoded=C.decrypt(data.decode('base64'))
  if data_md5==md5.md5(decoded).hexdigest():
    print("win", rc4_key)

We were actually quite lucky as it only took about 1 hour and less than a billion keys to crack it. Now we can decode everything.

With the RC4 key we can also see our own plane. Note also that compared to the previous image, the 3 enemy planes have moved forward, as well as, the white cloud. This is because RC4 is mainly responsible for moving objects.

This was a triumph. I'm making a note here; "Huge success"

Videos

No keys, XOR key, XOR and longxor keys, All keys.

References:

1. One-time pad
2. Index of coincidence
3. Known-plaintext Attack

---

Write your comment!

Submit

Comments