# AlexCTF 2017 - Bring weakness

A sever shows us random looking numbers and we have to predict the output of the next number. The numbers were generated using a linear congruential generator. Using the Marsaglia method we were ale to fully recover the parameters of the PRNG and thus predict the number sequence.

### Description

We got this PRNG as the most secure random number generator for cryptography.

Can you prove otherwise

nc 195.154.53.62 7412

Points: 300

Category: crypto

Validations: 76

### Solution

When we connected to the server we got the following interaction:

$nc 195.154.53.62 7412 Guessed 0/10 1: Guess the next number 2: Give me the next number 2 2607191779 Guessed 0/10 1: Guess the next number 2: Give me the next number 2 975774374 Guessed 0/10 1: Guess the next number 2: Give me the next number  So it seems that we have to guess the following value of a PRNG knowing the previous values but not the algorithm. After playing a bit with multiple connections to the server, I tried to see if the implementation was not a linear congruential generator. Meaning that the next value $x_{n+1}$ will be computed linearly from the previous value $x_n$ i.e $x_{n+1} = ax_n +b \mod m$. We have to find $m$, $a$, and $b$. I first noticed that all the values were coded on 32 bits so $m < 2^{32}$. Then according to the Marsaglia method we can find $m$ by computing the least common divisor of the determinants of several given outputs. We can repeat the procedure until $m<2^{32}$ which gave $m = \mathtt{0xffffffff}$. Computing $a$ is then easy because each consecutive outputs have a linear dependance thus $a = (x_{n+2}-x_{n+1})(x_{n+1}-x_n)^{-1} \mod m$. In our case it gave $a = \mathtt{0x939a5ec0}$. Finally we have $b = x_{n+1} - ax_n \mod m = \mathtt{0x8aa90086}$. Then from a single value we are able to predict the next value with a simple computation. The complete computation are given in this script which allows to recover the flag: $ python3 solution.py
[2333394338, 3027468667, 937323110, 3491539096, 1367160218, 2111818057, 1743138065, 385408531, 3028765313, 3928804162, 1369218140, 1408119226]
m = 0xffffffff
a=2476367552
b=2326331526
Initial number: 3688430318
Next number (in decimal) is

Next number: 896975107
Guessed 1/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 842681045
Guessed 2/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 234035431
Guessed 3/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 3961618553
Guessed 4/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 1021667737
Guessed 5/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 4154774900
Guessed 6/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 1597680361
Guessed 7/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 1400691188
Guessed 8/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 1765742767
Guessed 9/10
1: Guess the next number
2: Give me the next number
Next number (in decimal) is

Next number: 939554780