a = getRandomNBitInteger(30) c = getRandomNBitInteger(15) m = getPrime(32) x0 = getRandomNBitInteger(30)
n = random.randint(2**8, 2**10)
flag = open("flag.txt").read().strip()
classRandom(): global m, a, c
def__init__(self, x0): self.x0 = x0
defrandom(self): self.x0 = (a*self.x0+c) % m return self.x0
encryptor = Random(x0)
assert m < 2**32 assert isPrime(m)
x = [ord(i) for i in flag]
withopen("out.txt", "w") as wfile: for ind inrange(len(x)): next = encryptor.random() if ind < 6: print(str(next)) wfile.write(str(next) + "\n") for __ inrange(n-1): x[ind] ^= encryptor.random() print(f"n = {n}") print(" ".join([str(i) for i in x])) wfile.write("n = " + str(n) + "\n") wfile.write(" ".join([str(i) for i in x]) + "\n")
So, the Random function is pretty much just your standard LCG. There are a few key things to note:
The initial state (x0), multiplier (a), increment (c), and modulus (m) are all unknown.
The encryption for loop calls encryptor.random() 186 times between the 6 provided states at the top of out.txt, i.e. the second output is the 187th .random() call after the first output, and so on.
The challenge at hand requires us to figure out a, c, and m, because we need to know all the numbers generated by the LCG and used to XOR with our flag bytes. Notably, we don’t need to know the intial state because we are provided the first state after the initial state (the very first provided state at the top of out.txt), which is enough to figure out everything after that state once we have a, c, and m.
modulus
The first step (as outlined in the previously linked site) of breaking this LCG is to find the modulus m. How can we do that?
Well, we can actually follow very similar steps in breaking standard LCGs (where we are provided 6 consecutive states) to get m. Time for some math!
Let us define s0, s1, etc. to be the provided states of the LCG. Then, we can write:
$$n = 187$$
$$s0 = 123855601$$
$$s1 = s0(a^n) + c(a^{n-1}) + c(a^{n-2}) … + ca + c ;(mod ;m)$$
$$X = c(a^{n-1}) + c(a^{n-2}) … + ca + c ;(mod ;m)$$
$$s1 = s0(a^n) + X ;(mod;n)$$
$$s2 = s1(a^n) + X ;(mod ;m)$$
Note that these derivations come from going through the math for the first few states of the LCG.
From these initial equations, we can derive the following:
We can extend this to any expression $$t_{r+2} \cdot t_{r} - t_{r + 1} \cdot t_{r + 1}$$
where r is some integer >= 0
Because we know that expression will be equal to a multiple of m.
Through this, by taking the GCD of this expression for a few different values of r, we can get the modulus! Also, it turns out this site’s function for doing so does the exact thing we want it too!
multiplier
Now let’s find the multiplier. Take a look at this equation:
$$t1 = s2 - s1 = (a^n)(s1 - s0) ;(mod ;m)$$
Well, we can pretty easily solve for a^n:
$$a^n = \frac{s2 - s1}{s1 - s0} ;(mod ;m)$$
Now that we have the modulus, we can simply calculate the inverse for the modulus of $$s1 - s0$$
Perfect! So now we have a^n. Now… how do we calculate a?
I’m sure there’s a smart solution to this, but uh… a is only 30 bits.
…
Yeah I just brute-forced it: (only took like 10 minutes)
1 2 3
for a in trange(1<<30): ifpow(a, n, m) == a_power_n: print(a)
Sweet, now we have the multiplier!
increment
Do you enjoy using your brain to solve crypto challenges? Not me!
1 2 3 4 5 6 7 8
for c in trange(1<<15): lcg = Random(states[0]) for _ inrange(n-1): lcg.random() res = lcg.random() if res == states[1]: print(c) break
Only 15 bits for the increment, and only 187 calls to lcg.random(), so easy brute-force!
WIN
Now that we have the modulus, multiplier, and increment, we can just iterate forward from the very first state we were provided, do the same encryption process on the ciphertext (since XOR encryption == decryption) and get the flag!
m = crack_unknown_modulus(states) a_power_n = crack_unknown_multiplier(states, m)
# NOTE: find a # for a in trange(1<<30): # if pow(a, n, m) == a_power_n: # print(a)
a = 779849675
# NOTE: find c # for c in trange(1<<15): # lcg = Random(states[0]) # for _ in range(n-1): # lcg.random() # res = lcg.random() # if res == states[1]: # print(c) # break
c = 23327
out = # ommitted because very long lcg = Random(states[0]) for i inrange(len(out)): if i != 0: lcg.random() for _ inrange(n - 1): out[i] ^= lcg.random()
