Σ2333! の 博客
0%

BUUCTF 每日打卡 2021-7-24

发表于 更新于

BUUCTF 每日打卡 2021-7-24

引言

台风天，还练了一天车，淦

[SUCTF2019]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
from Crypto.Util import number
from flag import flag

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m

def transform(message):
    assert len(message) % 4 == 0
    new_message = ''
    for i in range(len(message) / 4):
        block = message[i * 4 : i * 4 +4]
        block = number.bytes_to_long(block)
        block = convert(block)
        block = number.long_to_bytes(block, 4)
        new_message += block
    return new_message

transformed_flag = transform(flag[5:-1].decode('hex')).encode('hex')
print 'transformed_flag:', transformed_flag
# transformed_flag: 641460a9e3953b1aaa21f3a2

看到这个convert函数，我就有些胆怯了 这个位运算看起来完全打乱了加密内容（而且之前碰到类似的题目都没做出来） 尤其是第二三步，感觉完全乱了 看了一眼别人的wp，受到了启发 发现bin(2029229568)后9位都是0，而bin(2245263360)后17位(其实是18位)都是0，与移位的位数相同，那就好办了 首先要明确一件事：位运算符的优先级 移位(>>和<<) > 与运算(&) > 异或运算(^) 就以'abcd'为例，推出第四和第三步的解密过程（第一和第二步同理） 因为我没有装python2的环境，就用python3把加密代码重写了一遍，做了一点小修改 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

flag = 'abcd'

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m

def transform(message):
    assert len(message) % 4 == 0
    new_message = ''
    for i in range(len(message) // 4):
        block = message[i * 4: i * 4 + 4]
        block = bytes_to_long(block.encode())
        block = convert(block)
        block = bin(block)[2:].zfill(32)
        new_message += block
    return long_to_bytes(int(new_message, 2))

cipher = transform(flag)

第四步操作

首先要知道，">>"是二进制位向右移动，低位丢弃，高位补0 经过前三步加密的二进制结果为（当然，解密时以下结果是未知的）： 10100101011101011110111001110111记为m4 那么 m4>>19 的结果为 0000000000000000000101001010111 01011110111001110111 高位补0<- ->低位丢弃 接下来是异或运算 解密需要用到异或运算的两个性质： 1、若a=b ^ c，则c=a ^ b 2、a=a ^ 0 

1
2
3
4
5
6
7
8
9
10
11
12
按位加密的过程中，m4的前19位都是和0做异或运算，也就是说加密结果cipher的前19位与m4是相同的，由此可以得到m4的前19位
又因为**m4后13位 ^ m4>>19的后13位 = m4后13位 ^ m4的前13位 = cipher的后13位**
所以**cipher的后13位 ^ m4的前13位 = m4后13位**
由此可以得到完整的m4
解密代码如下：
```python
block = bytes_to_long((cipher[i * 4: i * 4 + 4]))
block = bin(block)[2:].zfill(32)
# step4 decode
m4 = block[:19] + bin(int(block[:13], 2) ^ int(block[19:], 2))[2:].zfill(13)
print(m4)
print(long_to_bytes(int(m4, 2)))

第三步操作

首先要知道，"<<"是二进制位向左移动，高位丢弃，低位补0；"&"是按位做与运算，有0出0，全1出1 经过前两步加密的二进制结果为（当然，解密时以下结果是未知的）： 00100001101100011110111001110111记为m3 00100001101100011 11011100111011100000000000000000 高位丢弃<- ->低位补0 接下来是与运算 首先看bin(2245263360)='0b10000101110101000000000000000000' 发现2245263360的后17位都是0 那么，m3<<17的后17位 & 2245263360的后17位 = 00000000000000000(17个0) 与第四步解密操作相同，就可以得到m3的后17位就是m4的后17位 又因为m3前15位 ^ m3<<17的前15位 & 2245263360的前15位 = m3前15位 ^ m3的后15位 & 2245263360的前15位 = m4的前15位 由此可以得到完整的m3 解密代码如下： 

1
2
3
4
5
# step3 decode
block = m4
m3 = bin((int(block[17:], 2) & int(bin(2245263360)[2:].zfill(32)[:15], 2)) ^ int(block[:15], 2))[2:].zfill(15) + block[15:]
print(m3)
print(long_to_bytes(int(m3, 2)))
第二和第一步的解密类似，就是需要重复操作几次 完整的测试解密代码如下： 
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
from Crypto.Util.number import *

flag = 'abcd'

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m

def transform(message):
    assert len(message) % 4 == 0
    new_message = ''
    for i in range(len(message) // 4):
        block = message[i * 4: i * 4 + 4]
        block = bytes_to_long(block.encode())
        block = convert(block)
        block = bin(block)[2:].zfill(32)
        new_message += block
    return long_to_bytes(int(new_message, 2))

cipher = transform(flag)
print(bin(bytes_to_long(cipher))[2:].zfill(32))
print(cipher)
plain = ''
for i in range(len(cipher) // 4):
    block = bytes_to_long((cipher[i * 4: i * 4 + 4]))
    block = bin(block)[2:].zfill(32)
    # step4 decode
    m4 = block[:19] + bin(int(block[:13], 2) ^ int(block[19:], 2))[2:].zfill(13)
    print(m4)
    print(long_to_bytes(int(m4, 2)))
    # step3 decode
    block = m4
    m3 = bin((int(block[17:], 2) & int(bin(2245263360)[2:].zfill(32)[:15], 2)) ^ int(block[:15], 2))[2:].zfill(15) + block[15:]
    print(m3)
    print(long_to_bytes(int(m3, 2)))
    # step2 decode
    block = m3
    m2 = bin((int(block[23:], 2) & int(bin(2029229568)[2:].zfill(32)[14:23], 2)) ^ int(block[14:23], 2))[2:].zfill(9) + block[23:]
    block = m3[:14] + m2
    m2 = bin((int(block[14:23], 2) & int(bin(2029229568)[2:].zfill(32)[5:14], 2)) ^ int(block[5:14], 2))[2:].zfill(9) + block[14:]
    block = m3[:5] + m2
    m2 = bin((int(block[9:14], 2) & int(bin(2029229568)[2:].zfill(32)[:5], 2)) ^ int(block[:5], 2))[2:].zfill(5) + block[5:]
    print(m2)
    print(long_to_bytes(int(m2, 2)))
    # step1 decode
    block = m2
    m1 = block[:13] + bin(int(block[:13], 2) ^ int(block[13:26], 2))[2:].zfill(13)
    block = m1 + block[26:]
    m1 = block[:26] + bin(int(block[13:19], 2) ^ int(block[26:], 2))[2:].zfill(6)
    print(m1)
    print(long_to_bytes(int(m1, 2)))
    plain += m1
print(long_to_bytes(int(plain, 2)))
结果是对的 在这里插入图片描述 然后就把测试解密的代码应用于transformed_flag上 这里有个地方有点麻烦，就是原加密代码还要一步：transformed_flag = transform(flag[5:-1].decode('hex')).encode('hex') 而python3没有decode('hex')和encode('hex')，可以参考Python3 字符串与hex之间的相互转换 .decode('hex')对应于bytes.fromhex()，.encode('hex')对应于.hex() 所以，完整的解密代码如下：

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

cipher = bytes.fromhex('641460a9e3953b1aaa21f3a2')
print(cipher)
plain = ''
for i in range(len(cipher) // 4):
    block = bytes_to_long((cipher[i * 4: i * 4 + 4]))
    block = bin(block)[2:].zfill(32)
    # step4 decode
    m4 = block[:19] + bin(int(block[:13], 2) ^ int(block[19:], 2))[2:].zfill(13)
    print(m4)
    print(long_to_bytes(int(m4, 2)))
    # step3 decode
    block = m4
    m3 = bin((int(block[17:], 2) & int(bin(2245263360)[2:].zfill(32)[:15], 2)) ^ int(block[:15], 2))[2:].zfill(15) + block[15:]
    print(m3)
    print(long_to_bytes(int(m3, 2)))
    # step2 decode
    block = m3
    m2 = bin((int(block[23:], 2) & int(bin(2029229568)[2:].zfill(32)[14:23], 2)) ^ int(block[14:23], 2))[2:].zfill(9) + block[23:]
    block = m3[:14] + m2
    m2 = bin((int(block[14:23], 2) & int(bin(2029229568)[2:].zfill(32)[5:14], 2)) ^ int(block[5:14], 2))[2:].zfill(9) + block[14:]
    block = m3[:5] + m2
    m2 = bin((int(block[9:14], 2) & int(bin(2029229568)[2:].zfill(32)[:5], 2)) ^ int(block[:5], 2))[2:].zfill(5) + block[5:]
    print(m2)
    print(long_to_bytes(int(m2, 2)))
    # step1 decode
    block = m2
    m1 = block[:13] + bin(int(block[:13], 2) ^ int(block[13:26], 2))[2:].zfill(13)
    block = m1 + block[26:]
    m1 = block[:26] + bin(int(block[13:19], 2) ^ int(block[26:], 2))[2:].zfill(6)
    print(m1)
    print(long_to_bytes(int(m1, 2)))
    plain += m1
print(long_to_bytes(int(plain, 2)))
print(long_to_bytes(int(plain, 2)).hex())

结果为： 在这里插入图片描述 即为flag

未曾设想的道路

正如wp中所说，还有一种通过反复加密得到结果的解法 这里给出python3的代码： 

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

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m

def transform(message):
    assert len(message) % 4 == 0
    new_message = b''
    for i in range(len(message) // 4):
        block = message[i * 4: i * 4 + 4]
        block = bytes_to_long(block)
        block = convert(block)
        block = long_to_bytes(block, 4)
        new_message += block
    return new_message

transformed_flag = '641460a9e3953b1aaa21f3a2'
cipher = bytes.fromhex('641460a9e3953b1aaa21f3a2')
# assert (transform(bytes.fromhex('84b45f89af22ce7e67275bdc')).hex() == transformed_flag)
c = cipher
s = set()
while True:
    c = transform(c.zfill(len(cipher)))
    print(c.hex())
    s.add(c.hex())
    print(len(s))
    if c.hex() == transformed_flag:
        break
至于为什么，是因为本题使用的加密算法是梅森旋转算法（Mersenne twister），是一种伪随机数生成算法，该算法的一个更新的和更常用的是MT19937, 32位字长，对应了题目 并且该算法生成的随机数具有周期性，这也就不难理解为什么一直加密密文能得到明文，因为经过一个周期后得到的还是密文，那么上一个就是明文了 上述解密代码结果为： 在这里插入图片描述 不难发现其周期为61319

更多关于MT19937伪随机数生成算法的体型可以参考madmonkey前辈的浅析mt19937伪随机数生成算法 其中介绍了与第一种方法相同的解法，只不过和wp一样采用模块化的代码，将解密步骤打包成函数 这里给出参照其中代码的解密代码：

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

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


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

# left shift inverse
def inverse_left(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 extract_number(y):
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y & 0xffffffff

def recover(y):
    y = inverse_right(y, 19)
    y = inverse_left_mask(y, 17, 2245263360)
    y = inverse_left_mask(y, 9, 2029229568)
    y = inverse_right(y, 13)
    return y & 0xffffffff

transformed_flag = '641460a9e3953b1aaa21f3a2'
cipher = bytes.fromhex('641460a9e3953b1aaa21f3a2')
new_message = b''
for i in range(len(cipher) // 4):
    block = cipher[i * 4: i * 4 + 4]
    block = bytes_to_long(block)
    block = recover(block)
    block = long_to_bytes(block, 4)
    new_message += block
print(new_message.hex())

结果是相同的： 在这里插入图片描述 另一种方法是黑箱方法，将密文和明文的二进制编码视为两个向量\(a,b\)，而由加密方法可知，两个向量存在线性关系，即存在一个方阵\(M\)，使得\(a=Mb\) 具体线性关系如下： 在这里插入图片描述 这种方法没怎么看懂，以后有机会再说（溜了溜了）

结语

昨天(7.24)写了一点，但没写完 因为方法二的代码出了bug，怎么都没法解决，感谢Phoenix大佬帮我改了 今天(7.25)争取加更一期 （你问我7.23干嘛去了？补了一天番[doge]） 希望继续坚持

欢迎关注我的其它发布渠道

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