Rating:

## PokePark - Raising New Generation Writeup (6 solves / 497 points)

> nc 3.16.14.62 5000

### [Solve Script](sol/apex.py)

```py

from Crypto.Util.number import inverse, GCD

from functools import reduce

def get_inc(states, m, n):

s1 = states[0]

s2 = states[1]

return ( s2 - m * s1) % n

def get_mult(states, n):

s1 = states[0]

s2 = states[1]

s3 = states[2]

m = ((s3 - s2) * inverse(s2-s1, n)) % n

return m

def get_mod(states):

diffs = [b - a for a, b in zip(states, states[1:])]

z = [a*c - b**2 for a, b, c in zip(diffs, diffs[1:], diffs[2:])]

n = reduce(GCD, z)

return n

def predict_state(curr_state, n, m, c):

pred = (m * curr_state + c) % n

return pred

if __name__ == '__main__':

states = [1997095401, 13001997, 1628715232, 1990339562, 284249215, 1372925577, 48385624, 1468364002, 2059193937, 26044107]

n = get_mod(states)

print("n:", n)

m = get_mult(states, n)

print("m:", m)

c = get_inc(states, m, n)

print("c:", c)

print("predicted:", predict_state(states[-1], n, m, c))

```

The name of the challenge was supposed to be a hint that it's Park-Miller Random Number Generator ?. Here is a little bit of intro stuff about

this Random Number Generator (RNG).

State[i+1] = m * State[i] mod n

where **m** is the multiplier and n is the prime modulus. So the next **State[i+1]** is determined by multiplying the

current **State[i]** with **m** and then mod **n**.

## Predicting The Next State

### The Modulus

According to this - [Cracking a linear congruential generator](https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator)

we can recover the modulus by this method:

*To recover m, define t<sub>n</sub> = s<sub>n</sub> + 1 - s<sub>n</sub> and u<sub>n</sub> = |t<sub>n</sub> + 2 * t<sub>n</sub> - t2<sub>n</sub> + 1|;

then with high probability you will have m = gcd(u1, u2, ..., u10). 10 here is arbitrary; if you make it k, then the probability that this fails is

exponentially small in k.*

### The Multiplier

We can get the multiplier by solving the two linear equations only,

s1 = s0 * m + c (mod n)

s2 = s1 * m + c (mod n)

s2 - s1 = s1 * m - s0 * m (mod n)

s2 - s1 = m * (s1 - s0) (mod n)

m = ((s2 - s1) * inverse_mod(s1 - s0, n)) (mod n)

where **s0, s1 and s2** are the three consecutive states.

### The Increment

The increment for Lehmer RNG is 0 but if you want you can recover that too,

s1 = s0 * m + c (mod n)

c = s1 - s0 * m (mod n)

Now that we have the modulus, multiplier and the increment( which is 0 anyway) we can predict the next state like this:

next_state = m * last_state + c (mod n)

Now submit the predicted value and get the flag !!! \o/

## Flag

> darkCON{P0k3m0ns_4nd_RNG!!!}

### # Source Code + the binary - [[./src folder]](src/)

## Ref

* [Lehmer random number generator - Wiki](https://en.wikipedia.org/wiki/Lehmer_random_number_generator)

* [Cracking a linear congruential generator](https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator)

Original writeup (https://github.com/r3yc0n1c/CTF-Writeups/tree/main/2021/darkCON-2021/Crypto/PokePark%20-%20Raising%20New%20Generation#pokepark---raising-new-generation-writeup-6-solves--497-points).