Challenge completed

This post completes the challenge I took on a while back. I you have not read the first post you should go back and do that before continuing, because the rest would not make much sense.

As I found myself with both some time on my hands and a need to focus on “something completely different” I picked up the thread I threw on the stack a few months ago. I needed to crack the final task in the FRA challenge which was to be able to decrypt the high score list that had been encrypted with RC4.

So I read some more on RC4 weaknesses and I knew the same key was used every time, but I still felt that the task was insanely hard compared to the others if I was to actually calculate the keystream based on the encrypted messages. Sure, I probably had some known plain text, like ANSI escape codes and the player name ‘Kalle’ along with his score. But it just felt wrong.

So I went back to look at the original client code for clues…and there it was, staring at me. Probably laughing too since I should have seen this way back when I originally started out on this task.

Here is a snippet of the code with the clue:

class ClientView:
    def __init__(self, s):
        self.sock=s

        try:
            f=open('crypto.txt', 'r')
            self.xor_key=f.readline()
            self.longxor_key=f.readline().strip()
            self.rc4_key=f.readline().strip()
            f.close()
        except:
            # If keys are missing
            self.xor_key=raw_input('Enter xor key: ')
            self.longxor_key=raw_input('Enter long xor key: ')

            # generate rc4 key
            self.rc4_key=''.join(random.sample(string.uppercase, 7))
            print "Keys are stored in crypto.txt"
            f=open('crypto.txt', 'w')
            self.xor_key=self.xor_key[0]
            print >>f, self.xor_key
            print >>f, self.longxor_key
            print >>f, self.rc4_key
            f.close()

Do you see it? In the exception clause there is code for when the crypto.txt is missing. And if we look closely the RC4 key will only be generated 7 characters long, in uppercase letters! *face palm* Why didn’t I see it before?

self.rc4_key=”.join(random.sample(string.uppercase, 7))

So I went ahead and created a brute force script that will try all combinations until it succeeds. After all, I had md5 hashes for the plain text of all messages. So I could easily check if each attempt was correct or not.

For a 7 characters long password that only consist of uppercase letters there are 8,031,810,176 possible combinations. So I would have to either write a brute force script that used several threads or just write a quick one that I just left running over night. I went with the latter.

#!/usr/bin/python

import json
from Crypto.Cipher import ARC4
from hashlib import md5
import string
import itertools
import time

KEY_LENGTH = 7
checked = 0
found = False


def check(key, data, correct_md5):
    global checked
    global found
    decrypted = ARC4.new(key).decrypt(data)
    checked += 1
    if md5(decrypted).hexdigest() == correct_md5:
        print('Key found: %s' % key)
        found = True

    if checked % 401590508 == 0:
        print('Brute force is at attempt %d trying key %s' % (checked, key))


def worker(base):
    global found
    rc4_message = ''
    correct_md5 = ''
    f = open('packets2.dump', 'r')
    data = f.read()
    f.close()
    for d in ''.join(data).split('\n'):
        try:
            if not len(d):
                continue
            j = json.loads(d)
            if j['encoding'] == 'rc4':
                rc4_message = j['buf'].decode('base64')
                correct_md5 = j['md5']
        except:
            continue

    for i in itertools.product(string.ascii_uppercase, repeat=KEY_LENGTH-len(base)):
        check(''.join(base + i), rc4_message, correct_md5)
        if found:
            exit()


if __name__ == "__main__":
    worker(tuple())

What the script does is simply take the last message encrypted with RC4 and then go into a loop testing all possible keys for the RC4 keystream that encrypted the message, from AAAAAAA, AAAAAAB, AAAAAAC and so on up to ZZZZZZZ. If the correct key is found it will print it out and stop execution of the script. At about each 5% of running it will print out the current progress. I started the script and went to bed wondering if the clue would turn out to be a dead end or not.

When I woke up the next morning and finally came around to check the results I found myself staring at this:

Wow! I had to test this key immediately! So I opened up my old player.py and filled in the key for RC4 and ran the script.
Yes…there it is…the all time high…

So there, finally I can leave that one to history and go crazy on the next FRA challenge! I learned a lot from this one, and I hope the next one will teach me things as well.