# 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*

### Details

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
flag is ALEXCTF{f0cfad89693ec6787a75fa4e53d8bdb5}
```