SUCTF2019-MT

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

 

首先要知道位运算的优先级，由高到低：<<，&，^

考点

  • MT19937

题目代码

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


def convert(m):
    m = m ^ m >> 13     # 高13位不变
    m = m ^ m << 9 & 2029229568     # 低9位不变
    m = m ^ m << 17 & 2245263360    # 低17位不变
    m = m ^ m >> 19     # 高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

朴素的方法

第一次接触MT19937，最直观的想法就是把convert逆回去

  • 第一四组位运算

    [SUCTF2019]MT 我也很异或呢-f4ee9bb3.png

    与第一个位运算相同，第四个位运算也可以逆回来

    1
    2
    3
    4
    5
    6
    7
    def forth_cal_re(c, x):
        y = len(bin(c)[2:])-x
        c = bin(c)[2:]
        part1 = c[0:x].zfill(x)
        part2 = bin(int(c[x:], 2) ^ int(c[:y], 2))[2:].zfill(y)
        output = int(part1+part2, 2)
        return output

    合并一下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def first_cal_re(c, x):
        y = len(bin(c)[2:].zfill(31))-2*x
        if y <= 0:
            y = len(bin(c)[2:].zfill(31)) - x
            c = bin(c)[2:].zfill(31)
            # 高x位完全相同
            part1 = c[0:x].zfill(x)
            part2 = bin(int(c[x:], 2) ^ int(c[:y], 2))[2:].zfill(y)
            output = int(part1 + part2, 2)
            return output
        c = bin(c)[2:].zfill(31)
        # 高x位完全相同
        high13 = c[0:x].zfill(x)
        # 中间的几位
        mid5 = bin(int(c[x:x+y], 2) ^ int(high13[:y], 2))[2:].zfill(y)
        low13 = bin(int(c[x+y:], 2) ^ int((high13+mid5)[y:], 2))[2:].zfill(x)   # 注意填充
        output = int(high13+mid5+low13, 2)
        return output

  • 第二三组位运算

    如法炮制，总之也是可以逆回去的

    [SUCTF2019]MT 我也很异或呢-86361ff5.png

    实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def second_cal_re(c, x, y):
        y = bin(y)[2:].zfill(32)
        c = bin(c)[2:].zfill(32)
        output = [0 for _ in range(len(c))]
        # 低x位保持不变
        for i in range(len(y)-x, len(y)):
            output[i] = int(c[i])
        # 13-21位 = (低x位)&(y[13:21])^c[13:21]
        for i in range(len(y)-2*x, len(y)-x):
            output[i] = output[i+x] & int(y[i]) ^ int(c[i])
        # 4-12位 = (13-21位)&(y[4:12])^c[4:12]
        for i in range(len(y)-3*x, len(y)-2*x):
            output[i] = output[i+x] & int(y[i]) ^ int(c[i])
        # 高4位 = (8-12位)&(y[0:3])^c[0:3]
        for i in range(0, 5):
            output[i] = output[i+x] & int(y[i]) ^ int(c[i])
        output = "".join(map(lambda _: str(_), output))
        output = int(output, 2)
        return output

但在实际跑的时候，存在一些bug。比如1234转数字是9位，而abcd是8位

最后看着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
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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *


def first_cal_re(c, x):
    y = len(bin(c)[2:].zfill(31))-2*x
    if y <= 0:
        y = len(bin(c)[2:].zfill(31)) - x
        c = bin(c)[2:].zfill(31)
        # 高x位完全相同
        part1 = c[0:x].zfill(x)
        part2 = bin(int(c[x:], 2) ^ int(c[:y], 2))[2:].zfill(y)
        output = int(part1 + part2, 2)
        return output
    c = bin(c)[2:].zfill(31)
    # 高x位完全相同
    high13 = c[0:x].zfill(x)
    # 中间的几位
    mid5 = bin(int(c[x:x+y], 2) ^ int(high13[:y], 2))[2:].zfill(y)
    low13 = bin(int(c[x+y:], 2) ^ int((high13+mid5)[y:], 2))[2:].zfill(x)   # 注意填充
    output = int(high13+mid5+low13, 2)
    return output


def second_cal_re(c, x, y):
    y = bin(y)[2:].zfill(32)
    c = bin(c)[2:].zfill(32)
    output = [0 for _ in range(len(c))]
    # 低x位保持不变
    for i in range(len(y)-x, len(y)):
        output[i] = int(c[i])
    # 13-21位 = (低x位)&(y[13:21])^c[13:21]
    for i in range(len(y)-2*x, len(y)-x):
        output[i] = output[i+x] & int(y[i]) ^ int(c[i])
    # 4-12位 = (13-21位)&(y[4:12])^c[4:12]
    for i in range(len(y)-3*x, len(y)-2*x):
        output[i] = output[i+x] & int(y[i]) ^ int(c[i])
    # 高4位 = (8-12位)&(y[0:3])^c[0:3]
    for i in range(0, 5):
        output[i] = output[i+x] & int(y[i]) ^ int(c[i])
    output = "".join(map(lambda _: str(_), output))
    output = int(output, 2)
    return output


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


def re_convert(m):
    m = first_cal_re(m, 19)
    m = second_cal_re(m, 17, 2245263360)
    m = second_cal_re(m, 9, 2029229568)
    m = first_cal_re(m, 13)
    return m


def test():
    # 对应括号外的encode('hex')
    message = b'641460a9e3953b1aaa21f3a2'.decode('hex')

    new_message = ''
    for i in range(len(message) // 4):
        block = message[i * 4: i * 4 + 4].ljust(4, ' ')
        block = bytes_to_long(block)
        block = re_convert(block)
        block = long_to_bytes(block, 4)
        new_message += block
    print new_message.encode('hex')


def main():
    test()

main()

尚师傅的方法

简单来说，有类位运算是可以移回来的，也就是

1
2
for i in range(xxx):
    m = convert(m)

循环固定的次数就能够恢复初试的状态

不清楚是为啥，但经常在比赛中遇到

通用的方法

其实这里的convert作为MT19937中extract_number的一部分，逆向convert是有固定套路的，也就是用位运算精简上面朴素的方法

不带mask的右移

1
m = m ^ m >> 18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        print_i(tmp >> shift)
        tmp = res ^ tmp >> shift
        print_i(tmp)
    return tmp

def print_i(x):
    print(bin(x)[2:].rjust(32))

i = 1234567891
print_i(i)
print_i(i >> 18)
i = i ^ i >> 18
print_i(i)
i = inverse_right(i, 18)
# 1001001100101100000001011010011
#                   1001001100101
# 1001001100101100001000010110110
#                   1001001100101
# 1001001100101100000001011010011

带mask的左移

1
m = m ^ m << 17 & 2245263360
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 inverse_left_values(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        print_i(tmp << shift)
        print_i(tmp << shift & mask)
        tmp = res ^ tmp << shift & mask
        print_i(tmp)
    return tmp

def print_i(x):
    print(bin(x & 0xffffffff)[2:].rjust(32))

i = 1234567891
print_i(2245263360)
print_i(i)
print_i(i << 17)
print_i(i << 17 & 2245263360)
i = i ^ i << 17 & 2245263360
print_i(i)
i = inverse_left_values(i, 17, 2245263360)
# 10000101110101000000000000000000
#  1001001100101100000001011010011
#      101101001100000000000000000
#      101100001000000000000000000
#  1001100000100100000001011010011
#      101101001100000000000000000
#      101100001000000000000000000
#  1001001100101100000001011010011

细想还挺简单的

最后附上官方wp