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.

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

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.
The first, and easiest, to crack is the XOR key. XOR actually has perfect secrecy
making it very strong^{1}, 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

{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.

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^{2}.
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 PThe partial key

`bgcolors`

. Better yet, we can use some other headers in the `]], "colors": [[`

. This small plaintext is called a
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 elPangPangFlygWe got it!

`FlygplansspelPangPang`

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

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.

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

`{"bgcolors": [0..7`

.
Finally we analyze:
`plain = (p`_{i} ⊕ c_{t}) ⊕ c_{o} = keystream ⊕ c_{o}

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":'35Only the first one (

`{"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 0000000000000004From 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.

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 (```
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" *

Hade lite problem med att dela upp paketen från wireshark och få till det så att de skickas till spelklienten i rätt uppdelning, så att man kan se hela spelförloppet. Har du något tips där?

Tack!