Tags: rand rev
Rating: 5.0
# 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/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.
