LCG_hack#

Let’s try to hack the Linear Congruential Generator for pseudorandom numbers (PRN). Its formula is: Xn+1 = (A * Xn + B) mod M You can ask for several consecutive PRNs, up to 50. And then guess the next PRN.

Server file#

1
import math
2
import time
3

4
flag = "FAKE_FLAG"
5

6
m=math.ceil(time.time()*1000000)
7
a=2**15-1
8
b=2**51-1
9

10
x = m
11
rand_numbers = [x,]
12

13
for i in range(1,50):
14
    x = (a*x + b) % m
15
    rand_numbers.append(x)
16

17
d = """
18
Попробуем взломать Линейный Конгруэнтный Генератор псевдослучайных чисел (ПСЧ).
19
Его формула: Xn+1 = (A * Xn + B) mod M
20
Вы можете попросить несколько последовательных ПСЧ, до 50 штук.
21
А затем угадать следующее ПСЧ."""
22
print (f"{d}\n\n")
23
print ('1. Получить следующее число')
24
print ('2. Угадать следующее число')
25
ind = 0
26

27
while True:
28
    if ind == len(rand_numbers):
29
        print ('Слишком долго думаешь. Отдохни ...')
30
        break
31
    inp = input('> ')
32
    if inp == '1':
33
        print (f"Следующее число: {rand_numbers[ind]}")
34
    elif inp == '2':
35
        ans = int(input('Ваше число: '))
36
        if ans == rand_numbers[ind]:
37
            print (f"\nФлаг: {flag}")
38
        else:
39
            print (f"\nОшибка. Мое число: {rand_numbers[ind]}")
40
        break
41
    ind += 1

Basically we can get up to 50 random numbers by sending 1 and we must guess the next random number after sending 2 to get the flag

If we do some googling we can find that LCG can be easily hacked by finding m after a few inputs from this post

To recover m, define tn = sn+1 - sn and un = |tn+2 tn - t2n+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. I can share a pointer to why this works, if anyone is interested.

So all we need is about 10 inputs and we can crack m and a and b are already give to us so we can predict the next number

Solution#

1
import math
2
from functools import reduce
3
from pwn import *
4

5
def compute_m(l, k=10):
6
    t = [l[i+1] - l[i] for i in range(len(l) - 1)]
7

8
    u = [abs(t[i+2] * t[i] - t[i+1]**2) for i in range(min(k, len(t) - 2))]
9

10
    return reduce(math.gcd, u)
11

12
io = remote('ctf.mf.grsu.by', 9042)
13
output = io.readuntil(b'>')
14

15
l = []
16

17
for i in range(10):
18
    io.sendline(b"1")
19
    o = io.recvline()
20
    num = int(o.decode().split(': ')[1].strip(" \n'"))
21
    l.append(num)
22

23
print("L:", l)
24
m = compute_m(l)
25
print("M:", m)
26

27
a=2**15-1
28
b=2**51-1
29

30
print("NEXT GUESS:", (a*l[-1]+b)%m)
31
io.interactive()

Now if we run this script we can get our next num that predict it and submit it to get our flag

1
[+] Opening connection to ctf.mf.grsu.by on port 9042: Done
2
L: [1751589033459241, 500210780226006, 1288260367646571, 1383560121169104, 987337136181212, 726704037818340, 1310097128850632, 508799809806322, 719158238923142, 1030958447650747]
3
M: 1751589033459241
4
NEXT GUESS: 769565657331029
5
[*] Switching to interactive mode
6
> $ 2
7
Ваше число: $ 769565657331029
8

9
Флаг: grodno{8e78c0436448239239fe54646addf1e34}
10
[*] Got EOF while reading in interactive
11
$
12
[*] Closed connection to ctf.mf.grsu.by port 9042

Conclusion#

Don’t use an LCG to generate random numbers its really easy to predict