前言
这篇博客其实在xman培训的时候就应该出的，但当时还有一些没学通，所以拖到现在
简介
这个其实是硬件实现的一个过程，但是被人搬去了密码学上使用，于是就有了这个知识点啦
这其实是一种流密码，整个过程可以简单的理解成一串数据放去进行一系列随机化操作以后获得加密后的数据，这中间的操作，也就是反馈函数如果是线性的，那就是线性反馈移位寄存器，如果是非线性的，那就是非线性反馈移位寄存器，emmm，这么说很难理解，放几个例题就能懂了
线性反馈移位寄存器LFSR
2018 ciscn oldstream
1 | flag = "flag{xxxxxxxxxxxxxxxx}" |
这是国赛的一道题，也是一道比较简单的LSRF的题目，先读代码，简单的可以理解成：将mask的二进制为1的地方跟flag对应起来，然后记录到I上，然后将1的个数记录到output上，一直循环进行运算，再简单一点的理解就是循环将高位的值异或到低位上，信息并没有丢失，所以我们要解密逆推回去就行了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
34import libnum
from Crypto.Util.number import bytes_to_long
# coding=utf-8
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)
def lfsr_inv(R, mask):
str = bin(R)[2:].zfill(32)
new = str[-1:] + str[:-1] #最后一个 + 前面31个
new = int(new, 2)
i = (new & mask) & 0xffffffff
lastbin = 0
while i!=0:
lastbin ^= (i & 1)
i = i >> 1
return R>>1 | lastbin<<31
# flag = 14-5-1 = 8
mask = 0b10100100000010000000100010010100
data = open("key").read()
data = data[:4]
c = bytes_to_long(data)
for k in range(32):
c = lfsr_inv(c, mask)
print hex(c)
#flag: 0x926201d7L
这题还有另一种使用矩阵变幻的做法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
27mask = 0b10100100000010000000100010010100
N = 32
F = GF(2)
b = ''
with open('key', 'rb') as f:
b = f.read()
R = [vector(F, N) for i in range(N)]
for i in range(N):
R[i][N - 1] = mask >> (31 - i) & 1
for i in range(N - 1):
R[i + 1][i] = 1
M = Matrix(F, R)
M = M ^ N
vec = vector(F, N)
row = 0
for i in range(N / 8):
t = ord(b[i])
for j in xrange(7, -1, -1):
vec[row] = t >> j & 1
row += 1
print rank(M)
num = int(''.join(map(str, list(M.solve_left(vec)))), 2)
print hex(num)
2019 de1ctf babylfsr
前面的做法只能适用于flag长度比较小的时候，当flag长度比较长的时候，直接爆破显然是不现实的，算力支撑不了，因此只能进行矩阵变换进行求解
非线性反馈移位寄存器NFSR
非线性的反馈移位寄存器一般有三种1
2
3非线性组合生成器，对多个LFSR的输出内容使用一个非线性的组合函数
非线性滤波生成器，对一个LSRF的输出内容使用一个非线性的组合函数
钟控生成器，使用一个或多个LFSR的输出来控制另一个或多个LFSR的时钟
2018 ciscn 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
48flag='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("./output/" + str(fi), "ab")
f.write((bytes)(tmp1mb.encode()))
f.close()
2019 TCTF zer0lfsr
这题跟上一题差不多，也是先求三个lfsr，然后再联合获得结果，源码如下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
35from 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的长度给出来，也没有更多的信息，所以不能直接用相关攻击，但是我们可以仔细观察，虽然有掩码位数很长，但是只有两位是1，其他位都是0，所以我们可以先思考一下，next处理的部分，对他进行影响的，只是init中位数为1的部分，而且处理后的信息储存到了最低位，没有丢失，因此可以逆推回去获得原值，而其中combine的三个值因为输入为单位，所以实际上可以变换为1
2def combine(x1, x2, x3):
return (x1&x2) ^ (x2&x3) ^ (x3&x1)
因此结合一起的三个lfsr就可以轻易的分解为单个lfsr了，剩下的求解可以直接用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# -*- coding:utf8 -*-
from z3 import *
from Crypto.Util.number import long_to_bytes
import hashlib
def combine(x1, x2, x3):
return (x1 * x2) ^ (x2 * x3) ^ (x1 * x3)
def solve_3_lfsr(keystream, relevant_bit_indices, length, mask_length):
len_mask = (2 ** (mask_length + 1) - 1)
result_bits = map(long, "".join([bin(ord(c))[2:].zfill(8) for c in keystream]))
s = Solver()
x = BitVec('x', length) # z3中只有BitVec类型支持异或操作
y = BitVec('y', length) # BitVec表示无符号数
z = BitVec('z', length)
inits = [x, y, z]
for result in result_bits:
combs = []
new_inits = []
for index in range(3): # 无符号数的移位需要使用LShR，表示逻辑移位
relevant_bit1 = (inits[index] & (1 << relevant_bit_indices[index][0]))
bit1_value = LShR(relevant_bit1, relevant_bit_indices[index][0])
relevant_bit2 = inits[index] & (1 << relevant_bit_indices[index][1])
bit2_value = LShR(relevant_bit2, relevant_bit_indices[index][1])
single_lfsr_result = bit1_value ^ bit2_value
combs.append(single_lfsr_result)
new_init = ((inits[index] << 1) & len_mask) ^ single_lfsr_result
new_inits.append(new_init)
s.add(combine(combs[0], combs[1], combs[2]) == result) # 约束条件
inits = new_inits
s.check()
model = s.model()
x_res = int(str(model[x]))
y_res = int(str(model[y]))
z_res = int(str(model[z]))
return x_res, y_res, z_res
with codecs.open("keystream", 'rb', 'utf8') as input_file:
data = input_file.read()
mask1 = (47, 22)
mask2 = (47, 13)
mask3 = (47, 41)
keystream = data[:24]
x, y, z = solve_3_lfsr(data[:24], [mask1, mask2, mask3], 48, 48)
init1, init2, init3 = map(long_to_bytes, [x, y, z])
print "flag{" + hashlib.sha256(init1 + init2 + init3).hexdigest() + "}"
#flag{b527e2621131134ec22250cfbca75e8c9f5ae4f40370871fd55910927f66a1b4}
后记
看来还得继续拖着了……生成函数啥的没学懂，做题到后面地动山摇Orz