Lfsr Notes

huangx607087学习lfsr的一些笔记

0.简介

本篇blog用在BUU上面刷的两道题来讲解lfsr.

1. 基本概念

LFSR,中文名称叫做线性反馈移位寄存器,由多个时钟存储元件和一个反馈路径组成。其中触发器的数量又称为

作用就是当给定前一个状态的输出的时候,这个输出状态会继续存入移位寄存器(同时最早的数据会被删除)。

S1

lfsr的基本Python实现代码如下(以下就是一个$24$位的lfsr):

1
2
3
4
5
6
7
8
9
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)

2.解决LFSR问题的方法

PART 1[24digs]

当lfsr的位数不超过$30$位时且知道mask的情况下,可以直接采用暴力枚举法爆破seed(又称key)比如2018强网杯streamgame1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25
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)
R=int(flag[5:-1],2)
mask=0x5311c
f=open("key","ab")
for i in range(12):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
f.write(chr(tmp))
f.close()

PART 2[32 digs]

在知道mask但不知道种子的情况下,我们可以用我们上面提到的式子进行移项,就可以求出之前被丢弃的一个比特位,进而不断迭代就可以得到后面的比特位,典型例题为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
flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14
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)
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的值,而flag则为lfsr的种子,长度为$32$位。虽然爆破也是可行的,但此处不使用爆破做法,二是递推求出lfsr的种子。

$32$位的lfsr,告诉了我们只需要知道输出的最开始的$32$个数字,我们就可以递推求出seed,代码如下:

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
from Crypto.Util.number import *
mask = 0b10100100000010000000100010010100
b = ''
N = 32
with open('key.txt', 'rb') as f:
b = f.read()
key = ''
print(bin(bytes_to_long(b)))
for i in range(N // 8):
t = b[i]
for j in range(7, -1, -1):
key += str(t >> j & 1)
print(key)
idx = 0
ans = ""
key = key[31] + key[:32]
while idx < 32:
tmp = 0
for i in range(32):
if mask >> i & 1:
tmp ^= int(key[31 - i])
ans = str(tmp) + ans
idx += 1
key = key[31] + str(tmp) + key[1:31]
num = int(ans, 2)
print (hex(num))

Update 2021.7.29 增加一个更简单易懂的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
def padbin(x,l=32):
s=bin(x)[2:]
if(len(s)<l):
s=(l-len(s))*'0'+s
return s
mask=padbin(0x80000057)
state=padbin(0x155a796b)
for i in range(32):
s=int(state[0])
#print(len(state),len(mask))
for j in range(31):
s^=int(mask[j])&int(state[j+1])
state=state+str(s&1)
state=state[1:]
print(hex(int(state,2))[2:])

PART 3[64 digs]

可以求出mask的,例题为**[AFCTF2018]Tiny LFSR**,64位是无法爆破的

详细内容请见文章21Jan2,发布时间为2021.1.21

PART 4[256 digs]

我们来看这样一道题目**[De1CTF2019]Babylfsr**

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
import hashlib
from secret import KEY,FLAG,MASK
assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')
LENGTH = 256
assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)
def pad(m):
pad_length = 8 - len(m)
return pad_length*'0'+m
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
if __name__=="__main__":
l = lfsr(KEY,MASK,LENGTH)
r = ''
for i in range(63):
b = 0
for j in range(8):
b = (b<<1)+l.next()
r += pad(bin(b)[2:])
with open('output','w') as f:
f.write(r)

题目给出了一个长度为$256$位的lfsr和长度为$504$位的输出结果,并告诉你KEY以及FLAG的一些特征(sha256后的值前$4$位是$1224_h$)。

CTF WIKI提到:如果我们知道了$2n$位输出结果,就可以把mask求出来,进而求出key,这个算法就是BM算法,其时间复杂度为$O(n^2)$,空间复杂度为$O(n)$,$n$为lfsr的比特位数,这道题是$256$。

S2

1

然后我们就可以得到mask的值,如下的矩阵运算

2

这个时候我们就求出了mask值,紧接着就是求key值了。

然后我们回到题目中:$256$位的lfsr,我们要知道$512$位才可以求出最后的结果,但目前我们只知道了$504$位,缺失$8$位,因此我们可以爆破最后$8$位,得到$256$个可能的mask值,然后我们再用这$256$个mask值恢复得到$256$个key值,根据题目给出的约束条件就可以确定最后的key值了。

上面讲的应该都算是比较详细的了,直接上一下sage的脚本,注意$\det=0$求逆矩阵会报错,因此要进行一次$\det!=0$的判断

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
def pad8(L,K):
C=[]
while K>0:
C=[K&1]+C
K>>=1
if(len(C)<8):
C=[0]*(8-len(C))+C
return L+C
def f(x):
num=0
for i in range(256):
num=num*2+x[i]
return num
def solve(mask,key):
idx,ans=0,''
key=[key[255]]+key[:256]
while idx<256:
tmp=0
for i in range(256):
if mask>>i&1:
tmp=(tmp+key[255-i])%2
ans=str(tmp)+ans
idx+=1
key=[key[255]]+[tmp]+key[1:255]
return int(ans,2)

#---------MAIN BELOW---------#
S=[0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0]
for i in range(256):
Scnt=pad8(S,i)
T=[]
for j in range(257):
T.append(Scnt[j:j+256])
X=matrix(GF(2),T[0:256])
B=matrix(GF(2),T[256])
if(det(X)!=0):
C=B*(X^-1)
D=matrix(ZZ,C)
print(hex(solve(f(D[0]),S[:256])))

只给出了所有可能的key值,最后筛选很简单的,脚本就不放了


Lfsr Notes
http://example.com/2021/01/27/Lfsr-Notes/
作者
huangx607087
发布于
2021年1月27日
许可协议