LSFR入门
2023-7-5 16:32:0 Author: xz.aliyun.com(查看原文) 阅读量:4 收藏

前言:

LFSR(线性反馈移位寄存器)已经成为如今CTF中密码学方向题目的一个常见考点了,在今年上半年的一些国内赛和国际赛上,也出现了非常多的这类题目,对其的说明解释也有几位大佬已经做过详细说明,但始终网上针对这类考点的详细分析不多,因此接下来我将以更为简单的的介绍及分析带入门,后续将会附上大佬的链接,若有总结不到位请见谅。

LFSR简介:

LFSR是属于FSR(反馈移位寄存器)的一种,除了LFSR之外,还包括NFSR(非线性反馈移位寄存器)。反馈移位就是可以通过前面已经存在的寄存器中的值反馈出后面的的寄存器的值,通过不断移位对应不同的前寄存器值一直反馈出后面连续的后寄存器值。即类似于摸石过河的游戏,三块石头总量不变却能一直向前移动,你可以将石头看作是寄存器中的值,每次移动石头相当于进行一次位移操作,而你手中的石头则是通过反馈决定下一次移动的位置。

那么接下来正式带各位进入LFSR,由上文可知这是该一个不断反馈的过程,FSR是流密码产生密钥流的一个重要组成部分,在GF(2)上的一个n级FSR通常由n个二元存储器一个反馈函数组成,如下图所示:

在反馈移位寄存器(FSR)中,从第n项转移到第n+1项时,通过反馈函数将第1项的值反馈到第n+1项,从而实现循环的效果。在这个过程中,从第n项开始到第2项的所有存储器的位置都将进行改变,而最后一项的值会被反馈到第1项。

因此,通过从第n项指向第1项的箭头来表示反馈过程是为了更好地说明存储器值的位移和流动,以及整体循环的效果。在这个过程中,每个存储器的值会不断地被反馈并移动到下一个位置,最终回到第1项的位置,从而实现了循环。

请注意,实际上,反馈值不直接影响第一项存储器的值。第一项存储器的值是由初始状态或初始向量决定的,而不是通过反馈值计算得到的。箭头的指向并不意味着反馈值直接影响第一项存储器的值,而只是简单地展示存储器值的流动和位移过程。

因此,箭头从第n项指向第1项的表述方式在图解中是为了更好地说明存储器值的位移和流动方向,并不代表反馈值对第一项的直接影响。
如果这里的反馈函数是线性的,我们则将其称为LFSR,此时该反馈函数可以表示为,其中ci=0或1,⊕表示异或(模二加)。

我们接下来通过一个例子来更直观的明确LFSR的概念,假设给定一个5级的LFSR,其初始状态(即a1到a5这5个二元存储器的值)为:

其反馈函数为:

整个过程可以表示为下图所示的形式:

接下来我们来计算该LFSR的输出序列,输出序列的前5位即为我们的初始状态10011第6位的计算过程如下:

第7位的计算过程如下:

由此类推,可以得到前31位的计算结果如下:

1001101001000010101110110001111

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

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

显然,这个反推并不是一个容易的过程,尤其当反馈函数十分复杂的时候,接下来我们就通过一些比赛当中出现过的具体的CTF题目,来看一下在比赛当中我们应该如何解决这类问题,由于不同题目之间难度差异会很大,所以我们先从最简单的题目开始,同样如果有错误的地方请谅解,而我挑选的也是经典比赛题目,网络上有着详尽的wp,在此我将尽可能的用最通俗的语言和脚本来进行演示。

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

下面我将进行逐行分析该题代码:

flag = "flag{xxxxxxxxxxxxxxxx}"

assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14
#已知初始状态的长度为4个十六进制数,即32位,初始状态的值即我们要去求的flag,所以初步判断这里的级是32,那么最大周期就是2^32-1。
#那么我们的任务很明确,就是通过分析lfsr函数,整理成数学表达式的形式求解即可,接下来我们一行一行的来分析这个函数

```python
def lfsr(R,mask):
    #接受两个参数,R是我们的flag,mask是32位的掩码,本题中mask已知,作为常数

​    output = (R << 1) & 0xffffffff
​    #把R左移一位取低32位(即抹去R的最高位,然后在R的最低位补0)的值赋给output变量,最低位的0要补在反馈函数lastbit计算的值来造成循坏

​    i=(R&mask)&0xffffffff
​    #把传入的R和mask作按位与运算,运算结果取低32位,将该值赋给i变量,注意这里跟上面的output没有关系
​    #这个步骤会将 R 中与 mask 对应位上为 1 的位保留下来。

​    lastbit=0
​    #初始化变量 lastbit,用于存储异或的结果

​    while i!=0:
​        lastbit^=(i&1)
​        #将变量 i 的最右端位与 1 进行异或运算,并将结果存储到 lastbit 中。

​        i=i>>1
​        #将变量 i 右移一位,用于进行下一轮的判断。
​    #从i的最低位向i的最高位依次做异或运算,将运算结果赋给lastbit变量,最后补到output上

​    output^=lastbit
​    #将output变量的最后一位设置成lastbit变量的值,对应前面造成循环

​    return (output,lastbit)
​    #返回output变量和lastbit变量的值,output经过一段时间lstf之后输出的新序列,就是左移且补了一位反馈函数生成的lastbit后的值。

R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100
key='20FDEEF8A4C9F4083F331DA8238AE5ED083DF0CB0E7A83355696345DF44D7C186C1F459BCE135F1DB6C76775D5DCBAB7A783E48A203C19CA25C22F60AE62B37DE8E40578E3A7787EB429730D95C9E1944288EB3E2E747D8216A4785507A137B413CD690C'
#32位Key值:00100000111111011110111011111000,这里进行了转换

for i in range(100):
    tmp=0
    for j in range(8):

​        (R,out)=lfsr(R,mask)
​        #调用 lfsr 函数,并将 R 和 mask 作为参数传入。函数返回的结果是更新后的 R 和最右端位的值 out。

​        tmp=(tmp << 1)^out
​        #将 tmp 左移1位,并将 out(最右端位)与结果进行异或运算,将异或结果存储回 tmp。

print(chr(tmp))
#以上循环进行了改编,删去了对于文件读写编辑的过程
分析完毕后,我们可以看出在这道题的情境下,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。注意,这里的lastbit是一个数字,仅为1或0。

在代码中,lastbit 变量在循环中通过异或运算逐步计算得到,并最终用于更新output的最后一位。异或运算符^用于按位异或操作,当两个操作数的对应位不同时,结果为 1;当两个操作数的对应位相同时,结果为 0。在每次循环中,将i的最右端位与i进行异或运算,并将结果存储到lastbit 变量中。由于i 只能取整数值,每次对其进行右移操作后,最右端位的值只能是 1 或 0。因此,lastbit只能取 1 或 0。当lastbit 为 0 时,则表示当前的i的最右端位为 0;当lastbit为 1 时,则表示当前的i的最右端位为 1。根据lastbit的值,可以影响下一次迭代中output的最后一位是保持不变还是进行翻转。因此,lastbit 变量仅能取到 1 或 0,用于在 LFSR 的循环中标识当前的寄存器位状态,并根据其值来调整下一次迭代中的输出位。

当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这几位依次异或的结果。

将其写成数学表示式的形式,即为我们要求的**反馈函数**,反馈函数的形式也说明了初始位数要**32位**:

![](https://xzfile.aliyuncs.com/media/upload/picture/20230704130357-2e9aa30c-1a28-1.png)

那么对于明文key的输出,最后八行代码,对flag,它做了一百次循环,每次循环都产生一个结果,并将这个结果写到key里面去,所以key里面总共有一百个ASCII字符,共两百个16进制数。题目之所以会出现 100 个ASCII字符是因为 4 循环次加内嵌的 8 位一次共 32 位循环往后产生的 4 个flag生成的加密字符共 8 个 16 进制数后,继续用这 4 个加密后的 flag 字符继续新一轮加密,就是多层加密。所以我们取 32 位即可,结果 flag 也是 4 个ASCII字符拆分出的 8 个 16 进制数。

显然,lastbit和R之间满足线性关系,那么接下来我们就可以开始求解了,而且从这里我们可以知道,这种移位的CTF题目类型要反推32位的初始值要多少位输出序列呢,答案就是32位,因为这种移位的题目是32位为一个循环,这就和我们前面说的2^32-1的循环不太同了,因为这里是移位操作。

我们想象这样一个场景,当即将输出第32位lastbit时,此时R已经左移了31位,根据上面的数学表达式,我们有:



我们要明确我们是解题,需要的是逆过程,输出值output的不断左移导致右边不断补充由反馈函数生成的last bit。当右边补满31位last bit后,最左边的第32位就是原始标志(flag)的第1位。在这个过程中,由于反馈函数的计算是基于当前的R值,所以前31位的R值是已知的,可以利用这些已知位来计算出第32位的值。

这样我们就可以求出R的第1位,同样的方法,我们可以求出R的第2位:
!!
那么解题脚本就是:

```python
mask = 0b10100100000010000000100010010100
key1="00100000111111011110111011111000" 
#lastbit全部值,就是反馈函数生成的值,32位的key1

key2=key1
flag=[]

for i in range(32):
    output='?'+key1[:31]    
    #?0100000111111011110111011111000,因为后面有key1=str(lastbit)+key1[:31],key1不断填补,output不断取前31位,所以这里output每次把?定在第i位上,注意output和key1是独立的分开的。

    flag.append(str(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])))
#这里之所以取负数是因为我们截取是从左往右取,而在计算机中是小端顺序,应该从右往左取才对,这里的key2[-1-i]就是小端左到右的第i位,也就是前面分析的反馈函数生成值的第i位。
#flag值的原第i位,现在在第32位,可以通过⊕的可逆性来求,就是R32=lastbit ⊕ R3 ⊕ R5 ⊕ R8 ⊕ R12 ⊕ R20 ⊕ R27 ⊕ R30                                    

    key1=str(flag[i])+key1[:31]
    #不断填补key1,让key1向右推进

print("flag{"+hex(int(''.join(flag[::-1]),2)).replace('0x','')+"}")
#这里是经过一系列操作,首先把flag变成小端顺序的[::-1],然后就是转十六进制。

那么这便是LSFR的基础知识及入门,如有不对敬请指出。


文章来源: https://xz.aliyun.com/t/12663
如有侵权请联系:admin#unsafe.sh