100% Robust PRNG#

Let’s try to create an unhackable 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 = random.getrandbits(31)
8
a = 2**10
9
b = 2**30
10

11
rand_numbers = []
12

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

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

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

Code is pretty similar to the last chall but this time its not choosing a specific seed. This means it is prob getting it from /dev/urandom which is impossible to guess

So this time we need to get a bunch of inputs and crack the Mersenne Twister (the PRNG python uses). Usually all we need are 624 inputs of 32 bit numbers and we are able to guess the next number. However this time we only get 31 bits which makes it challenging since we are missing a bit everytime

Now a lot of crackers found online dont support less than 32 bits but I was able to find one that does any number of bits by using z3 to crack the Mersenne Twister here

Mistsuu

randcracks

Waiting for api.github.com...

00K

Waiting...

Solution#

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

7
def getnextguess(l):
8
    randomSolver = RandomSolver()
9
    for i in l:
10
        randomSolver.submit_getrandbits(i, 31)
11
    randomSolver.solve()
12
    return randomSolver.getrandbits(31)
13

14
io = remote('ctf.mf.grsu.by', 9046)
15
output = io.readuntil(b'>')
16
l = []
17
for i in range(999):
18
    io.sendline("1")
19
    o = io.recvline()
20
    num = int(o.decode().split(': ')[1].strip(" \n'"))
21
    print(i, num)
22
    l.append(num)
23

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

Code is pretty much the same, we just grab 1000 inputs, submit it to the randomsolver and make it to solve. Then we get our next generated number

Since we only get 1000 inputs it can get pretty inaccurate (we should need about 624*2 = 1248 inputs) but if we try a few times we can get lucky and get the flag

1
...
2
995 712169511
3
996 24678483
4
997 945543443
5
998 1180336752
6
NEXT NUM:  818870482
7
[*] Switching to interactive mode
8
> $ 2
9
Ваше число: $ 818870482
10

11
Флаг: grodno{0ebcd057543753ee54f3a077c6644953923237233143562f0e60}

Conclusion#

Again pythons PRNG can be easily hacked so don’t use it for things that need to be secure