📃 Challenge Description

Do you remember these times, where Key Generators where a thing? Pls provide me a nice and oldschool Key Generator for the attached file and use the Service to test your KeyGenerator.

🔎 Research

I first wanted to solve this challenge with angr, but as the input can be anything, and we simply need the associated serial, this was an infinite possibility dead-end. WE COULD set the name in stdin at angr and let the symbolic execution give us the serial as well as WE COULD simply input the name and let a debugger automatically retrieve the serial in the process memory, but I wanted to practice my reverse engineering skills and with an own written algorithm the results are also faster.

I didn’t googled some constants but if I did, I would have found out that this algorithm actually implements the Mersenne Twister.

When analyzing the given binary we can see that it is packed with the UPX packer:

Untitled

Untitled1

to decompress it we run this command:

upx -d -o KeyGenDecompressed.exe KeyGen.exe

Now we are ready to finally inspect the binary.

When running the program, it asks for a name and a serial-key. It looks like each name has a specific serial-key that we have to generate. When giving the wrong Serial, the program prints out N0P3N0P3. Okay, so lets dive deep into the assembler code.

📝 Vulnerability Description

As the given binary contains the algorithm to check for a valid serial, we can also use it to write a serial key generator. This is also the goal of this challenge.

🧠 Exploit Development

I simply started to read and translate the assembler line per line. In the following I will explain the serial generation based on my own python implementation.

First, the name was repeatedly extended to fit whole 0x20 bytes.

class Name():
    def __init__(self, initial_name):
        self.name = self._extend_name(list(initial_name.encode("utf-8")))

    def _extend_name(self, name):
        rel = len(name)
        for i in range(len(name), 0x20):
            name.append(name[i-rel])
        return name

Second, the name_key is generated with the first 4 bytes of the name as a seed.

		def get_name_key(self):
		        name_key = [] # starting at [esp+0x28]
		        name_iv = self.name_iv
		        for i in range(1, 0x270):
		            name_iv = ((name_iv>>0x1e) ^ name_iv) & 0xFFFFFFFF
		            name_iv = (name_iv * 0x6c078965) & 0xFFFFFFFF
		            name_iv += i
		            name_key.append(name_iv)
		        return name_key

    def _hex(self, bytes_):
        return "".join([hex(i)[2:] for i in bytes_])

    @property
    def hex(self):
        return self._hex(self.name)

    @property
    def name_iv(self):
        return bitstring.BitArray(hex=self._hex(self.name[:4][-1::-1])).uint

Then, the name is scrambled based on the name_key.

    def scramble_name(self, name_key, counter=0x270, nn=0xFFFFFFFF):
        for i in range(len(self.name)):
            name_key, eax = some_encryption(counter, nn, name_key, self.name_iv)
            index = eax % 0xff
            self.name[i] = self.name[i] ^ alphabet_table[index+1]
            counter += 1

The some_encryption function looks like this:

def some_encryption(counter, nn, orig_name_key, name):
    if(counter==0x270):
        name_key = [name] + orig_name_key
        for i in range(counter):
            ecx = name_key[i] ^ name_key[i+1]
            ecx = ecx & 0x7fffffff
            ecx = ecx ^ name_key[i]
            eax = ecx
            b = bool(bitstring.BitArray(uint=eax, length=4*8)[-1])
            if(b):
                eax = 0x9908b0df
            else:
                eax = 0x0
            ecx = ecx>>0x1
            eax = eax ^ name_key[i+397]
            eax = eax ^ ecx
            name_key.append(eax)
        eax = counter
    elif(counter>=0x4e0): # DEAD CODE
        pass
    else:
        name_key = orig_name_key

    nc = name_key[counter] # edx -> 0x9bc -> start of new generated above
    return name_key, (((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) & 0xffffdf8C) << 0xF)) & 0xFFFFFFFF)>>0x12) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) & 0xffffdf8C) << 0xF)) & 0xFFFFFFFF)

On its first call (with counter set to 0x270), the name_key will be doubled in size with values based on the initial name_key. After this and on every next call this function basically just takes the entry of name_key at index counter, and returns a value from a big calculation at the end. This value is then used in the scramble_name function to determine the entry of the alphabet_table with which the name is xored. The alphabet_table is a predefined table of characters with 0xff entries. You can find it in the memory dump:

Untitled2

I converted these entries to a list and stored it as a variable in my python script:

alphabet_table = [0x00, 0x1d, 0x30, 0x9f, 0x37, 0xc7,  0xc3, 0x1e, 0xe8, 0x2f, 0xe6, 0x85, 0xcf, 0x4d, 0x52, 0x3f, 0xff, 0xf8, 0xea, 0x9f, 0x3d, 0x73, 0x70, 0xa5, 0x5a, 0xde, 0x3b, 0x39, 0xb3, 0x31, 0x39, 0xa8, 0x8f, 0xe7, 0x65, 0xff, 0xa4, 0x59, 0x61, 0xc0,  0x68, 0x1e, 0xaa, 0x2b, 0x0e, 0xb0, 0xf9,  0x03, 0xf5, 0xa0, 0xb8, 0xab, 0x76, 0x5f, 0x58, 0x57, 0xeb, 0xff, 0x7d, 0x00, 0x4b, 0xe6, 0xf3, 0xfc, 0xc6, 0xc4, 0xe5, 0xbd, 0xdc, 0x48, 0xb7, 0xc4, 0x5e, 0xd8, 0x2d, 0xfd, 0xa6, 0x77, 0xb1, 0xf4, 0xd6, 0xde, 0x49, 0x19, 0x2a, 0x43, 0xfd, 0x9a, 0xda, 0x07, 0x39, 0x6e, 0x57, 0x11, 0x41, 0x61, 0x39, 0x29, 0x35, 0x53, 0xdb, 0xc0, 0x17, 0x55, 0x68, 0x2d,  0xff, 0x9b, 0x21, 0x0c, 0x2f, 0x8d, 0xe3, 0x45, 0x04, 0xfa, 0xa0, 0x60, 0xf9, 0x43, 0xad, 0x5d, 0x2d, 0xc5,  0xea, 0xfd, 0x02,  0x0a, 0x4e, 0x7d, 0xcc, 0xa4, 0xb3, 0x73, 0x07, 0xab, 0xd8, 0x70, 0x6c, 0x58, 0xf5, 0x40,  0x5f, 0x51, 0xd3, 0xf5,  0x31, 0xdd,  0x64, 0xc2, 0xae, 0x9c, 0x36, 0x04, 0xe1, 0x0d, 0x58, 0x00, 0xe5, 0x53, 0x23, 0x14, 0xb0, 0xa7, 0xd8, 0x41, 0xdd, 0x5d,  0x3f, 0x65, 0x9b, 0x93, 0xc2, 0x4d, 0xf7, 0x85, 0x37, 0xb7, 0x32, 0x49,  0x9b, 0xb3, 0x97, 0x4a, 0x1a, 0x36, 0x40,  0xd6,  0x20,  0xcc, 0x79,  0x4c, 0x48, 0xe3, 0x3f, 0x00, 0xe3, 0xd1, 0xaf, 0x48, 0x65, 0x51, 0x9a, 0xf7, 0x42, 0x7d, 0x15, 0xf3, 0x7d, 0x05, 0x0b, 0xfb, 0x76, 0x4c, 0xe8, 0xe3, 0xfe, 0x57, 0xea, 0x11, 0x61, 0xa9, 0x39, 0x26, 0x54, 0x9f, 0x30, 0x57, 0xa5, 0xd4, 0x9d, 0xc4, 0x20,  0x96, 0x82, 0xd6, 0xe0, 0x8f, 0x5c, 0x73, 0x32, 0x27, 0xac, 0x8c, 0x9d, 0x58, 0xe9, 0x3d, 0xb4, 0x30, 0xf8, 0x1e, 0x0f, 0x81, 0xd4, 0xd1]

At this point, we are ready to calculate the serial.

    def calculate_serial(self):
        serial = b""
        for i in range(len(self.name)-1, 0, -1):
            if((len(serial)+1)%9 == 0 and i!=len(self.name)-1):
                serial += b'-'
            idx = self.name[i] % 0x21
            serial += int.to_bytes(ascii_alphabet[idx], 1, "little")
        return serial

Note that the serial consists of 4 blocks each containing 8 characters except the last one with 7 characters. These blocks are seperated by a hyphen. The characters in each block have to match the specific entry of the ascii_alphabet table at index specified by the scrambled_name. The ascii_alphabet table is just another array containing these characters:

ascii_alphabet = b"ABCDEFGHJKLMNPQRSTUWQYZ0123456789!"

This table can be also found in the strings table of the executable.

Overall it was very time-consuming and I struggled a little bit with some array offsets, but in the end I was able to generate my own serial for any given username:

Untitled3

🔐 Exploit Program

generator.py:

import bitstring
bitstring.bytealigned = True

alphabet_table = [0x00, 0x1d, 0x30, 0x9f, 0x37, 0xc7,  0xc3, 0x1e, 0xe8, 0x2f, 0xe6, 0x85, 0xcf, 0x4d, 0x52, 0x3f, 0xff, 0xf8, 0xea, 0x9f, 0x3d, 0x73, 0x70, 0xa5, 0x5a, 0xde, 0x3b, 0x39, 0xb3, 0x31, 0x39, 0xa8, 0x8f, 0xe7, 0x65, 0xff, 0xa4, 0x59, 0x61, 0xc0,  0x68, 0x1e, 0xaa, 0x2b, 0x0e, 0xb0, 0xf9,  0x03, 0xf5, 0xa0, 0xb8, 0xab, 0x76, 0x5f, 0x58, 0x57, 0xeb, 0xff, 0x7d, 0x00, 0x4b, 0xe6, 0xf3, 0xfc, 0xc6, 0xc4, 0xe5, 0xbd, 0xdc, 0x48, 0xb7, 0xc4, 0x5e, 0xd8, 0x2d, 0xfd, 0xa6, 0x77, 0xb1, 0xf4, 0xd6, 0xde, 0x49, 0x19, 0x2a, 0x43, 0xfd, 0x9a, 0xda, 0x07, 0x39, 0x6e, 0x57, 0x11, 0x41, 0x61, 0x39, 0x29, 0x35, 0x53, 0xdb, 0xc0, 0x17, 0x55, 0x68, 0x2d,  0xff, 0x9b, 0x21, 0x0c, 0x2f, 0x8d, 0xe3, 0x45, 0x04, 0xfa, 0xa0, 0x60, 0xf9, 0x43, 0xad, 0x5d, 0x2d, 0xc5,  0xea, 0xfd, 0x02,  0x0a, 0x4e, 0x7d, 0xcc, 0xa4, 0xb3, 0x73, 0x07, 0xab, 0xd8, 0x70, 0x6c, 0x58, 0xf5, 0x40,  0x5f, 0x51, 0xd3, 0xf5,  0x31, 0xdd,  0x64, 0xc2, 0xae, 0x9c, 0x36, 0x04, 0xe1, 0x0d, 0x58, 0x00, 0xe5, 0x53, 0x23, 0x14, 0xb0, 0xa7, 0xd8, 0x41, 0xdd, 0x5d,  0x3f, 0x65, 0x9b, 0x93, 0xc2, 0x4d, 0xf7, 0x85, 0x37, 0xb7, 0x32, 0x49,  0x9b, 0xb3, 0x97, 0x4a, 0x1a, 0x36, 0x40,  0xd6,  0x20,  0xcc, 0x79,  0x4c, 0x48, 0xe3, 0x3f, 0x00, 0xe3, 0xd1, 0xaf, 0x48, 0x65, 0x51, 0x9a, 0xf7, 0x42, 0x7d, 0x15, 0xf3, 0x7d, 0x05, 0x0b, 0xfb, 0x76, 0x4c, 0xe8, 0xe3, 0xfe, 0x57, 0xea, 0x11, 0x61, 0xa9, 0x39, 0x26, 0x54, 0x9f, 0x30, 0x57, 0xa5, 0xd4, 0x9d, 0xc4, 0x20,  0x96, 0x82, 0xd6, 0xe0, 0x8f, 0x5c, 0x73, 0x32, 0x27, 0xac, 0x8c, 0x9d, 0x58, 0xe9, 0x3d, 0xb4, 0x30, 0xf8, 0x1e, 0x0f, 0x81, 0xd4, 0xd1]
ascii_alphabet = b"ABCDEFGHJKLMNPQRSTUWQYZ0123456789!"

def some_encryption(counter, nn, orig_name_key, name):
    if(counter==0x270):
        name_key = [name] + orig_name_key
        for i in range(counter):
            ecx = name_key[i] ^ name_key[i+1]
            ecx = ecx & 0x7fffffff
            ecx = ecx ^ name_key[i]
            eax = ecx
            b = bool(bitstring.BitArray(uint=eax, length=4*8)[-1])
            if(b):
                eax = 0x9908b0df
            else:
                eax = 0x0
            ecx = ecx>>0x1
            eax = eax ^ name_key[i+397]
            eax = eax ^ ecx
#            print("[{0}] appening: {1}\n".format(hex(counter-i),hex(eax)))
            name_key.append(eax)
        eax = counter
    elif(counter>=0x4e0): # DEAD CODE
        pass
    else:
        name_key = orig_name_key

    nc = name_key[counter] # edx -> 0x9bc -> start of new generated above
    return name_key, (((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) & 0xffffdf8C) << 0xF)) & 0xFFFFFFFF)>>0x12) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) ^ ((((nc ^ (nn & (nc >> 0xb)) & 0xFFFFFFFF) & 0xff3A58Ad) << 0x7)) & 0xFFFFFFFF) & 0xffffdf8C) << 0xF)) & 0xFFFFFFFF)

class Name():
    def __init__(self, initial_name):
        self.name = self._extend_name(list(initial_name))

    def _extend_name(self, name):
        rel = len(name)
        for i in range(len(name), 0x20):
            name.append(name[i-rel])
        return name

    def get_name_key(self):
        name_key = [] # starting at [esp+0x28]
        name_iv = self.name_iv
        for i in range(1, 0x270):
            name_iv = ((name_iv>>0x1e) ^ name_iv) & 0xFFFFFFFF
            name_iv = (name_iv * 0x6c078965) & 0xFFFFFFFF
            name_iv += i
            name_key.append(name_iv)
        return name_key

    def scramble_name(self, name_key, counter=0x270, nn=0xFFFFFFFF):
        for i in range(len(self.name)):
            name_key, eax = some_encryption(counter, nn, name_key, self.name_iv)
            index = eax % 0xff
            self.name[i] = self.name[i] ^ alphabet_table[index+1]
            counter += 1

    def calculate_serial(self):
        serial = b""
        for i in range(len(self.name)-1, 0, -1):
            if((len(serial)+1)%9 == 0 and i!=len(self.name)-1):
                serial += b'-'
            idx = self.name[i] % 0x21
            serial += int.to_bytes(ascii_alphabet[idx], 1, "little")
        return serial

    def _hex(self, bytes_):
        return "".join([hex(i)[2:] for i in bytes_])

    @property
    def hex(self):
        return self._hex(self.name)

    @property
    def name_iv(self):
        return bitstring.BitArray(hex=self._hex(self.name[:4][-1::-1])).uint

def keygen(name):
    name = Name(name)
    name_key = name.get_name_key()
    name.scramble_name(name_key)
    serial = name.calculate_serial()
    return serial

if(__name__ == "__main__"):
    name = input("Name: ")
    serial = keygen(name.encode("utf-8"))
    print("serial: {0}".format(str(serial)))

exploit.py:

from pwn import *
import sys
import generator

initial_name = b"tibotix"
initial_serial = b"LGGH8MDC-P97631PU-PH2C0ZT3-K6QGUDW"

if(len(sys.argv)<3):
    print("Usage: python3 exploit.py <host> <port>")
    sys.exit(0)

host = sys.argv[1]
port = int(sys.argv[2])

p = remote(host, port, ssl=True)

p.recvuntil("Name: ")
p.sendline(initial_name)
p.recvuntil(b"Serial: ")
p.sendline(initial_serial)

p.recvuntil("'")
name = p.recvuntil("'")[:-1]
print(str(name))
serial = generator.keygen(name)
p.sendline(serial)
p.recvline()
flag = p.recvline()

print("[+] Flag found: {0}".format(str(flag)))

💥 Run Exploit

Untitled4

FLAG: CSCG{0ld_sch00l_k3y5_4r3_th3_b35t_k3y5}

🛡️ Possible Prevention

Offline key validation are always a bad idea. As long as the program is offline and performs the key validation algorithm, this algorithm can be reversed to generate an own valid key. Certainly one could make things harder by adding more obfuscation and encryption to the algorithm, but that does not give you a full protection. When only checking for one universal serial number you could of course use a hash function and store the hash in the binary. But when you want to check a key for any given user, an online based solution is the way to go. Using this approach one should have a centralized database containing the serial keys. When validating a key for a given user, the program sends a validation request to the server with the given serial and name that will be checked. The server then responds with a failure or success message. This response should obviously be signed by the servers private key and be verified by the server public key, which will be stored in the binary, and should contain some random nonce to prevent replay attacks.

🗄️ Summary / Difficulties

In the beginning try to let the program do the algorithm. Overall it was not difficult but rather very “noisy” with this many steps we had to reverse. Anyways I enjoyed this challenge a lot and I definitely learned and practiced a lot new stuff. However on new rev challenges I would overthink my strategy to solve it.

🗃️ Further References

Using reverse engineering techniques to see how a common malware packer works

angr

UPX