LFSR学习

2023-09-19

未分类

1k 词

——————施工中——————

遇到过，没有深入研究过，看到一篇博客深入分析CTF中的LFSR类题目（一）-安全客 - 安全资讯平台 (anquanke.com)，所以又来开了个新坑。

流密码

流密码一般逐字节或者逐比特处理信息。

一般来说

流密码的密钥长度会与明文的长度相同。
流密码的密钥派生自一个较短的密钥，派生算法通常为一个伪随机数生成算法。

LFSR

LFSR是FSR（反馈移位寄存器）的一种，另外还有NFSR（非线性反馈移位寄存器），可以用于为流密码生成密钥流。

原理部分：

初始状态：

反馈函数：

这里看到两种，一种是ctfwiki的加法型

，其中均在某个有限域中，序列为最后的输出序列。

另一种是博客以及见过的题里出现的异或型。

即求和改成求异或，取值为0,1，递推式不同，其余相同。

一点概念：对于一个n级LFSR来讲，其最大周期为，再后面的输出序列即为前位的循环

~~画外音：写了2节课的内容因为没保存丢失了，现在处于一个暴躁重写状态~~

解题思路：通过输出序列和反馈函数求解初始状态，而对反馈函数的理解是解题的核心。

以2018 CISCN 线上赛 oldstreamgame为例

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

分析代码逻辑：lfsr函数中，R与mask按位与运算获得i，i逐位异或得到lastbit，外部对R进行左移一位、右拼接lastbit的更新，tmp为输出序列。

那么，根据与运算和异或的性质可以获得反馈函数:

（下标表示高位，⊕表示异或，i自0取，下同）对于lastbit和R的关系，博客中没有进行详细推导，这里尝试给出。

定义序列为

根据反馈函数，有：

其中

当j>32时

当j<=32时

取i+1=32：

此时有

因为输出序列tmp已知，所有lastbit均为已知值，根据异或性质可以求得

接下来对i递减，即可求得全部R。

以下是出hgamemini时的解题脚本：

from Crypto.Util.number import *
output=['1001100000001010100011000010111010110110010101000000000010010011111110111111111010111100110110010101010000001100010011101110010111001011111110100010101101110100001110000011010001000010001100011111000101110001011101111111100111010110100110000000101001010000010100000111100101111101111110010110010110110101100100010110111111000001011111010111001001000100000110110001101101110111010000110100000101101100111011010010110011011110101000001100000101001111101001000110000111011111010111011110111001001100100011010111110010111011101011000111101110000111101100101111001100000010110000111010000000101010110110100110111001001110101010010110111100111000101101110110100101011000110111000110000011111011010010000101101010001010110010000111001010010100110011001011000010110001001111110110111101010001001010001100111110010100101100011100111101100111010100101011111001100110001110011011000101001111101010000011010101110111110010011100011011000111000111111001111000001100101011011101100111100110011111010011010101001011', '0010100011011110101100000111101011101100101110011000110110101000010000011101000110100110011110101010100101000011100110110111000011111100100011001101110001100001010101011111001010100011001111111101001101101100111011011011010111101101010000001111010101011011110111101110100011011001101101010011001110011000100010100111001001111110100010100010010100111000001110101111001011101011010010110000010011000010001011011111101100111010001111100110010101011011010010110001001101010010100010010011000011001010110111000110110001001110001000110011111100000010001000000001010001010101000110101001100001100011100001011110011000111001101101001010000001101110101011010110110111010111011110010010110000011011010100101110100010001001010110011010110001101001111100010110111011110101001010000110101111000010101000111011010010011111111011101000101001001011011010110111111100001101110111111110001110001000010100110001111100100011011011001110010011000101001100110010000100110001101000111000101100101010001011100010000100111000', '0000010001010010111001101110001100000111001000111101011011000110000011000001000111001011111101010001100011110001111010100010000110010001100000001001001001110100000101010111010110111000000010000110100011110000111100111111101110001101101100010000011001010101100110000111111100111101001000011101111011110001010001110111101101011100001000111110111011101111001101100100101101101000101011000100100101110111011101110110110011011111001111010111000100001111100111110111101111110011000001110001001101111001000111110101110110010000000011011011001110110001010100000011010100000100111101000010111111100111100010100111011111110000000101101010010101010000001111011101011111011111010010101000001010010101001001000100011110001000010000100111101110100110011100000001111001001000100010011111011101010001100110100010000001000101101000001101010011101001000010101001000100101100110111011101001000110000111101011110101101001010011100011001000000010110111001001010101100100001100011011011011010111110100011111101000001101110', '1100100111111110100000001011110000110000111010011110100101010010011011111011001001110101001001100100010001010000111101100000100011110111011100100111000001100101011111110000000111100011000111111001110001110000010001000000001001110011111000011000000001100101000101100011110010101111101110000010001000110101101110110110111010010111010011100010111111011101111111111000011000001100000001111000001001010000110001101111001000000011011111111110111101010111101101100000100010111000110001101110111111100011011101001101111100001100110101101110100110111011110001010111001110101011110110111001010111001001000011101100011010011010011000001010110010100100001101111010011000110001110000011010100110000100010110010110110100011001000011011011011010011100001001110000101001100000000001101001001010101101111100000001000010001101010000111101011010001110100101001011011001010111010000101000100110001110101101101100010111100010110011011011011100110101000101011101010000001100011000000001101000110100101001010111111100000010']
flag=''
for j in range(4):
    R = ''
    key=(output[j])[:32]
    temp=key
    for i in range(32):
        out = '?'+key[:31]
        ans=int(temp[-1-i])^int(out[-1])^int(out[-4])^int(out[-8])^int(out[-11])^int(out[-15])^int(out[-20])^int(out[-25])^int(out[-28])
        R += str(ans)
        key = str(ans) + key[:31]
    R = format(int(R[::-1],2),'x')
    flag+=R
print('VIDAR{'+flag+'}')

参考资料：

线性反馈移位寄存器 - LFSR - CTF Wiki (ctf-wiki.org)

深入分析CTF中的LFSR类题目（一）-安全客 - 安全资讯平台 (anquanke.com)