Robust_PRNG_in_Python#

Let’s try to hack the generator of pseudo-random number (PRN) of the Python interpreter. We assume that the PRNs are generated by the getrandbits(31) function of the standard random library. You can ask for several consecutive PRNs, up to 1000 pieces. And then you have to guess the next PRN.

Server Code#

1
import time
2
import random
3
import math
4

5
flag = "FAKE_FLAG"
6

7
m=math.ceil(time.time()*1000000)
8
a = 2**10
9
b = 2**30
10

11
random.seed(m)
12
rand_numbers = []
13

14
d = """
15
Попробуем взломать генератор псевдослучайных чисел (ПСЧ) Python.
16
Считаем, что ПСЧ создаются функцией getrandbits(31) стандартной библиотеки random.
17
Вы можете попросить несколько последовательных ПСЧ, до 1000 штук.
18
А затем вы должны угадать следующее ПСЧ."""
19
print (f"{d}\n\n")
20

21
print ('1. Получить следующее число')
22
print ('2. Угадать следующее число')
23
ind = 0
24

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

Code is very similar to the LCG challenge but this time we get 1000 numbers and we have to guess what random.getrandbits(31) will output

If we can figure out what the next output is we will be able to get the flag

The easiest way to solve this is by seeing that the seed for random is generated by the current time*1000000. So all we need to do is to start with a seed of our current time. Then we keep decreasing the number until the first number we see is the same number that the server sent. Once we have the seed all we need to do is just call random.getrandbits(31) to get the next number

Solution#

1
import math
2
import time
3
import random
4
from pwn import *
5

6
def getnextguess(n):
7
    i = math.ceil(time.time()*1000000)
8
    random.seed(i)
9

10
    while(random.getrandbits(31) != n):
11
        i -= 1
12
        random.seed(i)
13

14
    print("SEED:",i)
15
    return random.getrandbits(31)
16

17
io = remote('ctf.mf.grsu.by', 9045)
18
output = io.readuntil(b'>')
19
io.sendline(b"1")
20

21
o = io.recvline()
22
num = int(o.decode().split(': ')[1].strip(" \n'"))
23

24
print("NEXT NUM: ", getnextguess(num))
25
io.interactive()

Running this outputs our next num and we input that and get our flag like so

1
[+] Opening connection to ctf.mf.grsu.by on port 9045: Done
2
SEED: 1751669984568044
3
NEXT NUM:  22866641
4
[*] Switching to interactive mode
5
> $ 2
6
Ваше число: $ 22866641
7

8
Флаг: grodno{cebcc057543753644953923237233143560f6e63}

This same thing also works on the previous Python_PRNG_hack and even on the LCG one which makes it really easy

Conclusion#

Dont use pythons random functions they are not cryptographically secure