20220522-DAS MAY 出题人挑战赛-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 6.1k Reading time ≈ 6 mins.

 

  • 考点：MT19937伪随机恢复与预测

集大成者

起手式

MT19937

先看下wiki上MT19937算法，以python实现

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 _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)


    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)


    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

逆extract_number

extract_number是最后进行随机数返回的，所以要先逆

而位运算都是可以逆的，就算魔改了数据也一样

1
2
3
4
5
6
7
8
9
def recover_state(out):
    state = []
    for i in out:
        i = inverse_right(i, 18)
        i = inverse_left_values(i, 15, 4022730752)
        i = inverse_left_values(i, 7, 2636928640)
        i = inverse_right(i, 11)
        state.append(i)
    return state

逆extract_number plus

魔改了位运算的形式，比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

如果只看一次位运算，会发现基本上没得玩

image-20220523135035059

但是包括之前做到过的，这类反复进行相同的位运算是可以逆回来的，不晓得为什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def cs2l(y, shift):
    return ((y << shift) ^ (y >> (32 - shift))) & 0xffffffff


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


def recover_state(out):
    ret = []
    for _ in out:
        y = _
        for j in range(7):
            y = y ^ cs2r(y, 7) ^ cs2r(y, 19)
        for j in range(7):
            y = y ^ cs2l(y, 11) ^ cs2l(y, 15)
        ret.append(y)
    return ret

逆twist

twist就是梅森旋转的旋转，每生成624次随机数都将624个状态进行旋转，只要有624个随机数，在逆extract_number之后，twist也是可逆的

先逆最高位（需要对应的两组随机数

再逆低31位（也需要对应的两组随机数

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
def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(623, -1, -1):
        tmp = state[i] ^ state[(i + 397) % 624]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<= 1
        # recover 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] ^ state[(i + 396) % 624]
        # 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

逆init

初始化624位状态，其中初始值，即种子可以自己定

其实就是一个模运算，可以求个逆元逆回来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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(2037740385, n)
    for i in range(623, 0, -1):
        last = ((last - 1) * inv) % n
        last = invert_right(last, 30)
    return last

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

特点：已知624个连续随机数，魔改extract_number的数字和形式

题目代码

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
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
		print(self.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

import os
secret = int(os.urandom(4).hex(),16)
r = Myrand(secret)
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)

正是前面所讲的一般类型

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

特点：生成624个随机数，能够指定知道其中两个

上面提到的逆twist中的一组总共需要知道四组，而知道两组可以恢复低31位或者最高位，知道低31位后，最高位可以爆破

题目代码

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

		for i in range(1,624):
			t = 2037740385 * (self.MT[i-1] ^ (self.MT[i-1] >> 30)) + 1
			self.MT[i] = t & 0xffffffff
		#print(self.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
		#print(self.MT)
	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
secret = int(os.urandom(4).hex(),16)
print(secret)
r = Myrand(secret)
out = []
for i in range(624):
	out.append(r.rand())
print(out)
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()

image-20220522194602473

Yusa的密码学课堂——三行情书

题目代码

1
2
3
import random
output=[random.getrandbits(32) & 2037740385 for i in range(2000)]
flag = 'DASCTF{'+hex(random.getrandbits(32*4))[2:] + '}' # DASCTF{3797****************************}

知道2000个随机数，但是其中有15位被与掉了

有个脚本，https://github.com/icemonster/symbolic_mersenne_cracker

不晓得为什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def mt19937truncated():
    a = 2037740385
    a = bin(a)[2:].rjust(32, '0')
    x = []
    for i in range(len(a)):
        if a[i] == '0':
            x.append(i)
    r1 = Random()
    ut = Untwister()
    r = 
    for i in r:
        ut.submit(fun(i, x))
        r1.getrandbits(32)

    r2 = ut.get_random()
    flag = 'DASCTF{' + hex(r2.getrandbits(32 * 4))[2:] + '}'  # DASCTF{3797****************************}
    print(flag)

    
if __name__ == '__main__':
    mt19937truncated()
# DASCTF{3797d603cc622d3de7858f42726aea48}

Reference

  1. 安全客-浅析MT19937伪随机数生成算法
  2. https://zh.m.wikipedia.org/zh/梅森旋转算法