# 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:```python#!/usr/bin/pythonimport structimport ctypesimport 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 = Truewhile 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.