r1ngs's blog

反馈移位寄存器小结

2019-04-05

前言

先知已投, 戳我跳转

流密码的关键在于设计好的伪随机数生成器。一般来说,伪随机数生成器的基本构造模块为反馈移位寄存器。反馈函数或者反馈逻辑F如果是线性函数,那么称其为线性反馈移位寄存器(LFSR)否则为非线性反馈移位寄存器

去年反馈移位寄存器的密码学题目考的比较多,前一阵的tctf又出现了这个考点,于是做了一个对LFSR攻击手法的总结

线性反馈移位寄存器

LFSR是什么?如何实现?通过下面这道题可以很好的理解

2018 CISCN 初赛 oldstreamgame

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
flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14

def lfsr(R,mask):
output = (R << 1) & 0xffffffff '''将R左移一位然后保留低32位,赋值给output'''
i=(R&mask)&0xffffffff '''R和mask做与运算,然后保留低32位赋值给i'''
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1 '''让lastbit依次和i的每一位异或,然后赋值给lastbit'''
output^=lastbit
return (output,lastbit)

R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100

f=open("key","w")
for i in range(100):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
f.write(chr(tmp))
f.close()

单从代码层次来看比较难懂,我画了一个流程图便于理解:

通过流程图可以简单概括代码的功能为:将mask的二进制位为1的位置对应到种子flag的位置,让他们做异或运算(比如如果mask的二进制位中第2位和第12位为1,其余位置为0,那么就将flag的第2位和第12位的值异或),然后将flag左移一位,最低位加上刚才做异或运算的结果,如此一直循环,此题解法如下:

每一个lastbit输出,是我们已知的,考虑当flag依次左移到只剩下一个二进制位时,剩下的31位全是已知的输出过后的lastbit,那么第32个lastbit(已知)就由第一位flag(未知)和31个lastbit(已知)生成,这样就能知道第一位的flag然后依次得到所有位的flag了,exp如下:

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
def lfsr(R,mask):
output = (R << 1) & 0xffffffff
i=(R&mask)&0xffffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)


mask = '10100100000010000000100010010100'
key = '00100000111111011110111011111000' '''注意key的高位和低位顺序'''
flag = ''

for i in range(32):
r=key[:-i-1]
l='0'+flag
R=int(l+r, 2)
(out,lastbit)=lfsr(R, int(mask, 2))
out = '{:032b}'.format(out)
if out==flag+key[:-i]:
flag='0'+flag
else:
flag='1'+flag

print hex(int(flag, 2))

非线性反馈移位寄存器

常见的有三种

  • 非线性组合生成器,对多个 LFSR 的输出使用一个非线性组合函数
  • 非线性滤波生成器,对一个 LFSR 的内容使用一个非线性组合函数
  • 钟控生成器,使用一个(或多个)LFSR 的输出来控制另一个(或多个)LFSR 的时钟

目前遇到最多的是第一种

2018 强网杯 streamgame3

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
flag='flag{01b9cb05979c16b2f3}'
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==24

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))

R1=int(flag[5:11],16)
R2=int(flag[11:17],16)
R3=int(flag[17:23],16)
assert len(bin(R1)[2:])==17
assert len(bin(R2)[2:])==19
assert len(bin(R3)[2:])==21
R1_mask=0x10020
R2_mask=0x4100c
R3_mask=0x100002


for fi in range(1024):
print fi
tmp1mb=""
for i in range(1024):
tmp1kb=""
for j in range(1024):
tmp=0
for k in range(8):
(R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
tmp = (tmp << 1) ^ out
tmp1kb+=chr(tmp)
tmp1mb+=tmp1kb
f = open("E:/output/" + str(fi), "ab")
f.write(tmp1mb)
f.close()

题目里的LFSR和第一题一样,但是利用了一个函数将三个LFSR的输出关联起来,来增大解题难度

这里题目告诉了我们R1、R2、R3的2进制长度,虽然直接对flag爆破有难度,但是可以采用关联攻击的思想,对R1、R2、R3分别单独暴破。首先枚举x1, x2, x3和F的所有可能取值

x1 x2​ x3 F
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

如果把每一种可能视作等概率事件,F和x1、x3相同的概率有75%和x2相同的概率有50%,所以我们可以对R1、R3单独枚举,并且用单独的lfsr代替single round,如果和cipher相同的位数接近75%的话就认为枚举正确,而且题目给出的cipher的数据量足够大,足够在这种大量数据的基础下完成攻击,x1和x3猜测出以后,剩下的x2直接爆破就可以解出了,exp如下:

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
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 correlation(a,b):
assert len(a)==len(b)
count = 0
for i, j in zip(a, b):
ib = '{:08b}'.format(ord(i))
jb = '{:08b}'.format(ord(j))
for m, n in zip(ib, jb):
if m == n:
count+=1
return count / (bytes_size * 8.0) * 100

def guess(length, mask):
for n in range(2**(length-1), 2**length):
R = n
s = ''
for i in range(bytes_size):
tmp = 0
for j in range(8):
(R, out) = lfsr(R, mask)
tmp = (tmp << 1) ^ out
s += chr(tmp)
pb = correlation(s, cipher)
'''print pb,hex(n)'''
if 72<=pb<=78:
print pb,hex(n)

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))

def brute_force(R1, R3, length):
for n in range(2**(length-1), 2**length):
r2 = n
r1 = R1
r3 = R3
s = ''
for i in range(bytes_size):
tmp = 0
for k in range(8):
(r1, r2, r3, out) = single_round(r1, R1_mask, r2, R2_mask, r3, R3_mask)
tmp = (tmp << 1) ^ out
s += chr(tmp)
assert len(s)==len(cipher)
'''print hex(n)'''
if s == cipher:
return str(hex(n))


bytes_size = 64
with open("E:/output/0") as f:
cipher = f.read(bytes_size)


R1_mask=0x10020
R2_mask=0x4100c
R3_mask=0x100002

len1=17
len2=19
len3=21

'''guess(len1, R1_mask) #76.5625 0x1b9cb'''
R1 = 0x01b9cb
'''guess(len3, R3_mask) #73.4375 0x16b2f3'''
R3 = 0x16b2f3

print brute_force(R1, R3, len2) '''0x5979c'''

在选择64个字节进行比较的情况下,实测R1和R3的相似度分别为$76.6\%$和$73.4\%$,故最终flag为flag{01b9cb05979c16b2f3}

TCTF 2019 zer0lfsr

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
from secret import init1,init2,init3,FLAG
import hashlib
assert(FLAG=="flag{"+hashlib.sha256(init1+init2+init3).hexdigest()+"}")

class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1

def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output
self.init = nextdata
return output

def combine(x1,x2,x3):
return (x1*x2)^(x2*x3)^(x1*x3)

if __name__=="__main__":
l1 = lfsr(int.from_bytes(init1,"big"),0b100000000000000000000000010000000000000000000000,48)
l2 = lfsr(int.from_bytes(init2,"big"),0b100000000000000000000000000000000010000000000000,48)
l3 = lfsr(int.from_bytes(init3,"big"),0b100000100000000000000000000000000000000000000000,48)

with open("keystream","wb") as f:
for i in range(8192):
b = 0
for j in range(8):
b = (b<<1)+combine(l1.next(),l2.next(),l3.next())
f.write(chr(b).encode())

和上一题差不多,但是l1, l2, l3长度未知,也许和mask的长度可能差不多,所以上面的攻击思路不好利用

这道题的漏洞点在于掩码的选择上,可以发现三个掩码尽管有48bit但是只有两个bit是1,其余的都是0

先从单个lfsr研究:

那从之前的这张图就可以看到每一轮的运算等价于是对有1的两个bit位做的一个异或,然后贴到R的最低位

由于后面所有的异或的值已知,所以实际上可以通过列线性方程组的方法恢复出每一位,我写了一个demo来模拟500轮变化:

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
init = []
for i in range(48):
init.append(str(i+1))

def counter(c, li):
count = 0
for i in li:
if c == i:
count += 1
return count

def clear(string):
new = []
for c in string.split('+'):
if counter(c, string.split('+'))==1:
new.append(c)


return '+'.join(new)

for i in range(500):
print init
tmp = init[0]+'+'+init[6]

init = init[1:]
init.append(clear(tmp))

输出结果中使用+代表异或,每一个list即代表寄存器中目前存放的是哪几个初始bit,假设掩码中从高位数起的第1位和第7位为1,输出结果如下:

追踪初始值1 xor 7可以看到后面还有和1 xor 7单独异或的结果

也就是说我们知道了43 xor 1 xor 7和1 xor 7的结果,那么我们把这两者异或就能得到第43位的值,而我们所有有关xor的项都是知道的,所以只要数据量够大,就可以通过列出一系列线性方程组来恢复出所有的bit位

但是我们如果想实现这个攻击的话,是比较麻烦的,我们可以用python z3库来帮助我们实现,这里推荐在linux环境下安装z3库:pip install z3-solver

我们只需要为z3的solver添加每一轮的约束断言,z3就能解决这个问题了

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
from libnum import *
from z3 import *
from os import urandom


class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1

def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output
self.init = nextdata
return output


def get_pos(mask):
s_mask = bin(mask)[2:]
pos = []
for i in range(len(s_mask)):
if s_mask[i] == '1':
pos.append(len(s_mask)-i-1)
return pos

def combine(x1,x2,x3):
return (x1*x2)^(x2*x3)^(x1*x3)


def single_lfsr(cipher, pos, length):
s = Solver() '''初始化一个Sovler api'''
x = BitVec('x', length) '''定义一个bit向量'''
for c in cipher:
x_bit1 = LShR(x & (1 << pos[0][0]), pos[0][0])'''LShR表示二进制位右移'''
x_bit2 = LShR(x & (1 << pos[0][1]), pos[0][1])
xs = x_bit1 ^ x_bit2
x = ((x << 1) & (2 ** (length + 1) - 1)) ^ xs
s.add(xs == int(c))'''向s添加约束断言'''

s.check()
return str(s.model())


if __name__=="__main__":
mask1 = 0b100000000000000000000000010000000000000000000000
init1 = urandom(48/8)

print 'init:', s2n(init1)

flag1 = lfsr(s2n(init1), mask1, 48)


keystream = ""
for i in range(48):
keystream += str(flag1.next())

res = single_lfsr(keystream, [get_pos(mask1)], 48)
print res

运行结果为:

注意keystream的大小,如果太小的话可能会得出错误的答案,应该尽可能的让数据量大,但又不至于太大

那么对于3轮来说的话,我们只需要把bit向量的个数扩充到3个,然后依次添加约束就好了,这样的话只是方程组复杂了一点

我们尝试下一个demo,发现z3同样也是可以为我们解出的

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
from libnum import *
from z3 import *
from os import urandom


class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1

def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output
self.init = nextdata
return output


def get_pos(mask):
s_mask = bin(mask)[2:]
pos = []
for i in range(len(s_mask)):
if s_mask[i] == '1':
pos.append(len(s_mask)-i-1)
return pos

def combine(x1,x2,x3):
return (x1*x2)^(x2*x3)^(x1*x3)

def break_3_lfsr(cipher, pos, length):
s = Solver()
x = BitVec('x', length)
y = BitVec('y', length)
z = BitVec('z', length)


for c in cipher:

x_bit1 = LShR(x & (1 << pos[0][0]), pos[0][0])
x_bit2 = LShR(x & (1 << pos[0][1]), pos[0][1])
xs = x_bit1 ^ x_bit2
x = ((x << 1) & (2 ** (length + 1) - 1)) ^ xs

y_bit1 = LShR(y & (1 << pos[1][0]), pos[1][0])
y_bit2 = LShR(y & (1 << pos[1][1]), pos[1][1])
ys = y_bit1 ^ y_bit2
y = ((y << 1) & (2 ** (length + 1) - 1)) ^ ys

z_bit1 = LShR(z & (1 << pos[2][0]), pos[2][0])
z_bit2 = LShR(z & (1 << pos[2][1]), pos[2][1])
zs = z_bit1 ^ z_bit2
z = ((z << 1) & (2 ** (length + 1) - 1)) ^ zs

s.add(combine(xs, ys, zs) == int(c))

s.check()
return s.model()


if __name__=="__main__":
mask1 = 0b100000000000000000000000010000000000000000000000
mask2 = 0b100000000000000000000000000000000010000000000000
mask3 = 0b100000100000000000000000000000000000000000000000


init1 = urandom(48/8)
init2 = urandom(48/8)
init3 = urandom(48/8)
print 'init:', s2n(init1), s2n(init2), s2n(init3)

flag1 = lfsr(s2n(init1), mask1, 48)
flag2 = lfsr(s2n(init2), mask2, 48)
flag3 = lfsr(s2n(init3), mask3, 48)


keystream = ""
for i in range(48*8):
keystream += str(combine(flag1.next(), flag2.next(), flag3.next()))

res = break_3_lfsr(keystream, [get_pos(mask1), get_pos(mask2), get_pos(mask3)], 48)

print res

运行结果为

这样的结果就足够让人兴奋了,说明有很大的可能是可以将flag直接解出的

先放一下这道题最终的exp:

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
from libnum import *
from z3 import *
from os import urandom
from hashlib import sha256



def get_pos(mask):
s_mask = bin(mask)[2:]
pos = []
for i in range(len(s_mask)):
if s_mask[i] == '1':
pos.append(len(s_mask) - i - 1)
return pos


def combine(x1, x2, x3):
return (x1 * x2) ^ (x2 * x3) ^ (x1 * x3)


def break_3_lfsr(cipher, pos, length):
s = Solver()
x = BitVec('x', length)
y = BitVec('y', length)
z = BitVec('z', length)

for c in cipher:
x_bit1 = LShR(x & (1 << pos[0][0]), pos[0][0])
x_bit2 = LShR(x & (1 << pos[0][1]), pos[0][1])
xs = x_bit1 ^ x_bit2
x = ((x << 1) & (2 ** (length + 1) - 1)) ^ xs

y_bit1 = LShR(y & (1 << pos[1][0]), pos[1][0])
y_bit2 = LShR(y & (1 << pos[1][1]), pos[1][1])
ys = y_bit1 ^ y_bit2
y = ((y << 1) & (2 ** (length + 1) - 1)) ^ ys

z_bit1 = LShR(z & (1 << pos[2][0]), pos[2][0])
z_bit2 = LShR(z & (1 << pos[2][1]), pos[2][1])
zs = z_bit1 ^ z_bit2
z = ((z << 1) & (2 ** (length + 1) - 1)) ^ zs

s.add(combine(xs, ys, zs) == int(c))

s.check()
return s.model()


if __name__ == "__main__":

mask1 = 0b100000000000000000000000010000000000000000000000
mask2 = 0b100000000000000000000000000000000010000000000000
mask3 = 0b100000100000000000000000000000000000000000000000

with codecs.open('keystream', 'rb', 'utf8') as f:
data = f.read(48)

cipher = ''
for c in data:
cipher += '{:08b}'.format(ord(c))
''' print cipher '''


res = break_3_lfsr(cipher, [get_pos(mask1), get_pos(mask2), get_pos(mask3)], 48*8)
print res

'''
[z = 191532558614761,
y = 181037482648735,
x = 70989122156399]

'''
z = 191532558614761
y = 181037482648735
x = 70989122156399
print 'flag{' + sha256(n2s(x) + n2s(y) + n2s(z)).hexdigest() + '}'

其中有一个非常坑的地方,就是题目脚本是用了python3的encode()方法将每个字节用utf-8编码了再写入进去的,所以我们打开文件的时候也必须指定utf-8编码格式打开

思考

那么是不是说明这种的非线性组合生成器存在通用的解法呢?是不是强网杯的那道题也可以用这样的做法呢?毕竟从上面的题看上去并没有对参数有特殊的限制,但是笔者进行了测试,强网杯的题这样做是没有解的,并且这种做法对参数是有比较严格的限制的,笔者利用“控制变量法”对三个mask,F函数,三个初始变量进行了测试,这些参数需满足以下约束条件,否则可能出现无解或多解的情况:

  • F函数的值与x1, x2, x3相同的概率要尽可能大,就像强网杯的那道题一样
  • mask的长度要尽可能地和tctf代码中的lengthmask相同
  • mask的二进制位中为1的个数要尽可能的少

而对三个初始变量的值则没有比较严格的要求

总结

通过这三道CTF,不仅理解了LFSR的实现过程,还学习到了较多的攻击手法,收获很多

Tags: 分析

1000000