Links

Secretive

The app uses AES to encrypt messages, with keys generated from a Linear Congruential Generator (LCG). If we are able to find previously-generated values from the LCG, then we could find the keys used to encrypt the flag.
class Secretizer:
def __init__(self):
self._lcg = None
​
def init_app(self, app):
self._lcg = LCG(app.config["LCG_SEED"], app.config["LCG_A"],
app.config["LCG_C"], app.config["LCG_M"])
...
​
def _gen_new_key(self):
return map(lambda _: self._lcg.random(), range(4))
​
def secretize_msg(self, msg):
key = self._gen_new_key()
key_str = self._key_to_keystr(key)
cipher = AESCipher(key_str)
encrypted_msg = cipher.encrypt(msg)
return (encrypted_msg, key)
The LCG implementation is as follows.
from __future__ import unicode_literals, absolute_import, print_function
​
class LCG:
def __init__(self, seed, a, c, m):
self._seed = seed
self._x = seed
self._a = a
self._c = c
self._m = m
​
def random(self):
next_x = (self._a * self._x + self._c) % self._m
self._x = next_x
return self._x
LCGs can be quite easily broken, allowing us to find the values of a, c and m. We need to submit two messages, so that we get a pair of keys and their corresponding LCG-generated values. This is sufficient for us to find the LCG parameters.
X = []
for _ in range(7):
X = [344919848, 133572217, 3837144844, 602813605, 3658183952, 3608054065, 2853669428, 2349514525]
​
Det_X = []
Det_X.append(calc_det(1, 2, X))
Det_X.append(calc_det(2, 3, X))
Det_X.append(calc_det(3, 4, X))
Det_X.append(calc_det(4, 5, X))
​
found_p = reduce(GCD, Det_X)
​
mod_inv_a = modInverse((X[2]-X[3]), found_p)
found_a = ((X[3] - X[4])*mod_inv_a) % found_p
​
found_c = (X[4] - found_a*X[3]) % found_p
​
print("Found: %d as P, %d as a and %d as c" % (found_p, found_a, found_c))
​
P, a, c = found_p, found_a, found_c
Now, we need to reverse the LCG to find previously-generated values.
To do this, note that we can reorder the LCG next-state equation and apply the modular inverse of a to find the previous value of x.
x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)
Starting from the most recently-generated value, we can work backwards to the first 4 generated values, which would be the key used to encrypt the flag.
x = 2349514525
x = (a * x + c) % P
​
for i in range(1411):
print('------------------' + str(1411 - i))
x = (modinv(a, P) * (x - c)) % P
print(x)
x = (modinv(a, P) * (x - c)) % P
print(x)
x = (modinv(a, P) * (x - c)) % P
print(x)
x = (modinv(a, P) * (x - c)) % P
print(x)
With the key found, we can obtain the flag!
Last modified 8mo ago