Praise our RNG Gods
#

Points: 436

Solves: 58

In this we were given chall.txt which contains the bytecodes of a python program.

Running file on the file really threw me of because, well…

❯ file chall.txt 
chall.txt: Dyalog APL transfer 

Eventually I didn’t see any connection between this and Dyalog, and went to GPT, who told me that it was python bytecode and reconstructed it

Now it didn’t reconstruct it properly, and it was a pretty bad idea to rely on it anyway. In the future, it’s not very hard to reconstruct it by hand. Here are some resources to help you

and something I found really useful was

Dis This

The specific place where GPT was stumbling was

 0 LOAD_GLOBAL 1 (NULL + random)
 2 LOAD_ATTR 2 (getrandbits)
 4 LOAD_CONST 1 (32)
 6 CALL 1
 8 load_fast 0 (i)
10 load_const 2 (195894762)
12 binary_op 12 (^)
14 LOAD_CONST 3 (322420958)
16 BINARY_OP 12 (^)
18 BINARY_OP 5 ()
20 LOAD_CONST 4 (2969596945L)
22 BINARY_OP 5 ()
24 STORE_FAST 1 (password)

It reconstructed this as

return (random.getrandbits(32) ^ 195894762 ^ 322420958) % 2969596945

Which clearly is wrong. What actually is happening is that

 0 LOAD_GLOBAL 1 (NULL + random)
 2 LOAD_ATTR 2 (getrandbits)
 4 LOAD_CONST 1 (32)
 6 CALL 1

is getting a 32-bit random number.

 8 load_fast 0 (i)
10 load_const 2 (195894762)
12 binary_op 12 (^)
14 LOAD_CONST 3 (322420958)
16 BINARY_OP 12 (^)

is just doing i ^ 195894762 and then XORING that with 322420958

Now a tricky part was BINARY_OP 5. Apparently this is multiplication (*). Till python v3.10 the bytecodes were BINARY_MULTIPLICATION etc, but in v3.11 they were changed to BINARY_OP x. I had to visit some forum threads to realise this, and then I confirmed this with Dis This. Which gives us the final math expression as

return (random.getrandbits(32) * ((i ^ 195894762) ^ 322420958) * 2969596945)

Now lets get to the actual exploit. What the challenge is basically an exploit of python’s random module. random uses the Mersenne Twister Pseudo Random Number Generator (“Praise our RNG gods”), which is predictable if you have information of 624 contiguous outputs.

The python randcrack module helps us execute this exploit. We have been given essentially an infinite sequence of numbers generated by random that we pass into randcrack then. Finally once we confirm randcrack is able to predict the numbers, we sent a predicted number to the challenge to get the flag :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
```py
from randcrack import RandCrack
from pwn import process, remote

rc = RandCrack()
# proc = process(["python"] + ["chall.py"])

REMOTE_URL = "chals.bitskrieg.in"
REMOTE_PORT = 7007

proc = remote(REMOTE_URL, REMOTE_PORT)

count = 0

print("================= submitting ===============")
for i in range(624):
    count = count + 1
    print(proc.recvuntil(b'>'))
    proc.sendline(b'1')
    res = proc.recvline()
    numbers = [int(s) for s in res.split() if s.isdigit()]
    password = ((int(numbers[0]) + 1) // 2969596945) // (count ^ 195894762 ^ 322420958)
    print(f"[{count}] ", numbers[0] + 1)
    print("[password] ", password)
    rc.submit(password)

print("================= testing ==================")
for i in range(10):
    count = count + 1
    proc.recvuntil(b'>')
    proc.sendline(b'1')
    res = proc.recvline()
    numbers = [int(s) for s in res.split() if s.isdigit()]
    password = (int(numbers[0]) + 1)
    new = rc.predict_getrandbits(32) * ((count ^ 195894762) ^ 322420958) * 2969596945
    print(f"[{count}] Attempt no {count}")
    print("[password] ", password)
    print("[test] ", new)
    if password == int(new):
        print(f"\033[92m[+] Test {i + 1} Passed \033[0m")
    else:
        print(f"\033[91m[-] Test {i + 1} Failed \033[0m")

print("================= attempting ===============")
for i in range(10):
    count = count + 1
    proc.recvuntil(b'>')
    new = rc.predict_getrandbits(32) * ((count ^ 195894762) ^ 322420958) * 2969596945
    print(f"[{count}] Attempt no {count}")
    print("[*] Submitting number ", new)
    proc.sendline(str(new).encode())
    res = proc.recvline()
    if "Granted" in res.decode().strip():
        print("\033[95m[+] ", res.decode().strip(), "\033[0m")
        break
    else:
        print(f"\033[91m[-] Attempt {i + 1} Failed \033[0m")

proc.close()
```

Reply by Email

Rev 50pt 233 Solves Obfuscation

Praise our RNG Gods#

Related

Praise our RNG Gods
#