RUN! (930 pts)

This challenge was a keygenme for Windows (64-bit PE), and like all keygenmes you had to understand the algorithm and write a keygen for it.

The algorithm was "simple", you just had to deal with C++ overhead for std::string, and was basically:

• The programs take the username and computes the sum of each char of the username (with some SSE2 wizardry)
• This sum is then given as seed to srand()
• The user serial is split into 2-char blocks, and each block is decoded as hex string and the integer is added to an array
• The program then searches the highest value in the decoded serial array and allocated a int array with this size
• The array is filled with rand() values mod 13371337
• A valid serial is a sequences of indexes into the random array whose sum is equals to 0xbcdb6 mod 1337

So, the tricky part was to generate this sequence of indexes. Since I wanted to generate a valid serial for any input (instead of bfing the seed value to find "nice" values), I had to "bruteforce" any possible sum until I found the correct sum with the given seed.

And since that sequence could be quite long, I used a "meet-in-the-middle" algorithm, where I basically did this:

• Create a map that will store a sum and its associated offset sequence and fill it with 1-byte sequences
• While nothing found:
  • Generate n+1 sequences, and for each new sequence generated, check if (0xbcdb6 - current sum) is in our dict.
  • If it's the case, then we found a valid serial which is map[current_sum] + map0xbcdb6 - current_sum].

Which gives this implemented in Python:

#!/usr/bin/python
import struct
import ctypes
import itertools

crt = ctypes.cdll.msvcrt

def mod(x, n):
    if x < 0:
        return (n + x) % n
    else:
        return (x % n)

username = b"aaSSfxxx"
print(username)
seed = sum(username)

crt.srand(seed)
random_array = [crt.rand() % 13371337 for _ in range(256)]

dictcomb = {random_array[x]: [x] for x in range(len(random_array))}
loop = True
while loop:
    keys = dictcomb.keys()
    for elt in list(keys):
        # Construct sequence of n+1 offsets
        for i in range(len(random_array)):
            # Compute the next sequence and the associated sum
            j = dictcomb[elt] + [i]
            result = (elt + random_array[i]) % 13371337
            # Add it into the dict if not already present (if we had a shorter sequence with the same sum)
            if result not in dictcomb:
                dictcomb[result] = j
            # Check if (0xbcdb6 - checksum) is present. If so then concatenate the two sequences to form the array
            if (0xbcdb6 - result) in dictcomb:
                print("".join(["%02x" % x for x in (dictcomb[result] + dictcomb[(0xbcdb6 - result)])]))
                loop = False
                break
        if not loop:
            break

After 2/3 minutes of running, this gives a valid flag for my username aaSSfxxx: 0101010101011c4465b0b0e601010b292929a5b0b0b0b0b0b0 . So after entering those information on the remote server, I got the flag.

Original writeup (https://github.com/ret2school/ctf/blob/master/2021/securinets/rev/README.md).