LFSR简介：

线性反馈移位寄存器（Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。线性反馈移位寄存器(LFSR)归属于移位寄存器(FSR)，除此之外还有非线性移位寄存器（NFSR）。

GF(2)上一个 n 级反馈移位寄存器由 n 个二元存储器与一个反馈函数 f(a1,a2,⋯,an)组成，如下图所示：

FSR

如果此处的反馈函数是线性的，我们就把它称为LFSR，此时该反馈函数可以表示为
$$
f(a_1,a_2,…,a_n)\ =\ c_na_1⊕c_{n-1}a_2⊕…c_1a_n
$$
其中c~i~ = 0 或 1，⊕表示异或

接下来，通过一个例子来更直观的确定LFSR的概念，假设给定一个5级的LFSR，其初始状态(即a~1~到a~5~各个寄存器的初始值)为：
$$
(a_1,a_2,a_3,a_4,a_5)\ =\ (1,0,0,1,1)
$$
其反馈函数为：
$$
f(a_1,a_2,a_3,a_4,a_5)\ =\ a_4⊕a_1
$$
整个过程可以表示为下图所示形式：
LFSR

$$
LFSR的输出序列{a_n}满足\left{
\begin{aligned}
a_{n+1}& =c_1a_n⊕c_2a_{n-1}⊕…⊕c_na_1\
a_{n+2}& =c_1a_{n+1}⊕c_2a_{n}⊕…⊕c_na_2\
.\
.\
.\
a_{n+i}& =c_1a_{n+i-1}⊕c_2a_{n+i-2}⊕…⊕c_na_i
\end{aligned}
\right.
$$

接下来，我们来计算该LFSR的输出序列，输出序列的前5位即为我们的初始状态10011，第6位的计算过程如下，
$$
a_6\ =\ a_4⊕a_1\ =\ 1⊕1\ =\ 0
$$
第7位的计算过程如下:
$$
a_7\ =\ a_5⊕a_2\ =\ 1⊕0\ =\ 1
$$
由此类推，可以得到前31位的计算结果如下：

1
1001101001000010101110110001111

此处可以借助代码辅助理解：

1
2
3
4
5
6
7
a = '10011'

for i in range(31-len(a)):
    a += str(int(a[i])^int(a[i+3]))
    
print(a)
#1001101001000010101110110001111

对于一个n级的LFSR来讲，其最大周期为2^n-1，因此对于我们上面的5级LFSR来讲，其最大周期为 2^5^-1=31，再后面的输出序列即为前31位的循环。

对于一个LFSR来讲，目前主要关心三个部分：初始状态、反馈函数和输出序列，那么对于CTF中考察LFSR的题目来讲也是如此，大多数情况下，我们在CTF中的考察方式都可以概括为：给出反馈函数和输出序列，要求我们反推出初始状态，初始状态即为我们需要的flag，另外大多数情况下，初始状态的长度我们也是已知的。

例题：

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

我们先分析一下已知条件：

已知初始状态的长度为4个十六进制数，即32位

已知反馈函数的代码形式，我们要提取出它的数学表达式

已知输出序列

那么我们的任务很明确，就是通过分析lfsr函数，整理成数学表达式的形式求解即可

接着我们就来逐行分析此函数

1
2
def lfsr(R,mask):
#接收两个参数，R是32位的初始状态(即flag)，mask是32位的掩码，由于mask已知，所以我们就直接把它当作常数
1
2
output = (R<<1) & 0xffffffff
#把R左移一位后低32位(即去除R的最高位，然后在R的最低位补0)的值赋给output
1
2
i = (R & mask) & 0xffffffff
#把传入的R和mask做按位与运算，运算结果取低32位，将该值赋给i变量
1
2
3
4
5
lastbit = 0
while i != 0:
    lastbit ^= (i&1)
    i = i>>1
#从i的最低位向i的最高位依次做异或运算，将运算结果赋给lastbit变量
1
2
output ^= lastbit
#将output变量的最后一位设置成lastbit变量的值
1
2
return (output,lastbit)
#返回output变量和lastbit变量的值，output即经过一轮lfsr之后的新序列，lastbit即经过一轮lfsr之后输出的一位

经过以上分析，我们发现lfsr函数本质上就是一个输入R,输出lastbit的函数

虽然我们已经清楚了R是如何经过一系列运算得到lastbit，但我们前面的反馈函数都是数学公式的形式，

我们怎么把他整理成一个表达式的形式呢？

mask只有第3、5、8、12、20、27、30、32这几位为1，其余位均为0。

mask与R做按位与运算得到i，当且仅当R的第3、5、8、12、20、27、30、32这几位中也出现1时，i中才可能出现1，否则i中将全为0。

lastbit是由i的最低位向i的最高位依次做异或运算得到的，在这个过程中，所有为0的位我们可以忽略不计（因为0异或任何数等于任何数本身，不影响最后运算结果），

因此lastbit的值仅取决于i中有多少个1：当i中有奇数个1时，lastbit等于1；当i中有偶数个1时，lastbit等于0。 当R的第3、5、8、12、20、27、30、32这几位依次异或结果为1时，即R中有奇数个1，因此将导致i中有奇数个1；当R的第3、5、8、12、20、27、30、32这几位依次异或结果为0时，即R中有偶数个1，因此将导致i中有偶数个1。

因此我们可以建立出联系：lastbit等于R的第3、5、8、12、20、27、30、32这几位依次异或的结果。

将其写成数学表达式的形式：
$$
lastbit\ =\ R_3⊕R_5⊕R_8⊕R_{12}⊕R_{20}⊕R_{27}⊕R_{30}⊕R_{32}
$$

显然，lastbit和R之间满足线性关系，那么接下来我们就可以开始求解了

我们想象：当即将输出第32位lastbit时，此时R已经左移了31位，根据上面的数学表达式，可以有

t0100384766078bfda8

我们可以求出R的第1位，同样的方法，我们可以求出R的第2位：

t01ef3d957b4726b14c

以此类推，R的全部32位我们都可以依次求出了，代码形式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mask = '10100100000010000000100010010100'
key = '00100000111111011110111011111000'

tmp=key

R = ''
for i in range(32):
    output = '?' + key[:31]
    ans = int(key2[-1-i])^int(output[-3])^int(output[-5])^int(output[-8])^int(output[-12])^int(output[-20])^int(output[-27])^int(output[-30])
    R += str(ans)
    key = str(ans) + key[:31]

R = format(int(R[::-1],2),'x')
flag = "flag{" + R + "}"
print(flag)

如下题目的分析方法同上：

2018 强网杯 线上赛 streamgame1

2018 强网杯 线上赛 streamgame2

2018 强网杯 线上赛 streamgame4

2018 HITB-XCTF 线上赛 streamgamex