# 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

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