强网杯 StreamGame3

Posted on | Edited on

介绍

这题和其他的几题，例如streamgame1、2、4，有点不一样，因为直接爆破可能性太多了，根本不可行，所以我们有必要好好分析一下。

流密码

关于流密码的知识可以Google了解，在这里就不再多说。这道题基本思路是，R1、R2、R3三个初始值，每次经过lfsr轮转，产生新的R1、R2、R3，并且将lastbit经过简单运算out = (x1 * x2) ^ ( (x2 ^ 1) * x3)的到一个out输出。out与tmp进行一系列运算得到最终结果，这题结果总共为1G的数据。（题目下载中只给了1M的，因为已经够了）

爆破R1、R3

而此题的突破点就在那个简单的运算，看一个表:

1
2
3
4
5
6
7
8
9
x1  x2  x3  out
0   0   0   0
0   0   1   1
0   1   0   0
0   1   1   0
1   0   0   0
1   0   1   1
1   1   0   1
1   1   1   1

可以发现，x1、x3与out相同的几率很大，约为75%。所以我们可以单独爆破x1、x3，将x1或x3视为out进行加密，然后统计加密结果与正确结果的相同的概率有多少，在75%左右的就是正确答案了，错误答案，理论上来说应该为50%。

爆破R2

在爆破成功了R1、R3之后我们就可以，直接爆破R2了。需要注意的是这里的爆破是根据概率统计来的，所以我们没有必要选全部加密文件来进行统计，选一小部分就可以了（32bit、64bit），因为根据前几题，错误的答案几乎不可能”蒙”出正确答案。

参考

本文参考了队内大佬的文章，文章链接:http://blog.leanote.com/post/xp0intjnu@gmail.com/66c91498d13b

脚本

详细解决脚本如下，脚本中有注释：

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
    def lfsr(R,mask):
    output = (R << 1) & 0xffffff
    i = (R & mask) & 0xffffff

    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    output ^= lastbit
    return (output,lastbit)

def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):

    (R1_NEW,x1) = lfsr(R1,R1_mask)
    (R2_NEW,x2) = lfsr(R2,R2_mask)
    (R3_NEW,x3) = lfsr(R3,R3_mask)

    return (R1_NEW, R2_NEW, R3_NEW, (x1*x2)^((x2^1)*x3) )

# x1 x2 x3 out
#  0  0  0  0
#  0  0  1  1
#  0  1  0  0
#  0  1  1  0
#  1  0  0  0
#  1  0  1  1
#  1  1  0  1
#  1  1  1  1

# 单独用R1、R3进行加密
def single_lfsr(R, R_mask):
    ret = ''
    for i in range(length):
        tmp = 0
        for j in range(8):
            (R, out) = lfsr(R, R_mask)
            tmp = (tmp << 1) ^ out
        ret += chr(tmp)
    return ret

# 统计概率
def count(ret):
    cnt = 0
    for r, c in zip(ret, cipher):
        for i in range(8):
            mask = 1 << i
            if ord(r) & mask == c & mask:
                cnt += 1
    return cnt / (length * 8)

# 爆破R1
def guess_r1():
    possible = 0
    percent = 0.0


    for R1 in range(pow(2, 16),pow(2, 17)):
        ret = single_lfsr(R1, R1_mask)
        per = count(ret)
        if per > percent:
            possible, percent = R1, per

        if per > 0.7:
            print('R1: ' + hex(R1) + '\tpercentage: ' + str(per * 100) + '%')

    print('R1 max:',hex(possible), percent)
    return possible

# 爆破R2
def guess_r3():
    possible = 0
    percent = 0.0

    for R3 in range(pow(2, 20), pow(2, 21)):
        ret = single_lfsr(R3, R3_mask)
        per = count(ret)
        if per > percent:
            possible, percent = R3, per

        if per > 0.7:
            print('R3: ' + hex(R3) + '\tpercentage: ' + str(per * 100) + '%')

    print('R3 max:',hex(possible), percent)
    return possible

# 模拟部分加密
def encrypt(R1, R2, R3):
    ret = []
    for i in range(length):
        tmp = 0
        for j in range(8):
            (R1, R2, R3, out) = single_round(R1, R1_mask, R2, R2_mask, R3, R3_mask)
            tmp = (tmp << 1) ^ out
        ret.append(tmp)
    return bytes(ret)

# 爆破R2
def solve_r2(R1, R3):

    for R2 in range(pow(2, 18), pow(2, 19)):
        ret = encrypt(R1, R2, R3)

        if ret == cipher:
            print('R2:',R2)
            return R2

# 测试的长度（小于32可能得到错误的结果）
length = 32
with open('./output/0','rb') as f:
    cipher = f.read(length)

R1_mask = 0x10020
R2_mask = 0x4100c
R3_mask = 0x100002
# R1、R2、R3的十六进制值在flag中为6为
R_len = 6


R1 = guess_r1()
# R1 = 0x1b9cb

R3 = guess_r3()
# R3 = 0x16b2f3

R2 = solve_r2(R1, R3)
# R2 = 0x5979c

# 补足6位
R1 = hex(R1)[2:].zfill(R_len)
R2 = hex(R2)[2:].zfill(R_len)
R3 = hex(R3)[2:].zfill(R_len)
flag = R1 + R2 + R3

print('flag{'+flag+'}')
# flag={01b9cb05979c16b2f3}

跑脚本需要一定的时间，需要耐心等待，在我电脑上约为18分钟。