W'Blog

Wbuildings的自勉小屋

0%

MT19937实战

发表于 分类于 Valine：
本文字数： 54k 阅读时长 ≈ 49 分钟

人间何所以，观风与月舒。

前言

回首看MT19937，似乎当脚本小子也不错，常规的四种题型是可以解的，魔改的大概也只能去啃原理了

此篇仅供常规解题所需

例题：

[NKCTF2023]real_MT

题目：

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
61
62
63
64
65
66
67
68
69
70
import random
import signal

def guess_number_1():
    randoms = []
    for _ in range(208):
        randoms.append(random.getrandbits(96))

    print("randoms = "+str(randoms))
    number = str(random.getrandbits(96))
    guess = str(input("Guess after number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_2():
    number = str(random.getrandbits(96))
    randoms = []
    for _ in range(627):
        randoms.append(random.getrandbits(32))

    print("randoms = "+str(randoms))
    guess = str(input("Guess pre number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_3():

    def _int32(x):
        return int(0xFFFFFFFF & x)  
    def init(seed):
        mt = [0] * 624
        mt[0] = seed
        for i in range(1, 624):
            mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
        return mt[-1]
    number = random.getrandbits(32)
    print("last number = "+ str(init(number)))
    guess = int(str(input("Guess seed number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_4():
    def extract_number(y):
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        return y&0xffffffff

    number = random.getrandbits(32)
    print("extract number = "+ str(extract_number(number)))
    guess = int(str(input("Guess be extracted number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)
    

print("Welcome to the Mersenne Twister basic challenge. Please try to solve 20 challenges in 60 seconds.")
signal.alarm(60)

for i in range(20):
    print("Round: "+str(i+1))
    random.choice([guess_number_1,guess_number_2,guess_number_3,guess_number_4])()
    print("Good job!")

flag = open('/flag').read()
print("Congratulations on passing the challenge. This is your flag: " + str(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
def guess_number_3():

    def _int32(x):
        return int(0xFFFFFFFF & x)  
    def init(seed):
        mt = [0] * 624
        mt[0] = seed
        for i in range(1, 624):
            mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
        return mt[-1]
    number = random.getrandbits(32)
    print("last number = "+ str(init(number)))
    guess = int(str(input("Guess seed number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_4():
    def extract_number(y):
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        return y&0xffffffff

    number = random.getrandbits(32)
    print("extract number = "+ str(extract_number(number)))
    guess = int(str(input("Guess be extracted number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

这两个直接跟着badmonkey师傅无脑代就行：浅析MT19937伪随机数生成算法 - badmonkey

求seed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 3 seed

from gmpy2 import invert

def _int32(x):
    return int(0xFFFFFFFF & x)

def invert_right(res,shift):
    tmp = res
    for i in range(32//shift):
        res = tmp^res>>shift
    return _int32(res)

def recover(last):
    n = 1<<32
    inv = invert(1812433253,n)
    for i in range(623,0,-1):
        last = ((last-i)*inv)%n
        last = invert_right(last,30)
    return last
seed = 578972588
print(recover(seed))

求extracted

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
# 4 extracted

# right shift inverse
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp


# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def recover(y):
    y = inverse_right(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right(y,11)
    return y&0xffffffff

extract = 1531729985
print(recover(extract))

预测随机数

1
2
3
4
5
6
7
8
9
10
11
def guess_number_1():
    randoms = []
    for _ in range(208):
        randoms.append(random.getrandbits(96))

    print("randoms = "+str(randoms))
    number = str(random.getrandbits(96))
    guess = str(input("Guess after number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

预测后面的一个96bit的随机数

常规的每个数都是32bit，而这里badmonkey师傅给的也是预测32bit数的脚本，所以我们要想办法把96bit的数转换成3个32bit的数，观察如下测试代码

1
2
3
4
5
6
7
8
9
10
11
12
import random
random.seed(1)  #掷随机数种子为1从而确保随机数产生的一致性
print(hex(random.getrandbits(32)))
print(hex(random.getrandbits(32)))
print(hex(random.getrandbits(32)))
random.seed(1)  #重新掷随机数种子
print(hex(random.getrandbits(96)))

# 0x2265b1f5
# 0x91b7584a
# 0xd8f16adf
# 0xd8f16adf91b7584a2265b1f5

可以看到一个96bit随机数是由三个连续的32bit随机数拼接而成的，并且第三个随机数为高位，第一个随机数为低位，所以我们修改一下代码即可：

1
2
3
4
5
6
c = []
for i in randoms:
    a = hex(i)[2:]
    c.append(int(a[len(a) // 3 * 2:], 16))
    c.append(int(a[len(a)//3:len(a)//3*2],16))
    c.append(int(a[:len(a) // 3], 16))

64bit随机数同样如此，如下是预测随机数脚本（有点很奇怪，有次测试的时候预测结果错了，但其他的是正确的）：

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
# 1 after number
from random import Random

def invert_right(m,l,val=''):
    length = 32
    mx = 0xffffffff
    if val == '':
        val = mx
    i,res = 0,0
    while i*l<length:
        mask = (mx<<(length-l)&mx)>>i*l
        tmp = m & mask
        m = m^tmp>>l&val
        res += tmp
        i += 1
    return res

def invert_left(m,l,val):
    length = 32
    mx = 0xffffffff
    i,res = 0,0
    while i*l < length:
        mask = (mx>>(length-l)&mx)<<i*l
        tmp = m & mask
        m ^= tmp<<l&val
        res |= tmp
        i += 1
    return res

def invert_temper(m):
    m = invert_right(m,18)
    m = invert_left(m,15,4022730752)
    m = invert_left(m,7,2636928640)
    m = invert_right(m,11)
    return m

def clone_mt(record):
    state = [invert_temper(i) for i in record]
    gen = Random()
    gen.setstate((3,tuple(state+[0]),None))
    return gen


randoms = [55015607074857799292945552290, 49368042755482977011736956173, 40475374240531115107595906636, 52147615048581670023735755450, 13432490767545507105189747763, 24440678017972777884814646255, 32822903152999092153407655597, 8563483583446603233686286354, 75732019275746461853540401495, 36842332206659125653150736486, 76786413054424156228987909265, 78728868918063155711331208027, 68111503649325447384558973315, 50046539350414059782746722603, 33122956341131312047186478550, 47134379833914353599100802574, 14506941828436962820850816482, 16254006011206386851511190777, 53774746810651233261166083709, 57317412206054586514985875280, 43011044274622942766585189176, 21510983328491776879720475647, 68805188235988349436606490157, 68293687378252177576750854213, 64020092712881170155616652147, 58788852915482172394398327520, 20534731592145885333097885636, 71497885157511490073528334436, 50079126675284942137464435871, 16433905363688130336892639414, 10833644831894048938957163773, 61837597918870726435017132850, 50007378472767284514600652443, 13242758280359098364681702807, 48040447462883040840110279722, 48653833299736009023667402599, 61877052829753339768672826777, 55104138447302791542841950167, 59956782054709979669719351421, 33622933736356173639796248572, 70720508316358691710097244967, 26438465850133558815351580879, 12121649600344247919530245458, 59429702128155774929559418436, 8461855977540480946850517835, 35371049050859796434557316156, 74900517442122255478113670139, 56015804116725775644082181473, 54019918704797178896937181953, 46449490759360975867530830160, 21716938523285444592131111037, 4075915261354769937217394891, 71101712150556394609286976122, 77514446308635805069858161218, 30443551680738939325710619401, 51330659874633330020137362887, 16870162608087608659692436972, 36332661698483296611490764287, 38912147134106871206560383319, 66798268847122499800706103042, 241691625661529797405764102, 9680620382995429570437419894, 54281462677774536994926184946, 49156921844074280073449443668, 47003617901112210542122896375, 20630134319865926707841141605, 38539127713936043329828502512, 37765649689660950654295018296, 27519165366018178520157118526, 47311700897513991864703815914, 14844131572803548743566512704, 72315716735652440986087523229, 46411344686639197025534075618, 13959184897278020398348948659, 2079854302954576073339089565, 39428786840574943257095970633, 33458396202396229906230251418, 69814672396568547483000493475, 28451062576030293943028542769, 3150653107998963723272095718, 20792548261825482531270352147, 69131192563757378564191442243, 73581103283131546986544846269, 32168289412017414311931877308, 55734763237596421172118618970, 37808961718727478136990696303, 22904874676153031620664377715, 9794575345156074603503087671, 22456694023771898844190118878, 49901970266243771395136385496, 63113371794658901555756959046, 68738124366682093927457951250, 23306235486349427954282639191, 43594485853233707551383467628, 50747180681744235554964992870, 49862479356739272497472347214, 38434690316151369964072773399, 71467050353277898958372067109, 55346669078871118497310884600, 46017420217054938248863989011, 75363033386622698885356870859, 10369764848153462639554152052, 75890142526899080264345852084, 9535759402085584783757952808, 43522044721852245514275493334, 12464589274296723227328792626, 78676543113595295732206638118, 60116759495604753189426160756, 69969854635185954403204801589, 15244509737688480815229679004, 36868877814286665666603704724, 25296352719228197917967642599, 27714369660917369969714529637, 7673110772037676634707790378, 66678444104365177982652169620, 46842636677378560041798283187, 10144943294980146082555306558, 28284306659807251586984133000, 33490472759408013029651749585, 77977414783931140205233073617, 69530485613806297267022583522, 76520003652664840680181807019, 46932273878708136776868709933, 55587849334378587663972698777, 288744469797385122841458086, 41277555669463912046072519012, 4464200409916053651301885032, 40054592246599648525169317693, 19475356311294822865721674381, 78967801470334524961687238739, 75822644069771873149506932458, 43938875242093048649223251016, 38961281929520042194905361090, 21610082723530059512385550253, 57418757224608120261793422587, 72515591359993311229453026924, 53301906528555214119355718384, 62399938403321209620318734938, 29562948809863356281824237526, 64690511731475499536620402074, 61422219087048013104282624678, 20023299367896362817857259034, 1531978217124909227300934212, 8362602216400318325888882470, 75999045381397120509496119808, 24819648371744754442222408890, 75932237139374495603284677727, 11591629473858684168400446684, 75483926784518263475169289687, 55768847294454228602227998151, 35105596201056028460562538709, 48075470868361149890782793466, 68011918805791011054681166147, 71379711286148023971490418355, 5119093941579935754141497093, 53547827525583375748301266038, 8537501347007365109158293206, 49644668676789081527660032954, 22515713345276622847996100404, 55307392324473859445909519983, 10994480124121534718832780851, 65533932078012255426667262659, 43392581419477495155490691253, 6149858215235626580350564774, 11427015895083257860925651246, 1213227811506969183950341669, 35938550903795041826608209051, 73091816395793401072374399076, 12197443447940928492569868668, 25301621853357018223709312786, 5689796934241659738266713001, 2613230292238434599188292344, 42124474617992669523056747325, 35194954579809956401055788693, 50290306214852192605264941404, 11584578367073737286597097637, 23330546567461178065917588032, 31343688234160714794757165377, 63918823993048504659024692114, 27365510636493497037417818163, 30638666912149387553328229778, 54531935194478667388418879230, 41072843969336419779445369322, 60930376536086388437175835196, 55947262970830901337865668896, 44515932960074495211895851717, 14252286294934938035868124826, 35800368864810336116694682268, 70076466250975352052336380744, 3518883683220809834826882516, 21235446402566298534375767444, 35231908696746966244552935642, 14398535620050895095986981975, 19103988715582383425140328987, 14062642498531815460021440383, 77110266168617581807736354811, 54409146707444728728561076439, 64253672045037421891482500882, 36181743183047944158650802993, 26890907171354385267615627636, 45223610791479728329076327440, 16690474955515435722262505229, 2814228033061481589868246822, 77863107456708086832326043708, 1351886029839065156773853534, 65968244564445520569592572140, 35354808513582870523085136830, 52007148783750186143061130576]

c = []
for i in randoms:
    a = hex(i)[2:]
    c.append(int(a[len(a) // 3 * 2:], 16))
    c.append(int(a[len(a)//3:len(a)//3*2],16))
    c.append(int(a[:len(a) // 3], 16))

g = clone_mt(c)
for i in range(208):
    g.getrandbits(96)

after = g.getrandbits(96)
print(after)
# 73177359307009435987099712513

回溯pre number

1
2
3
4
5
6
7
8
9
10
11
def guess_number_2():
    number = str(random.getrandbits(96))
    randoms = []
    for _ in range(627):
        randoms.append(random.getrandbits(32))

    print("randoms = "+str(randoms))
    guess = str(input("Guess pre number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

这里我倒是把state = backtrace([0]*4+partS)[:624] 调成了[1:625]，不知道是啥原因结果就正确了，做题时倒是可以尝试多调试一下

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
61
62
63
64
# 2 pre number
from random import Random
# right shift inverse
def inverse_right(res,shift,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp >> shift
    return tmp

# left shift with mask inverse
def inverse_left_values(res,shift,mask,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(3,-1,-1):
        tmp = state[i+624]^state[i+397]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        # recover the highest bit
        res = tmp&high
        # recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
        tmp = state[i-1+624]^state[i+396]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        res |= (tmp)&low
        state[i] = res
    return state

def recover_state(out):
    state = []
    for i in out:
        i = inverse_right(i,18)
        i = inverse_left_values(i,15,0xefc60000)
        i = inverse_left_values(i,7,0x9d2c5680)
        i = inverse_right(i,11)
        state.append(i)
    return state

randoms = [3131844436, 1710395493, 2040128529, 484345499, 2462793287, 3676280954, 1262783325, 2668249231, 1577554939, 1094686367, 3249775482, 2535455373, 1580873401, 3668020441, 600047797, 2368372766, 4131413888, 3881611699, 1654375267, 1363668945, 789513452, 3762247007, 953812596, 1506373208, 3472069184, 2545441793, 2826549707, 575091032, 1773264197, 192501172, 721152596, 2765035108, 1254008657, 2817100002, 3970642288, 1818378227, 1140978336, 3485195271, 386023852, 3403435021, 1144997183, 3945241205, 1211988218, 3434015373, 2046254427, 620893433, 3293410181, 3112865039, 1171882312, 1264231357, 2966804259, 43998805, 3637672398, 2681960565, 2709103871, 1456705725, 1660473171, 3820308210, 916345361, 66696421, 1234084934, 2260115865, 4103495816, 1445850634, 1688161812, 3904081009, 2933234077, 3523756803, 490871410, 2644412567, 648761244, 3530982511, 1024884722, 383286216, 2204575995, 3268537218, 2908281468, 749867101, 1077132488, 3270723079, 3585247012, 1269156557, 3096777547, 1366205746, 2642565074, 1356154486, 2371705450, 3277675427, 1949359019, 3911342223, 2302199881, 1787074024, 1176483441, 3382524643, 1726938894, 3732701826, 3873136097, 648865101, 1373666656, 1977863320, 2275109604, 1452217785, 2796416538, 4169530804, 903377449, 1230239737, 1392065473, 3204364427, 334317583, 2956184008, 2411445068, 41487849, 721765697, 1443541315, 2093099003, 893095099, 4074956390, 3098600401, 314246690, 1836298915, 651584091, 1915188462, 2767672465, 2165385064, 1519266519, 4022389379, 1728592657, 4225918363, 1086688090, 2667629859, 2236562855, 397758955, 3266197863, 1547047859, 1769483950, 1054690627, 3821081636, 4243049300, 2113976324, 3465256288, 3394237832, 1447852828, 3375689141, 3469852507, 108642640, 1417582614, 2226381889, 1108355161, 1107879584, 994843797, 3134161877, 1827259162, 2541380730, 1414991982, 66563096, 17558729, 2523246427, 2306870077, 4229357864, 1794849582, 342768726, 2537134735, 3992316097, 2390770768, 58919292, 3299454886, 47094719, 192273779, 576620652, 2653473543, 732566086, 3494470827, 375184426, 3046525929, 1917007196, 437621599, 226187925, 279460746, 2504991047, 2720647095, 1726214839, 2662580336, 310633501, 4201239133, 1411404284, 2797124852, 1009997203, 1619452767, 542751538, 2044343202, 634443864, 779388116, 1029257449, 214975482, 3625137656, 70328808, 3310617589, 1031353996, 3450854594, 679561624, 2983441457, 2349421851, 2795342193, 1652530355, 677860488, 1518458320, 3142116487, 1973355550, 3385226917, 823024989, 2787730966, 2961286907, 1903136206, 875506150, 4174650755, 3561996691, 1002531559, 4128921823, 1282902829, 1020680621, 3136992997, 1708678754, 1181634294, 3235211337, 660397562, 3060688465, 3934130449, 608548952, 1854108908, 4127434065, 1301263785, 980156946, 1702117699, 3806397832, 4159471046, 2458928134, 3866388551, 3053272844, 2378284756, 2054070916, 3825976364, 2336292623, 122801644, 3993151514, 4096144143, 3814616160, 3994433936, 3462289286, 4243017170, 3426172061, 2583801103, 212067227, 3534029236, 36875405, 4045543218, 187217458, 557973024, 444948938, 4077939216, 3268643877, 2993470198, 1493479975, 2130068040, 2299545462, 830879239, 1365763854, 478049374, 2074554524, 1821969699, 3959885144, 3646002934, 2672029263, 2753142311, 2688990434, 1863524787, 1040793750, 3125785761, 3638172148, 3540865755, 3757848958, 1414800242, 2928259859, 1861735245, 4235431182, 2862287091, 3428851640, 486857161, 1352945718, 3486730778, 883640701, 1296225663, 3655133993, 3830695918, 4200683490, 1115097527, 530632520, 2536734545, 3330209702, 692913861, 4173632848, 4182050947, 4099357993, 1992990649, 2689587606, 1397545631, 4049403842, 4198228871, 3313893404, 1356111161, 2718318666, 358872243, 1175402713, 1456360316, 1921597330, 1812196593, 1076515795, 2119895733, 3900210292, 3619512492, 2837094060, 167935, 2181313587, 2341488060, 2373964485, 952568298, 1842854296, 4045471217, 1939489272, 1473031514, 3060284468, 2661841551, 3031889599, 2907382437, 4286947591, 3584889180, 3005106221, 2727316663, 3931261841, 3490523908, 3780389181, 3743857672, 765390813, 1987225828, 2723892340, 1163275304, 3062347486, 2349224851, 787739531, 378052259, 2055505948, 3607986110, 3432516938, 1221088847, 3101819143, 3556683912, 4073221057, 577365487, 1860652081, 711563646, 1039004198, 2112807179, 809098012, 2811893098, 766665936, 2107894153, 3205397082, 1062442066, 3003811473, 2495630660, 681813468, 1247402813, 3015978207, 1908481948, 402536178, 1017534355, 3137699610, 1243214519, 2002971476, 2751738083, 4202633831, 2149611209, 2901851985, 3441366308, 1306405097, 1436920351, 3206822252, 3135875087, 3112772405, 2155012041, 4166786019, 2388412286, 3743595466, 1504277877, 2570252102, 1525324343, 3988357159, 2041485802, 3706379242, 1567644399, 3629389711, 3521760489, 2606285630, 2378614660, 2278092070, 3134112923, 1103492149, 2544530864, 1658255844, 1898801584, 904222527, 2957105662, 3389876719, 2456986124, 2695204025, 646113342, 4091650903, 2199478453, 3706005283, 612268437, 2484284336, 2662191700, 1940190622, 233733292, 4012212083, 2500822436, 541451268, 643453712, 3232122867, 3584484460, 648833258, 1768628917, 3984796041, 1411122343, 2111633947, 4054603898, 3486423013, 1936378246, 2642145436, 3750457204, 4014965456, 1555132787, 1596915262, 3543904379, 221214936, 3568886655, 509377956, 2735720233, 2280845785, 2244193115, 2491466696, 2899402863, 3409575433, 4090467960, 2298184706, 3445239101, 3543853500, 3002886346, 1957091440, 2232700177, 1214082317, 3253617000, 612662508, 1967176113, 1477788048, 2598998495, 3732580449, 3526698478, 3205961233, 1596289512, 3563960905, 701926946, 2091717748, 497084240, 1431153592, 2121887464, 2717201053, 1708163770, 2288780659, 695843074, 1804583145, 3549082991, 2132631780, 1404284920, 1812914597, 3786808737, 1238178729, 144709682, 2720425065, 2567630528, 3687426833, 921498776, 3846928815, 3992245405, 1523301292, 2975368564, 2794392842, 3915184151, 2374520221, 3570983257, 576777516, 434172278, 3432585614, 2488328901, 3502901745, 2189466832, 3258959396, 3652453078, 2646058339, 1487691505, 3489122606, 2095120777, 3444908045, 2169560914, 1142429299, 3290048052, 2989735964, 3394182052, 629348441, 3819996826, 45644271, 490572833, 497254234, 454033500, 4139957703, 1469582655, 1871913285, 3541204007, 1168363870, 887995922, 2876697335, 183207833, 3610125137, 3750324442, 1492867425, 3047407108, 3149823622, 3473939398, 3602043139, 823675959, 844582032, 3998968330, 2393470080, 2512238135, 67167808, 1611487897, 2830420861, 4112505264, 1473571356, 2312858766, 871689440, 556193926, 1001003215, 1273007741, 762017629, 2038148387, 4279168802, 2408310663, 2054122309, 42020314, 1396677628, 3773376680, 1932770810, 2471957404, 2226052083, 2029396226, 3765862340, 1050629836, 3182006232, 2413024927, 4016684643, 2024438409, 4090205995, 3597880762, 2506376035, 3927261145, 4205690402, 2307681663, 3274838512, 3523789777, 359904705, 1651827754, 3293539170, 3181510821, 1493999036, 1649777650, 4154519231, 1329665122, 90822454, 999884567, 141607911, 3884251899, 2825791367, 1739573277, 3234181642, 933041054, 186550284, 4092869914, 1043976374, 413839654, 4146441955, 2162431794, 1528203403, 3113434991, 1963838396, 1914312708, 2228058801, 1066392891, 3709434263, 3444101460, 822257454, 528906696, 2815319529, 1900590565, 1548596297, 2176062412, 2101521651, 4151077085, 2146296787, 837380469, 3104944571, 3846825052, 369339, 247134846, 3774886839, 2721198553, 3033768060, 4071240934]

partS = recover_state(randoms)
state = backtrace([0]*4+partS)[1:625]

prng = Random()
prng.setstate((3,tuple(state+[0]),None))
print(prng.getrandbits(96))
# 32029162575545328566623624142

此题的定位还是交互题，但由于没有复现环境，懒得搭（主要是还不会），就本地挨个测试了一下，最后也是成功输出了flag，不过没有写交互脚本以及统一的格式

test：

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
61
62
63
64
65
66
67
68
69
70
71
72
73
import random
import signal

def guess_number_1():
    randoms = []
    for _ in range(208):
        randoms.append(random.getrandbits(96))

    print("randoms = " + str(randoms))
    number = str(random.getrandbits(96))
    guess = str(input("Guess after number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_2():
    number = str(random.getrandbits(96))
    randoms = []
    for _ in range(627):
        randoms.append(random.getrandbits(32))

    print("randoms = " + str(randoms))
    guess = str(input("Guess pre number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)


def guess_number_3():
    def _int32(x):
        return int(0xFFFFFFFF & x)

    def init(seed):
        mt = [0] * 624
        mt[0] = seed
        for i in range(1, 624):
            mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
        return mt[-1]

    number = random.getrandbits(32)
    print("last number = " + str(init(number)))
    guess = int(str(input("Guess seed number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_4():
    def extract_number(y):
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        return y & 0xffffffff

    number = random.getrandbits(32)
    print("extract number = " + str(extract_number(number)))
    guess = int(str(input("Guess be extracted number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)


print("Welcome to the Mersenne Twister basic challenge. Please try to solve 20 challenges in 60 seconds.")


for i in range(20):
    print("Round: " + str(i + 1))
    random.choice([guess_number_1, guess_number_2, guess_number_3, guess_number_4])()
    print("Good job!")

flag = open('flag').read()
print("Congratulations on passing the challenge. This is your flag: " + str(flag))

前面说到预测和回溯都稍微会遇到一点问题，所以总是会有大佬站出来，上传了有很多相关的python库，我这里选择的是 ExtendMT19937Predictor

可以根据Predict、Backtrack的使用示例来进行预测和回溯，如下是exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def attack1(list1):
    predictor = ExtendMT19937Predictor()
    for i in range(208):
        predictor.setrandbits(list1[i], 96)    # 是将已有的随机数填入，从而预测或回溯随机数
    return predictor.predict_getrandbits(96)


def attack2(list1):
    predictor = ExtendMT19937Predictor()
    for i in range(627):
        predictor.setrandbits(list1[i], 32)
    for i in range(627):
        predictor.backtrack_getrandbits(32)
    x = predictor.backtrack_getrandbits(96)
    return x

[NKCTF2023]fake_MT

题目源码不说和real_MT长得像，简直是一模一样，一说这题是python2的环境

题解如上，和real_MT一样

补充：

2024-7-18

一直被忽略的第五个题型，这里面的扩展题型里，低于32字节的MT19937，例题给的是高位的 1 bit

easy_random

WKCTF 2024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

flag = b'WKCTF{}'
pad_flag = pad(flag,16)
key = random.randbytes(16)
cipher = AES.new(key,AES.MODE_ECB)
print(cipher.encrypt(pad_flag))
# b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
with open('random.txt','w') as f:
    for i in range(2496):
        f.write(str(random.getrandbits(8))+'\n')

（附件就不给了，可以自己生成测试）

上面讲了 32bit 以上的随机数是拼接而来的，而32bit 以下则不行，

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
import random

random.seed(1)
print(hex(random.getrandbits(8)))
print(hex(random.getrandbits(8)))

random.seed(1)
print(hex(random.getrandbits(32)))
print(hex(random.getrandbits(32)))

# 0x22
# 0x91
# 0x2265b1f5
# 0x91b7584a
# 22464

random.seed(1)
print(hex(random.getrandbits(16)))
print(hex(random.getrandbits(16)))

random.seed(1)
print(hex(random.getrandbits(32)))
print(hex(random.getrandbits(32)))

# 0x2265
# 0x91b7
# 0x2265b1f5
# 0x91b7584a

按顺序来讲，得到的每一个 8bit 是对应 32bit 的前八位，如何得来？也就是先生成 一个32bit的，再右移24bit，得到 8 bit

所以32 bit 以下的随机数不能进行拼接

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
import random
from Crypto.Util.number import *

random.seed(1)
print(random.randbytes(4))
print(random.randbytes(4))
random.seed(1)
print(random.randbytes(8))

random.seed(1)
print(hex(bytes_to_long(random.randbytes(8)))[2:])
random.seed(1)
print(hex(random.getrandbits(64))[2:])


random.seed(1)
print(long_to_bytes(random.getrandbits(32)))
print(long_to_bytes(random.getrandbits(32)))
random.seed(1)
print(long_to_bytes(random.getrandbits(64)))

# b'\xf5\xb1e"'
# b'JX\xb7\x91'
# b'\xf5\xb1e"JX\xb7\x91'
# f5b165224a58b791
# 91b7584a2265b1f5
# b'"e\xb1\xf5'
# b'\x91\xb7XJ'
# b'\x91\xb7XJ"e\xb1\xf5'

可以看到 生成随机字节 和随机数的拼接方式不一样，

后者后面生成的随机数在高位，先生成的随机数在低位

前者则相反，

所以按照上面我们的拼接方法再逆序即可得到 key

或者看到 生成的 4字节和 32 bit 的关系是逆序的，这种低字节在高位的情况称为 小端序 ，也可这样处理 key

题解：

通过 badmonkey 佬的方法，黑盒测试，在GF(2)上，有

$X·T = Z\Longrightarrow X=Z·T^{-1}$

其中X,Z为1 x 19968 的向量，T为19968 x 19968 的矩阵

我们可以令 X = (1,0,0…,0)，此时得到 Z 的结果 为 T 的第一行，再令 X = (0,1,0…,0)，以此类推得到全部 T

我们需要注意的是，文中说明了我们构造的T不是满秩的，求出的第一个32bit的随机数不够准确，我们还需要去还原第一个state，再来进行预测得到完整的32bit随机数

exp：

例题是 1 bit 的，这里是 8 bit 的，据此微改脚本

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
from sage.all import *
from random import Random
from tqdm import *
prng = Random()
length = 19968

def myState():
    state = [0]*624
    i = 0
    while i<length:
        ind = i//32
        expont = i%32
        state[ind] = 1<<(31-expont)
        s = (3,tuple(state+[0]),None)
        yield s
        state[ind] = 0
        i += 1

def getRow():
    rng = Random()
    gs = myState()
    for i in range(length):
        s = next(gs)
        rng.setstate(s)
#         print(s[1][0])
        data=[]
        for i in range(length // 8):
            data.extend(list(bin(rng.getrandbits(8))[2:].zfill(8)))
        data=[int(i) for i in data] # 只有1行，还是length长度
        row = vector(GF(2),data)
        yield row

def buildBox():
    b = matrix(GF(2),length,length)
    rg = getRow()
    for i in tqdm(range(length)):
        b[i] = next(rg)
    return b # length * length

# X = Z*(T^-1)
def recoverState(T,leak):
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i * 32:(i + 1) * 32], 2)
        state.append(tmp)
    return state

# 根据题型2,还原state,有两种可能,这时候可以用暴破
def backfirst(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    tmp = state[623] ^ state[396]
    if tmp & high == high:
        tmp ^= mask
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<= 1
    return (1 << 32 - 1) | tmp & low, tmp & low

def readrandom():
    c = []
    with open('random.txt','r') as f:
        for i in f.read().split():
            c.append(int(i))
    return c

def pwn(leak,state,guess1,guess2):
    prng = Random()
    originState = prng.getstate()
    state[0] = guess1
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("first")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("true")
            print(state)
            return
    state[0] = guess2
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("second")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("true")
            print(state)
            return

def main():
    T = buildBox()

    leak = readrandom()
    leak1=[int(j) for j in "".join([bin(i)[2:].zfill(8) for i in leak[:19968//8]])]
    leak1 = matrix(GF(2), leak1)
    # 恢复state
    state = recoverState(T,leak1)
    print("state恢复完成")
    # 两种可能
    guess1, guess2 = backfirst(state)
    print(guess1, guess2)
    pwn(leak,state,guess1,guess2)
    
main()

我们用这个得到 state去 还原题目当时的 state（seed？😅），进行预测 624个32bit的随机数用以回溯

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
from random import Random
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from extend_mt19937_predictor import ExtendMT19937Predictor

prng = Random()
state = [2922114156, 2886276701, 1168768544, 2339187170, 3551087255, 117510054, 4232565172, 1076139110, 3366831833, 1734453078, 4105913658, 1066792668, 2395352043, 785096749, 3707690263, 2430171307, 2064716469, 1119720065, 1112222395, 2136656989, 2232844740, 388978998, 1363102788, 67899517, 457789137, 3527002829, 1187847099, 1188611575, 3830294635, 3760337941, 297081839, 3230408812, 2906355860, 279725084, 3056220997, 1053068885, 3252084646, 2818726015, 3615795115, 2751222655, 74688614, 1452880497, 426221319, 1680367484, 4211465923, 908441837, 2290937869, 526329269, 3225608663, 350552485, 885538125, 3496826412, 3347875222, 2730243675, 1823616219, 1474037291, 2474670592, 1175091387, 1527449390, 2024565653, 2185945759, 902338428, 3571876882, 632524934, 1235569406, 3612682285, 2727233684, 2085380963, 1570339017, 3839696585, 1482742582, 646051896, 3804319832, 2113555238, 4150326517, 2606046640, 1454130831, 1919843931, 1018624146, 1956310311, 1162868231, 1118548906, 974692065, 3020424226, 2996838388, 1724936385, 1668410782, 3044755338, 3710133971, 1043581839, 362583150, 3880481779, 114234888, 1724135673, 1280834309, 2958310395, 3502226151, 620064160, 3244210820, 3839287479, 2283659292, 405764632, 29535149, 2759062778, 1662916252, 2374319319, 3359789079, 1896011543, 1991740933, 2041947596, 3393060496, 996086198, 193135800, 1184463268, 819767446, 410330102, 569788256, 3880255000, 340523190, 885031563, 2752345656, 4116368372, 1738848623, 1895472503, 85502529, 334873925, 3543996685, 3082948803, 3195880838, 1458851187, 2843458392, 20236078, 3136689072, 2121777470, 3543587943, 3590933177, 4057799526, 1241162800, 1014541188, 1031410742, 267989518, 92604561, 2190353015, 87786611, 435741463, 3800398555, 1860727248, 2608606593, 287619193, 768990059, 1686137462, 3255556540, 3234299857, 2087562050, 1575350832, 1982640551, 1476745138, 2757668599, 108958643, 337813164, 273001595, 3515727084, 2976758889, 2674818924, 2133197017, 3709052669, 1992118633, 2421927781, 174599786, 3608298365, 1708985493, 3925831183, 3063611093, 3852984733, 540242111, 1623482619, 1874921843, 1317809124, 2774735715, 3828180102, 1997343223, 1516869708, 941992323, 307089973, 368181535, 163007409, 596938343, 1686397275, 52708329, 230996593, 3597201983, 378926364, 3618422671, 2062721049, 3659976071, 546629459, 3976307656, 1509609055, 3677736141, 1613243397, 1378877471, 531534610, 2602178644, 4099876535, 1394187732, 1706260244, 1842911215, 3381571710, 456693813, 1667668257, 792813840, 4044011316, 1391972141, 1677638507, 1467741933, 2542725716, 3261642613, 1122181516, 1726857655, 2765884383, 2563231823, 1890137479, 3462591813, 290505918, 3480784421, 4146013364, 906268950, 1460571462, 625398701, 1868955581, 2562420879, 3524561573, 2480663847, 424010572, 3760440358, 506451740, 2616205788, 3835513223, 2698078113, 933669512, 2259175222, 1766445936, 3062774434, 3383207496, 165724374, 717679250, 872303977, 1054921507, 1640987195, 2398705310, 744526846, 2142916476, 3769314780, 3643489144, 906983325, 1001096018, 1522376663, 3516789445, 425379249, 1807654888, 1584889396, 996500676, 2138028000, 1877118731, 2780715755, 56317932, 994780643, 231703463, 1590924826, 449553992, 1970334362, 3631415563, 2378887069, 2645995105, 604040985, 766274135, 2897107084, 3122401328, 604584226, 3514594183, 3159592392, 539086862, 1966827756, 1548312674, 2223920152, 4193868755, 2604831097, 2301554299, 2919432501, 3445772747, 221908018, 1919849944, 1707243688, 1311680342, 1132835813, 824121832, 2623654824, 4245764621, 1669541543, 793028119, 1400611299, 2330555992, 1295319061, 2376883177, 3054784982, 1534527889, 3381065612, 431181624, 2520679460, 1612115175, 3417053178, 3202101207, 4112825474, 209873225, 3982289256, 3175605361, 1007754107, 1533969733, 3657972615, 1233249703, 1775877579, 2812100730, 3215107528, 1781386145, 3025989255, 3066346118, 3283795978, 1197222174, 2936543382, 3503535134, 2892598771, 2621962168, 931511531, 2231087188, 4146539078, 4002087507, 2491835423, 4060649251, 4048333160, 2444738719, 2691519303, 1556526141, 3615497232, 4050826531, 500299044, 717467546, 2206683369, 861398548, 3151369905, 4029791836, 3416545629, 4120104600, 1465267912, 483234533, 3035820989, 3832933168, 3568690105, 96174302, 2545526712, 1102861924, 1074783639, 4182941480, 1533353222, 1488829617, 1503690984, 185887778, 4211993208, 2290188486, 1146083769, 2041769341, 2684027677, 3176900642, 1387338494, 946259368, 1066487432, 795876682, 3861793354, 1668825820, 216618949, 2896083408, 3851619025, 442276681, 206355214, 270139248, 347366931, 1910792165, 3953458832, 2734158556, 2811136264, 1920172269, 1837836373, 3778467275, 3779230355, 3897121172, 2344011383, 1146522764, 2190434845, 609244986, 2013714652, 560173192, 2402932255, 1072869170, 1770725561, 952360909, 1412825165, 3696544236, 2306376326, 2830983153, 207976619, 4155556879, 3728896627, 2654370117, 3334033001, 1365410137, 1493856098, 1253593280, 1631830970, 5803336, 3918597809, 86127041, 333464839, 3604499396, 149662371, 2129288705, 1461710188, 3760680120, 3729872359, 2100765881, 3535556758, 444301423, 2716178967, 1126522126, 4087265377, 129975151, 3676574817, 946781552, 1144144314, 4160587561, 3992786314, 45372372, 2839307265, 3121990915, 2417091275, 2394722122, 2336989436, 3126674182, 3231554964, 3785353831, 3066121066, 4059908701, 3257600631, 3304564137, 976977941, 2994176851, 3509885563, 436168092, 2194926470, 572263581, 2964578564, 2577729800, 4257414592, 1074783671, 2629434251, 42822614, 1475322010, 3068645543, 3694724738, 3480058324, 4204711804, 3168448984, 2767935672, 3016152818, 4134435775, 2141315517, 2182008981, 2871864678, 2294299758, 1409773258, 3418660825, 3090287076, 3241139267, 2315623533, 2157788904, 334169841, 2062298350, 4075844652, 1672438569, 2994084656, 2204498767, 2430183901, 4179388667, 317027997, 2894184457, 3635887387, 1307832846, 3358657065, 734371454, 610520453, 3421706671, 3240587498, 3690351924, 935152653, 2737123774, 203357945, 1027962332, 3777141639, 743025036, 4046422672, 1085389282, 110265143, 320421926, 1931570193, 936595461, 2927488848, 2265674314, 3444945553, 786566925, 4133145648, 2879270131, 4165751769, 3985446237, 1971125873, 3724681025, 2661325531, 2441664181, 3290805620, 2459158763, 2102811157, 2881160687, 1153639082, 827213914, 3028527431, 2205345684, 3556675715, 1279123065, 4253124398, 3483559979, 4068430995, 4141206587, 2571521727, 2944439402, 443124686, 2268164570, 2235451426, 3679071975, 3129207272, 2516367556, 1468462786, 1881517367, 3491042253, 2913831047, 3164481275, 202602034, 3150723817, 1533130707, 1912730441, 2090267514, 3558123575, 1133228007, 3421482977, 2553693497, 3421969717, 2520271965, 2067324870, 1223636150, 2714495378, 3773685424, 2961634881, 88882886, 408668635, 904339271, 3187997208, 2883270961, 1911371885, 1111177434, 3677904221, 1424566197, 456428662, 3160502725, 2571618126, 1931038165, 1229862345, 885692642, 928907436, 281108918, 2025639202, 4098934983, 245166619, 3978368942, 2335134348, 2663736265, 3483476476, 1019177183, 1076843627, 2150626843, 3549898506, 497411044, 2948681730, 1293862520, 3364439483, 200913955, 876046583, 2810673955, 2828391839, 1905062360, 3783182365, 2472665728, 1439731349, 2736703148, 3316496080, 2996051367, 448455111, 3808598160, 2313472828, 1619655346, 1198200314, 3744504057, 1680713197, 2474661491, 3214410863, 1662774943, 3537885099, 3365412658, 3583677483]

prng.setstate((3, tuple(state + [0]), None))
D = [prng.getrandbits(32) for _ in range(624)]
print(D)
"""
[3086615663, 3771906507, 1933791567, 874400704, 4000928288, 1101512046, 3757205682, 895930285, 2975657910, 1590250704, 227397937, 3163700038, 1702493296, 86408336, 1317214060, 355017934, 4281601498, 2958424486, 3248821687, 1977038961, 75767861, 1848107476, 1201089736, 1669521311, 3079560731, 753259725, 2783047520, 1792692953, 1335325755, 4118154638, 221587457, 3931660158, 2105971738, 205787269, 3306213190, 3047766446, 757659831, 70863674, 2054184739, 418281550, 2654142751, 3195128907, 3920550815, 273337573, 856860348, 2332777112, 1144893468, 4097373151, 2348453877, 3391728911, 1909111864, 1167657184, 1690201897, 3037596190, 2683689827, 2591985588, 483396539, 583852871, 4213595783, 3297463098, 3940471284, 3167491933, 3836764654, 385184073, 4089593895, 2435556034, 2689611721, 3009515703, 2557788155, 742759035, 2911234764, 2747466359, 1658388676, 77325257, 1282826102, 833518584, 258773596, 1252680510, 2161330425, 1505524757, 1106189058, 2479195181, 4059279758, 4087261637, 2802856115, 215936888, 385734300, 3976823712, 2155716808, 166878602, 2958581226, 2153643018, 3459229793, 166654981, 1135752470, 2999716815, 102870168, 3592405002, 143561712, 3332529987, 3320611547, 176304087, 3809410875, 956905158, 3283895217, 1267764884, 1781613649, 2648889013, 4023857409, 2805378741, 2649655508, 2608225929, 2196639843, 2844902511, 1947381383, 133311662, 3189375534, 3360781939, 2598704112, 449730728, 1660136746, 2120362421, 4282918442, 553031705, 2359175283, 1820194402, 3326941501, 2079373053, 3848840564, 674418166, 2099289575, 3503720323, 71654499, 1153326313, 560391397, 987219237, 3519108661, 343772283, 2206155982, 1710469128, 4284016382, 1099544658, 2385903806, 435889661, 1754514095, 1654595795, 2611465271, 2924309399, 3849122741, 2771388572, 132443906, 639488960, 1702455392, 1197499823, 3431742381, 1162507747, 1956793904, 2882150352, 1024607141, 573195509, 4026654414, 2622992078, 3350586931, 3799382718, 189653578, 2030853706, 2360599919, 1447670146, 3029293260, 449492231, 794537698, 2013929440, 2521582617, 3662902133, 2988382934, 1101429406, 2204422539, 2884223003, 4160719615, 378925199, 321253023, 713869660, 1722066591, 4190495614, 3241838993, 3156104799, 3976107465, 690141471, 2565083608, 629627271, 3367902606, 3025623735, 1771459709, 2325207656, 29331249, 1631496960, 1272596234, 677116176, 36223230, 1894006200, 1868323656, 147662067, 3018282350, 847618418, 473803624, 303813116, 1222076488, 2857631548, 1620440323, 3028453586, 3771115277, 974948581, 2805463577, 3012869721, 1677541868, 873746956, 3206333732, 3540196648, 4222297189, 3955666095, 3723668809, 3383181896, 1572023031, 3593767211, 4139994756, 2493637240, 1055398974, 3491895839, 2158774748, 4074778554, 2265454243, 3123246270, 3737495019, 3584208536, 505004504, 711346815, 2265659930, 44813444, 762261590, 2345302575, 3635851795, 2255282129, 3598634106, 921749760, 1418440684, 3784150188, 2393915660, 2720478000, 1612782044, 4147046015, 2561634247, 586916363, 1606384598, 1299844033, 4047608483, 3431257347, 781242816, 3127114595, 1484369015, 483654543, 678493767, 2757899632, 3276695749, 1363370762, 1578035875, 555054787, 3093962781, 2222987767, 2130200534, 2053306276, 3948690640, 3249023873, 2343777324, 2833997966, 44199340, 1950451402, 1448991312, 1055067146, 3980624341, 1812874122, 2512418377, 3541037815, 714180005, 987816438, 3414079245, 1619142872, 4122595525, 3638144912, 3337941608, 2664929972, 1577036940, 206102296, 2850863132, 3729200403, 644729416, 844182047, 2261919397, 1040614315, 1776485562, 677708826, 223842114, 2591956969, 3141458682, 4271489476, 4253854271, 3973860423, 2805984925, 2908508806, 2328769351, 3865140, 4170270812, 1373888554, 1702101960, 3761095439, 3848481069, 812779025, 2073985983, 239315333, 1585392927, 2233774162, 2308108952, 3393306946, 2891660426, 1059096016, 2448311649, 2662483261, 422228248, 2356192519, 4004741305, 432651290, 2419877069, 3136967672, 329338548, 510605497, 2753410852, 2256462380, 3602678268, 2558451886, 324326056, 3822050324, 944965241, 4107093336, 1023337388, 564298141, 2977064774, 1802025909, 2329346614, 1460784428, 2510641562, 593994802, 4034614216, 4154528137, 3061249939, 487067285, 2856327155, 1909407614, 1782934804, 947220403, 2311402749, 3528590202, 2841893555, 3179384475, 3485733076, 87074890, 753396673, 790057962, 378850528, 3789224576, 3983502105, 1166116, 1854075229, 965611444, 3399039227, 3301304385, 3499808775, 1553588463, 2562124078, 3702675704, 1456114141, 768418804, 2227423616, 3711148950, 2738970313, 4033988307, 1184409529, 3461105405, 2986057969, 2112332635, 615658869, 2858394250, 2819269426, 499315937, 1714425168, 3816439521, 4188657733, 1226314395, 773286132, 1257824142, 2439511774, 1412431345, 451028253, 102711904, 3272107935, 1915128127, 674941443, 1907183006, 4205826365, 2592631544, 2001660887, 1793337902, 336832953, 1676534641, 439197643, 2175306211, 1969440247, 4084563735, 564896680, 1293717918, 1136684128, 4289259757, 2368216261, 3167549822, 1998645278, 2908859410, 2014400533, 1482521794, 3082876093, 2742987778, 3273667028, 1654313273, 3551772744, 1923315597, 1063687791, 1907747434, 3323400678, 3445870975, 316314436, 3905619499, 853586576, 456263058, 3213830894, 3603099146, 1478599807, 344267130, 1085971878, 2416474796, 247701271, 2926294528, 1981779524, 3809025846, 2106937971, 1596271124, 1289668306, 1824884242, 543613169, 2698011204, 1632632104, 179981234, 1091171130, 608067622, 4034608897, 2707671187, 2261524231, 2177175178, 1649366013, 733151281, 2783115482, 389580085, 495962438, 512715565, 1917819840, 1993385884, 2910358830, 3223741704, 3302008571, 857474180, 143995596, 3194737469, 2792999636, 111369357, 2665449999, 3481184513, 21965724, 172308864, 3373225896, 3941204120, 1487487599, 2697473345, 4173199839, 1988623177, 3567610975, 2393053467, 2231132558, 3798877543, 4275987399, 3626515970, 3957758644, 3196139612, 1577858639, 4145376193, 3982712357, 1316354617, 2476570111, 2796635786, 3673095113, 317782376, 38302891, 2729549772, 3124741082, 779634809, 480059945, 1764557943, 1905762442, 2439926326, 3398546304, 1275206055, 3578388510, 4286589961, 2284154687, 1547652572, 211218778, 4019993609, 1035325551, 47385212, 1413260320, 1895132671, 2144191841, 976730195, 880818479, 2944522030, 3051883625, 941172532, 1956827360, 604038865, 1490554868, 2014326554, 3585424155, 1705580179, 1484996770, 3145161387, 2410763156, 1196196268, 4125882510, 1569631240, 3635487118, 3743075539, 53348120, 3549050110, 2179975673, 1455493727, 909517499, 2034744814, 1815931219, 2625466993, 2328144852, 3083176966, 4185591290, 4232725936, 233807337, 987553443, 25498384, 1577858645, 3349985471, 222166290, 1566719496, 4025597331, 454410574, 4172717618, 3397690720, 1563985388, 1294197484, 454917824, 250364909, 1076318659, 3751354075, 3324840413, 2834288682, 1309780963, 3789459740, 1605544538, 1448439145, 1158482892, 407656226, 3589982226, 2670402128, 2795218845, 4079499284, 2736737218, 468906864, 347349067, 3541605667, 1532233501, 1192558327, 3650037602, 1570092544, 3596826230, 2768927258, 1775543901, 1324819997, 3401066173, 4078892370, 3373389918, 3360817112, 3261261117, 2443241006, 847292772, 3862028592, 4086319712, 1837673494, 3577160747, 2636413549, 4021668342, 573747407, 3546255858, 2787607684, 403421850, 3477281082, 4133820736, 332805644, 3663845239, 80993494, 344033777, 1187319040, 1547969768]
"""

def attack2(list1):
    predictor = ExtendMT19937Predictor()
    for i in range(624):
        predictor.setrandbits(list1[i], 32)
    for i in range(624):
        predictor.backtrack_getrandbits(32)
    x = predictor.backtrack_getrandbits(128)
    return x

key = attack2(D)

key = bytes(list(reversed(list(long_to_bytes(key)))))
# key = key.to_bytes(16, 'little')

c =  b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'

cipher = AES.new(key,AES.MODE_ECB)
print(cipher.decrypt(c))

# WKCTF{3f2af637b773613c18d27694f20d98fd}

官方解

利用 https://github.com/JuliaPoo/MT19937-Symbolic-Execution-and-Solver

这个项目上的脚本

1
Only [4, 8, 12, 16, 20, 24, 28, 32] are supported

有个限制，就是只能解 如上八种大小的随机数

详细使用方法见 Demo of Features.ipynb 

1
rng_clone = MT19937(state_from_data=(rand, 4))

无论随机数是4bit 还是 8bit，抑或其他几种，只需修改这个

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
sys.path.append('D:\Desktop\CTF\CTF工具\Sagemath\MT19937-Symbolic-Execution-and-Solver-master\source')
from MT19937 import MT19937

c = b'\x90\xddz\xbf@\xa2$a\xacGB\xe5\x1b\x1c\xa6\xc7'
f = open('random.txt','r')
rand = f.read().split('\n')[:-1]
rand = [int(i) for i in rand]

# Clone rng's current state
rng_clone = MT19937(state_from_data=(rand, 4))  # Only [4, 8, 12, 16, 20, 24, 28, 32] are supported

# Reverse state by 4
rng_clone.reverse_states(4)
reverse_states = [rng_clone() for i in range(4)]
# 先生成的32比特放在低位
k = reverse_states[0] + reverse_states[1]*2**32 + reverse_states[2]*2**64 + reverse_states[3]*2**96
key = k.to_bytes(16, 'little')
cipher = AES.new(key,AES.MODE_ECB)
print(unpad(cipher.decrypt(c),16).decode())

# WKCTF{3f2af637b773613c18d27694f20d98fd}
1
2
3
4
5
to_bytes(length, byteorder):
length：结果字节对象的长度（字节数）。这里是 16，意味着结果将是一个 16 字节长的字节对象。
byteorder：字节序，可以是 ‘big’ 或 ‘little’。
‘big’：大端序（big -endian），高位字节在前。
‘little’：小端序（little -endian），低位字节在前。

赣育杯2024-Random-dlp

2024-10-27

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
from random import *
from Crypto.Util.number import *
from gmpy2 import *

m = getrandbits(128)
flag = b'Sangfor{'+str(m).encode()+b'}'
big_bits = 992

x = getrandbits(32)
g = getrandbits(128)


def prime_number(big_bits):
    number = getrandbits(big_bits)
    number = number << 32
    return next_prime(number)


def encrypt(g, x, p):
    c = pow(g, x, p)
    return c


p = getPrime(1024)
c = encrypt(g, x, p)
random_list1 = []

for i in range(10):
    random_num1 = prime_number(big_bits)
    random_num2 = prime_number(big_bits)
    if i == 0:
        Composite_number = random_num1 * random_num2
        xor_prime = random_num1 ^ random_num2
        random_list1.append(int(Composite_number))
        random_list1.append(int(xor_prime))
    else:
        random_list1.append(int(random_num1))
        random_list1.append(int(random_num2))


with open("output.txt", "w") as file:
    file.write(str(p)+'\n')
    file.write(str(g)+'\n')
    file.write(str(c)+'\n')
    file.write(str(random_list1)+'\n')
    file.close()
1
2
Composite_number = random_num1 * random_num2
xor_prime = random_num1 ^ random_num2

给定p与q的异或求n的分解，剪枝

1
2
number = number << 32
return next_prime(number)

因为 << 32所以我们需要 >> 32，next_prime 就毫无影响

1
g = getrandbits(128)

再加上g，数据足够用于回溯了，

exp：

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from Crypto.Util.number import *
import sys
from extend_mt19937_predictor import ExtendMT19937Predictor

sys.setrecursionlimit(1500)

# part1,剪枝
a1= 99955815136124674505677363553135840917216692678315165208714645876521277179009541555218693763972124093311337930953461092973753294192953068017272222852126250530936095477001144686822657131226982048667251579944854755923118519999180605689190568796547900773861811522756528982895318342111571405051796393985533019048
b1= 5065809221397249795914513089532241535418102663843841350285885091820845924268184747393712704066864872817411880187138570682343431633457955483256879427452674941369291914713556216448497708811437937958937996112215942003348660775545739352648178349311820872326958487644664192024604484132973905940652831298817064882948766270012275390175132095666103160877771192023394295841216195145461506875974150379337178597242564194005887140459925415651634648423371399820338191237184941903484527013807399340034262032276649742513332545447037957047893203075544536859894680877963124739172891482242764504898102716242397187522857902572172473057

a1 = str(bin(a1)[2:])

def find(p, q):
    l = len(p)
    tmp0 = p + (1024 - l) * "0"
    tmp1 = p + (1024 - l) * "1"
    tmq0 = q + (1024 - l) * "0"
    tmq1 = q + (1024 - l) * "1"
    if (int(tmp0, 2) < int(tmq0, 2)):
        return
    if (int(tmp0, 2) * int(tmq0, 2) > b1):
        return
    elif (int(tmp1, 2) * int(tmq1, 2) < b1):
        return

    if (l == 1024):
        pp = int(tmp0, 2)
        qq = int(tmq0, 2)
        print('num1=',pp)
        print('num1=',qq)
    else:
        if (a1[l] == "1"):
            find(p + "1", q + "0")
            find(p + "0", q + "1")
        else:
            find(p + "0", q + "0")
            find(p + "1", q + "1")

tempp = ""
tempq = ""
find(tempp, tempq)

num1= 127954378905954473979599580543506133734470934402921187567126328044915399136783613004594347893231249786782113863929878799565038392492182148282608301947643527866047185811106214065159313666530775740342170598378474744062316856449855121227117986037506212272472581097517909639356259473022026193056598279705883312493
num2= 39590745269613494512251071983478757508814280272882049594849029032543594900913069786771939178626302619505593605829896534613681707527396968070583148545044036306348014204000427687094161885558852315374684881011665955520787218713536145424007912730740353898075406161865607017294126568950247058934097741037059441349

with open('output.txt','rb') as f:
    f = f.read()
    p = eval(f.decode().split('\r\n')[0])
    g = eval(f.decode().split('\r\n')[1])
    c = eval(f.decode().split('\r\n')[2])
    random_list1 = eval(f.decode().split('\r\n')[-2])
    random_list1[0] = num1
    random_list1[1] = num2
    for i in range(len(random_list1)):
        random_list1[i] = random_list1[i]>>32

def attack2(list1):
    predictor = ExtendMT19937Predictor()
    predictor.setrandbits(g, 128)		# 这个位置注意一下
    for i in range(20):
        predictor.setrandbits(list1[i], 992)

    for i in range(20):
        predictor.backtrack_getrandbits(992)
    predictor.backtrack_getrandbits(128)
    predictor.backtrack_getrandbits(32)
    x = predictor.backtrack_getrandbits(128)
    return x

x = attack2(random_list1)
flag = b'Sangfor{'+str(x).encode()+b'}'
print(flag)

# Sangfor{332419641733214815865048217860135168997}

Reference：

浅析MT19937伪随机数生成算法 - badmonkey

[CTF/randcrack]python随机数预测模块分析及改进方案_random.getrandbits(32)-CSDN博客

ExtendMT19937Predictor

[WKCTF 2024] Crypto (random)_wkctf2024-CSDN博客

-------------　　　　本文结束　　感谢阅读　　　　-------------