randomized random#

题目#

1
# FROM python:3
2
import random
3
with open("flag.txt","rb") as f:
4
    flag=f.read()
5
for i in range(2**64):
6
    print(random.getrandbits(32)+flag[random.getrandbits(32)%len(flag)])
7
    input()

题目分析#

因为题目有用到random库，所以这是MT19937问题，可以参考Xenny师傅的文章：MT19937 分析 | Xenny 的博客。

而题目每次交互里的遍历都会返回random.getrandbits(32)+flag[random.getrandbits(32)%len(flag) ，也就是一个随机32bit数与flag里的一个随机字节的和。

题目需要我们通过 $2^{64}$ 次遍历去还原出flag。

而每次得到的信息（即这个随机32bit数）不仅会因为加法而影响一定的bit数，还是不连续的（因为加flag里的一个随机字节那个地方也用了getrandbits）；所以得取前面一部分bit来打MT19937。

我跟naby师傅当时是想着取前16bit应该是没问题的，但没打出来（今天赛后听Dexter师傅他们说，他们测试发现——影响的bit挺多的，所以取前10bit好点）。

之后就是造矩阵来打MT19937，这个思路的原理可以参考鸡块师傅的这篇文章：2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto

（关键还是在数据量上，数据量不够确实还原不出来正确的state，算是我们当时没注意到的一个问题）

打出来后就是整理出flag了

首先肯定是相减得到flag的那些字符，但单单这样肯定还不能得到flag（毕竟是随机的，所以得到的都是随机的flag字符），但这些随机的flag字符的顺序与flag的长度有关。

而我们知道——flag里的左括号和右括号肯定不会有很多，所以我们分别找两组左括号和右括号所对应的getrandbits，然后相减做gcd就能得到长度，然后就根据长度去整理出flag即可。

exp#

因为整的时候Dexter、鸡块、Lst4r几位师傅他们说了些不同的方式（但都是同一种思路），用时都差不多

第一种就是刚刚说的造矩阵：

点击展开代码

1
# sage 10.5
2
import random
3
from sage.all import *
4
from Crypto.Util.number import *
5
from random import *
6
from tqdm import *
7
from pwn import *
8

9
# 1, get data
10
x,c=[],[]
11
sh = remote("1.95.57.127", 3001)
12
for i in trange(2500):
13
    tmp1=eval(sh.recvline())
14
    sh.send(b"\n")
15
    x.append(tmp1)
16
    c.append(tmp1>>22)
17

18

19
# 2, recover MT and get random bytes of (f_inf, f_len)
20
RNG = Random()
21
length = 19968
22
def construct_a_row(RNG):
23
    # 这里是关键, 一定要跟你已知数据的生成方式一致
24
    row = []
25
    for i in range(2500):
26
        row+=list(map(int, (bin(RNG.getrandbits(32) >> 22)[2:].zfill(10))))
27
        RNG.getrandbits(32)
28
    return row
29

30
L = []
31
for i in trange(length):
32
    state = [0]*624
33
    temp = "0"*i + "1"*1 + "0"*(length-1-i)
34
    for j in range(624):
35
        state[j] = int(temp[32*j:32*j+32],2)
36
    RNG.setstate((3,tuple(state+[624]),None))
37
    L.append(construct_a_row(RNG))
38
L = Matrix(GF(2),L)
39

40
known = []
41
for i in c:
42
    known+=list(map(int, (bin(i)[2:].zfill(10))))
43
print("solve_left")
44
s = L.solve_left(vector(GF(2),known))
45
print("ok")
46
init = "".join(list(map(str,s)))
47
print("init")
48
state = []
49
for i in range(624):
50
    state.append(int(init[32*i:32*i+32],2))
51
print("state")
52

53
prng = Random()
54
prng.setstate(tuple([3, tuple(state+[624]), None]))
55
f_inf = []
56
f_loc = []
57
for i in range(2500):
58
    x1 = long_to_bytes(x[i]-prng.getrandbits(32))
59
    x2 = prng.getrandbits(32)
60
    # print(x1, x2)
61
    f_inf.append(x1)
62
    f_loc.append(x2)
63

64

65
# 3, get flag_len and recover flag
66
loc1, loc2 = [], []
67
i = 0
68
while len(loc1) < 2 or len(loc2) < 2:
69
    if f_inf[i].decode() == "{":
70
        loc1.append(f_loc[i])
71
    if f_inf[i].decode() == "}":
72
        loc2.append(f_loc[i])
73
    i += 1
74
f_len = GCD(loc1[0]-loc1[1], loc2[0]-loc2[1])
75
i = 0
76
flag = ["*"]*f_len
77
while 1:
78
    if all(i != "*" for i in flag):
79
        print("".join(flag))
80
        break
81
    if flag[f_loc[i]%f_len] == "*":
82
        flag[f_loc[i]%f_len] = f_inf[i].decode()
83
    i += 1
84
'''
85
100%|███████████████████████████████████████████████████████████████████████████████| 2500/2500 [01:34<00:00, 26.46it/s]
86
100%|████████████████████████████████████████████████████████████████████████████| 19968/19968 [01:41<00:00, 197.41it/s]
87
solve_left
88
ok
89
init
90
state
91
TPCTF{Ez_MTI9937_pr3d1cTi0n}
92
TPCTF{Ez_MTI9937_pr3d1cTi0n}
93
'''

第二种是使用maple师傅之前整的gf2bv库，算是比较无脑?（不过就是需要多堆点数据）：

点击展开代码

1
# gf2bv
2
# python3
3
import random
4
from gf2bv import LinearSystem
5
from gf2bv.crypto.mt import MT19937
6
from tqdm import *
7
from pwn import *
8
from Crypto.Util.number import *
9
import pickle
10

11

12
def mt19937(bs, out):
13
    lin = LinearSystem([32] * 624)
14
    mt = lin.gens()
15

16
    rng = MT19937(mt)
17
    zeros = []
18
    for o in out:
19
        zeros.append((rng.getrandbits(32)>>22) ^ int(o))
20
        rng.getrandbits(32)
21
    sol = lin.solve_one(zeros)
22

23
    rng = MT19937(sol)
24
    pyrand = rng.to_python_random()
25
    return pyrand
26

27
if(0):
28
    print(random.getstate()[1])
29
    x,c=[], []
30
    for i in trange(3500):
31
        tmp1=random.getrandbits(32)
32
        random.getrandbits(32)
33
        x.append(tmp1)
34
        c.append(tmp1>>22)
35
    RNG = mt19937(int(10), c)
36
    for i in trange(832):
37
        xx = RNG.getrandbits(32)
38
        assert x[i] == xx and c[i] == (xx>>22)
39
        RNG.getrandbits(32)
40

41
if(1):
42
    # 1, get data
43
    nums = 5000
44
    sh = remote("1.95.57.127", 3001)
45
    out = []
46
    cout = []
47
    for _ in trange(nums):
48
        x = eval(sh.recvline())
49
        out.append(x)
50
        cout.append(x>>22)
51
        sh.send(b"\n")
52
    # 2, recover MT and get random bytes of (f_inf, f_len)
53
    RNG = mt19937(16, cout)
54
    f_inf = []
55
    f_loc = []
56
    for i in range(nums):
57
        x1 = long_to_bytes(out[i]-RNG.getrandbits(32))
58
        x2 = RNG.getrandbits(32)
59
        f_inf.append(x1)
60
        f_loc.append(x2)
61
    # 3, get flag_len and recover flag
62
    loc1, loc2 = [], []
63
    i = 0
64
    while len(loc1) < 2 or len(loc2) < 2:
65
        if f_inf[i].decode() == "{":
66
            loc1.append(f_loc[i])
67
        if f_inf[i].decode() == "}":
68
            loc2.append(f_loc[i])
69
        i += 1
70
    f_len = GCD(loc1[0]-loc1[1], loc2[0]-loc2[1])
71
    i = 0
72
    flag = ["*"]*f_len
73
    while 1:
74
        if all(i != "*" for i in flag):
75
            print("".join(flag))
76
            break
77
        if flag[f_loc[i]%f_len] == "*":
78
            flag[f_loc[i]%f_len] = f_inf[i].decode()
79
        i += 1
80
'''
81
100%|███████████████████████████████████████████████████████████████████████████████| 5000/5000 [02:59<00:00, 27.93it/s]
82
TPCTF{Ez_MTI9937_pr3d1cTi0n}
83
'''

后记#

这次算是对MT19937这个问题有了一点理解，希望下次能会分析吧

(至于后面的题，因为当时没全部下载，所以等后面看别的师傅的blog里有没有再接着复现吧)