2022DASCTF MAY 出题人挑战赛

Yusa的密码学课堂——一见如故

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
class Myrand():
	def __init__(self,seed):
		self.index = 0
		self.isInit = 1
		self.MT = [seed] + [0] * 623

		for i in range(1,624):
			t = 1314433253 * (self.MT[i-1] ^ (self.MT[i-1] >> 30)) + 1
			self.MT[i] = t & 0xffffffff#32bit


	def generate(self):
		for i in range(624):
			y = (self.MT[i] & 0x80000000) + (self.MT[(i+1)%624] & 0x7fffffff)
			self.MT[i] = self.MT[(i+397)%624] ^ (y >> 1)
			if y & 1:
				self.MT[i] ^= 2567483520

	def rand(self):
		if self.index == 0:
			self.generate()
		y = self.MT[self.index]
		y = y ^ self.cs2l(y, 11) ^ self.cs2l(y,15)
		y = y ^ self.cs2r(y,7) ^ self.cs2r(y,19)
		self.index = (self.index + 1) % 624
		return y

	def cs2l(self, y, shift):
		return ((y << shift) ^ (y >> (32 - shift))) & 0xffffffff

	def cs2r(self, y, shift):
		return ((y >> shift) ^ (y << (32 - shift))) & 0xffffffff

import os
r = Myrand(int(os.urandom(4).hex(),16))
out = []

for i in range(624):
	out.append(r.rand())

with open("output.txt","w") as f:
	f.write(str(out))

from hashlib import md5
flag = 'DASCTF{' + md5(str(r.rand()).encode()).hexdigest() + '}'
print(flag)

（小声逼逼：之前遇到了类似的题，但是文章因个人原因丢失了）

不难发现，关键之处在于如何破解 cs2l 和 cs2r ，破解了就可以求出 MT 序列，然后按题目中 flag 部分的操作就可以得出 flag 。

观察 cs2l 和 cs2r ，发现其功能是循环移位。而且特征如下：
$$
y = x ⊕ (x⋘p) ⊕(x⋘q)\tag 1
$$
网上觅得一篇文章：循环移位异或加密 - Tf1shC4T - 博客园 (cnblogs.com)

在长度为 $2^n$ 的二进制串中，循环移位异或变换中，如果有奇数项，那么这个变换是可逆的，否则就是不可逆的。

分析上式，两边同时 $⋘p$ 和 $⋘q$ ，得
$$
y⋘p = (x⋘p)⊕(x⋘2p)⊕(x⋘(p+q))\tag 2
$$

$$
y⋘q = (x⋘q)⊕(x⋘(p+q))⊕(x⋘2q)\tag 3
$$

$(1)*(2)*(3)$ 得
$$
y_1 = y⊕(y⋘p) ⊕(y⋘q) = x⊕(x⋘2p) ⊕(x⋘2q)
$$
同理
$$
y_2 = y_1⊕(y_1⋘2p) ⊕(y_1⋘2q) = x⊕(x⋘4p) ⊕(x⋘4q)
$$
$$
y_n = y_{n-1}⊕(y_{n-1}⋘2^{n-1}p) ⊕(y2⋘2^{n-1}q) = x⊕(x⋘2^np) ⊕(x⋘2^nq) = x\quad (bitlen = 2^n)
$$

如此就可以求出原来得 x 。

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
from hashlib import md5

bitlen = 32
def mov(y,k):#循环左移
    biny = bin(y)[2:].zfill(bitlen)
    k = k % bitlen
    biny = biny[k:] + biny[:k]
    return int(biny,2)

def decrypt(y,ks):
    for i in range(bitlen):
        y = y ^ mov(y,ks[0]) ^ mov(y,ks[1])
        ks = [ k<<1 for k in ks]
    return y

class Myrand():
    def __init__(self,MT):
        self.index = 0
        self.isInit = 1
        self.MT = MT

    def generate(self):
        for i in range(624):
            y = (self.MT[i] & 0x80000000) + (self.MT[(i+1)%624] & 0x7fffffff)
            self.MT[i] = self.MT[(i+397)%624] ^ (y >> 1)
            if y & 1:
                self.MT[i] ^= 2567483520

    def rand(self):
        if self.index == 0:
            self.generate()
        y = self.MT[self.index]
        y = y ^ self.cs2l(y, 11) ^ self.cs2l(y,15)
        y = y ^ self.cs2r(y,7) ^ self.cs2r(y,19)
        self.index = (self.index + 1) % 624
        return y

    def cs2l(self, y, shift):
        return ((y << shift) ^ (y >> (32 - shift))) & 0xffffffff#循环移位

    def cs2r(self, y, shift):
        return ((y >> shift) ^ (y << (32 - shift))) & 0xffffffff#循环移位

out = [3417500333, 4091726338, 652603332, 4187304543, 4293795290, 1622245003, 3383443782, 2420250331, 322010852, 1604005753, 3137930218, 1074571824, 1566336258, 2754341076, 1059426660, 2461569360, 613134153, 860561774, 3003069274, 553387944, 1949778231, 249886857, 2322866121, 3685855175, 1977923546, 1887238269, 253812990, 2188417674, 2718707711, 1599975569, 3254935456, 3199641169, 362166522, 1378687155, 912036995, 3174049018, 780042016, 970421905, 3468971406, 801660807, 833926127, 473587885, 158979812, 405306558, 1363084996, 2023076543, 2069797730, 718155249, 1641186127, 3616747747, 1575693921, 3856591855, 223881884, 3002184567, 1666647440, 617661934, 2673101022, 885332395, 3391329168, 1640225363, 2565685644, 3892963352, 3034627488, 2415435183, 3648712566, 2140877952, 1303506086, 2455662362, 1720382700, 3970268445, 2579167586, 4117229324, 846645263, 3252991293, 79067029, 2756800392, 2212447526, 2203329967, 1270408703, 740176928, 3176125705, 166800854, 3327343902, 2079714725, 3702269956, 3659849279, 3658666909, 797535816, 600857570, 553836307, 2394740468, 1178393549, 2183765310, 4014432190, 652246726, 3693235932, 4046942361, 4105444828, 145386213, 1198390220, 3023119098, 663559283, 225958361, 3893000878, 1615631644, 1941951859, 471085675, 2164362049, 4274234562, 4127314557, 1833529303, 17668093, 3208743142, 3210135945, 1772990736, 3290157875, 3006334453, 3831748800, 1120411838, 690279329, 2436940844, 1440602808, 1552272917, 1321728089, 524486126, 3696307959, 1189129368, 28736041, 3143264315, 3050323849, 1458456612, 389869312, 2360130428, 854837117, 1270423403, 3471650414, 243573262, 3449929772, 2436299611, 420972940, 923873821, 3499748829, 2470333529, 3901870125, 3589884387, 3339475693, 1526947412, 1747516667, 2971536797, 273910310, 2185887289, 2723697010, 1973585459, 1166325256, 1360822059, 416514510, 4038763765, 1816380840, 940152644, 3918708431, 3410593321, 3358844522, 3678637784, 2412834780, 3052967117, 3672611162, 570069042, 95771608, 1210821251, 2163778365, 2739972546, 3094346015, 749719666, 1697477587, 986142486, 2591897292, 1234948693, 3659791160, 3990257960, 501199958, 3029961497, 578415668, 124517322, 1985205894, 3777347400, 1149995545, 290699775, 3399696193, 1062094395, 2896523484, 1562688856, 992098141, 3941170280, 262596967, 2585751001, 3682611205, 530523926, 1202322766, 3777439514, 3051700271, 261632458, 2736123960, 2786338595, 86310784, 2760191516, 1344514731, 350767781, 2858876127, 519088864, 3193340756, 3563489312, 3239917298, 161418824, 470724403, 3310407387, 1743713887, 3064036770, 1175434157, 3029464330, 116086349, 1652489862, 1176236897, 4139800383, 3758499033, 2961626313, 3064683859, 958478146, 596650527, 1000277312, 4102368994, 1480011430, 4001401502, 4004287177, 3202905309, 1754655955, 2064262245, 1840530874, 2284428117, 2281854453, 1023839768, 2166517711, 2709857675, 2005014414, 4161461001, 2932436148, 2411599350, 4267437788, 2132764972, 150665266, 286170947, 2249288787, 3953585886, 1231725143, 2479045931, 2377059462, 281316188, 379113422, 920019004, 163289886, 2210874762, 1578529538, 309521495, 3737017316, 88919917, 559742618, 978230553, 2154491496, 994913727, 498894258, 1355546448, 4023836881, 3014313787, 164044564, 2408825840, 2029992558, 3707778216, 86206872, 3576935874, 185356787, 1774175910, 3145237900, 3497547609, 841914878, 3425254534, 4264030778, 2348022032, 178331591, 943923822, 3384367749, 2806712599, 1178535099, 1251085540, 2410015803, 1480595408, 2732607876, 1579706357, 870791724, 2320512780, 2149666862, 3797999384, 3905363134, 3388169321, 851973359, 1418716205, 207581030, 1740441523, 1173839013, 4280610104, 1769134281, 1758916333, 4061069248, 2147554262, 2749007447, 909878569, 2054562584, 1515003000, 560286390, 2482663802, 2690882951, 3298162668, 2561737261, 167825221, 507375343, 2179952491, 795452860, 2877704207, 3243106071, 1633372043, 2152178033, 2993246714, 4176238981, 3828458887, 695369535, 2514762808, 2251430819, 2743651063, 783239046, 4036497041, 2175424426, 765021321, 897227922, 3192938155, 4173350810, 2290496185, 4215986056, 2448481441, 3114984799, 2920066349, 722868808, 594363801, 4012575088, 454547939, 3331771662, 1267229957, 3170277692, 2446344734, 3730529788, 2621611481, 2972284304, 2580290241, 486727007, 2727955445, 1457071884, 1053028185, 462301682, 3907840756, 1832398102, 3144685297, 3403964915, 4263570498, 792776003, 306771255, 1633688240, 2159479271, 942060576, 1311531808, 3145754189, 4142271069, 2844524541, 4082439147, 2847276716, 1374436698, 2601522390, 529644524, 206090172, 3015114937, 4137169373, 2600331537, 344659140, 155319271, 1724932164, 3187877676, 4020168431, 711431575, 4123955169, 2539963709, 2764832709, 3897838285, 2521203644, 2059212822, 1129046005, 3277260664, 2739869189, 1955591901, 2661672178, 2926355273, 28176978, 706409211, 1432061304, 26517996, 3180196905, 2178525849, 607854674, 3953350517, 3532394548, 4175940932, 626671309, 1273934270, 3481828801, 22643989, 2104739013, 4183577772, 3932721637, 3075788222, 2814353001, 4120869721, 2045506903, 603494333, 335162960, 2069261279, 2278614835, 210140447, 2012566692, 2345710126, 70390387, 457247932, 2764651800, 652766919, 555253440, 864036913, 1720142260, 453262569, 1113437101, 2576419688, 144008475, 1786881829, 2455128823, 2884922345, 4251332234, 58949785, 4206002785, 3374754553, 2976162198, 546450687, 1268444784, 4132330381, 3404894280, 2421962142, 212361299, 2526283704, 1656118437, 1249336298, 305885855, 1090758249, 3752057640, 3508190692, 3637428, 105102422, 2247418237, 1873609555, 1206760240, 3761689119, 3151616638, 1711308858, 1261541178, 1843103377, 3158893523, 1226253110, 3337577909, 126612372, 2239219657, 1415387229, 3657507305, 3330696118, 2304219467, 3782535397, 2523926865, 173770442, 469421316, 4068724979, 567442650, 1996215573, 2071307093, 778899724, 3534102235, 1001138889, 2821812427, 591691317, 1265763678, 2241915660, 3220601768, 653090205, 2367897867, 1393909319, 2691817329, 3098049768, 117121403, 1255294678, 2272844919, 788255921, 2333869622, 4052660679, 2407095869, 2636108242, 2204717619, 1672726444, 2250826426, 258706466, 2295454699, 337308034, 3703973770, 3133498524, 22718827, 3096937679, 2039003308, 1519854757, 568184976, 1986854118, 2888207511, 822307630, 3829301724, 3198527490, 3073739663, 3043580445, 3458239370, 802145890, 376901460, 1251103099, 1143003993, 1280321148, 661386076, 3708710489, 2237151715, 3928104641, 2975550516, 1087492088, 1504028830, 61927086, 3858242888, 1916136658, 2328550074, 3032032377, 2193802260, 3311627503, 3196945045, 3396801792, 806210594, 2449941623, 2514744466, 3922130206, 3245757763, 3128328446, 2335833206, 3205660364, 3527402441, 2174241644, 1262568556, 2360103007, 2490217737, 1485100950, 3407260, 3005226942, 1355314866, 3154763465, 619881867, 2409963438, 2422269402, 205756019, 3300644241, 1157501775, 1229058028, 161050869, 969496287, 3385825249, 2557284067, 4236642714, 169094727, 2698326774, 1863176242, 3532885426, 3046403588, 3869207867, 496104150, 353604631, 1054882225, 152711981, 1362131890, 76912113, 3052177189, 3932252092, 3834713905, 2338378436, 44417325, 117723195, 1089433566, 4166617161, 2848021308, 2229619096, 319957702, 3661655667, 2809620731, 482011930, 3983483016, 82362287, 1518135562, 3490996143, 510129461, 1400609584, 2646113779, 732457215, 3735585198, 3451194227, 959269510, 244188667]
ks_l = [11, 15]
ks_r = [bitlen - 7, bitlen - 19]#右移转换成左移
MT = []
for each in out:
    MT.append(decrypt(decrypt(each,ks_r),ks_l))

r = Myrand(MT)
flag = 'DASCTF{' + md5(str(r.rand()).encode()).hexdigest() + '}'
print(flag)
#DASCTF{49e225e5b1b57a1d3c9803b5ddfd38f9}

Yusa的密码学课堂——二眼深情

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
代码同上，额外有：
import os
secret = int(os.urandom(4).hex(),16)
r = Myrand(secret)
out = []
for i in range(624):
	out.append(r.rand())

try:
	for i in range(2):
		a = int(input("Your "+['first','second'][i]+ " see: "))
		print(out[a % len(out)])
		guess = int(input("You konw my secret? "))
		if guess == secret:
			print("For you ~")
			print(os.getenv("DASFLAG"))
			exit()
		else:
			print(["Try again~ ","Bye~"][i])
except Exception as e:
	exit()

  1. 也就是说要选取两个合适的 $out$ 来反推出 $seed$ 。因此，选取 $out[395]$ 和 $out[622]$ 。通过第一题的方法反推出generate()之后的 $MT[395]$ 和 $MT[622]$ 。

  2. 根据generate函数，猜测 $bin(y)$ 的最低位(也就是 $bin(MT[623])$ )，这样就可以推出 $bin(MT)[2:][1:]$ ，再次猜测它的最高位，这样就有四种情况。

  3. 根据__init__()中的

    1
    2
    3
    for i in range(1,624):
    	t = 2037740385 * (self.MT[i-1] ^ (self.MT[i-1] >> 30)) + 1
    	self.MT[i] = t & 0xffffffff

    可以推出最初始的 $MT$ 。 t & 0xffffffff 相当于 t%$2^{32}$。这样， 求出 $MT[i-1]$只需要 (t-1)*inv(2037740385,$2^{32}$) ，在运行一遍上面这个异或操作就可以了。

  4. 四种情况，就需要筛选。用上面得出的 $MT$ 运行一遍generate()，看是否匹配步骤(1)中的 $MT[395]$ 和 $MT[622]$ 。

（奇怪了！有时候运行能得出结果，有时候不能！是不是代码有问题？我检查了好久但没发现，希望师傅们能斧正一下！）

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
from pwn import *
import gmpy2

s = remote('node4.buuoj.cn',25122)
#第一轮
print(s.recv())
s.sendline(b'395')
out395 = int(s.recvline()[:-1])
print(out395)
print(s.recv())
s.sendline(b'1')
print(s.recvline())
#第二轮
print(s.recv())
s.sendline(b'622')
out622 = int(s.recvline()[:-1])
print(out622)
print(s.recv())

#generate()之后的MT
bitlen = 32
def mov(y,k):#循环左移
    biny = bin(y)[2:].zfill(bitlen)
    k = k % bitlen
    biny = biny[k:] + biny[:k]
    return int(biny,2)

def decrypt(y,ks):
    for i in range(bitlen):
        y = y ^ mov(y,ks[0]) ^ mov(y,ks[1])
        ks = [ k<<1 for k in ks]
    return y

ks_l = [11, 15]
ks_r = [bitlen - 7, bitlen - 19]#右移转换成左移
out395 = decrypt(decrypt(out395,ks_r),ks_l)
out622 = decrypt(decrypt(out622,ks_r),ks_l)
print(f'out395 = {out395}')
print(f'out622 = {out622}')

#恢复所有初始MT
def recover(seed):
    seed &= 0xffffffff
    inv = int(gmpy2.invert(2037740385,0xffffffff+1))#
    re_MT = [seed] + [0]*623
    for i in range(1,624):
        mt = ((re_MT[i-1] - 1)*inv) & 0xffffffff
        '''
        mt = bin(mt)[2:].zfill(32)
        tmp1 = mt[:30]
        tmp2 = int(tmp1[:2],2) ^ int(mt[30:],2)
        tmp = (int(tmp1,2) << 2) + tmp2
        '''
        tmp = mt ^ (mt >> 30)
        re_MT[i] = tmp

    return re_MT[::-1]

#检验
def check(MT):
    for i in range(624):
        y = (MT[i] & 0x80000000) + (MT[(i + 1) % 624] & 0x7fffffff)
        MT[i] = MT[(i + 397) % 624] ^ (y >> 1)
        if y & 1:
            MT[i] ^= 25674835200
    #print(f'checkMT = {MT}')
    #print(f'MT[395] = {MT[395]},MT[622] = {MT[622]}')
    if MT[395] == out395 and MT[622] == out622:
        return True
    else:
        return False


#恢复MT[623]
def dec_generate(a,b):#a为out622,b为out395
    maybe = []
    #MT[623]最后一bit为1
    tmp1 = a ^ 25674835200
    y = tmp1 ^ b
    y = (y << 1) + 1
    #猜高位0,1
    mt1 = 0x80000000 + (y & 0x7fffffff)
    maybe.append(mt1)
    mt2 = y & 0x7fffffff
    maybe.append(mt2)
    # MT[623]最后一bit为0
    y = a ^ b
    y = (y << 1) + 0
    mt3 = 0x80000000 + (y & 0x7fffffff)
    maybe.append(mt3)
    mt4 = y & 0x7fffffff
    maybe.append(mt4)
    print(f'maybe = {maybe}')
    for each in maybe:
        MT = recover(each)
        print(f'MT = {MT}')
        if MT != -1:
            isflag = check(MT.copy())
            #print('3',MT)
            if isflag:
                return MT[0]
    return -1


seed = dec_generate(out622,out395)
print(f'seed = {seed}')
s.sendline(str(seed).encode())
print(s.recv())
#b'DASCTF{a448b996-140b-4b06-9bf0-b69c6cde067d}'

参考：

DASCTF｜2022DASCTF May出题人挑战赛官方Write – MD labs

循环移位异或加密 - Tf1shC4T - 博客园 (cnblogs.com)

Crypto
#MT19937 #Crypto
2022DASCTF MAY 出题人挑战赛
http://example.com/2022/07/13/CTF/2022DASCTF MAY 出题人挑战赛/
作者
gla2xy
发布于
2022年7月13日
许可协议