Lfsr Notes
huangx607087学习lfsr的一些笔记
0.简介
本篇blog用在BUU上面刷的两道题来讲解lfsr.
1. 基本概念
LFSR,中文名称叫做线性反馈移位寄存器,由多个时钟存储元件和一个反馈路径组成。其中触发器的数量又称为度。
作用就是当给定前一个状态的输出的时候,这个输出状态会继续存入移位寄存器(同时最早的数据会被删除)。
lfsr的基本Python实现代码如下(以下就是一个$24$位的lfsr):
1 |
|
2.解决LFSR问题的方法
PART 1[24digs]
当lfsr的位数不超过$30$位时且知道mask的情况下,可以直接采用暴力枚举法爆破seed(又称key)比如2018强网杯streamgame1
1 |
|
PART 2[32 digs]
在知道mask但不知道种子的情况下,我们可以用我们上面提到的式子进行移项,就可以求出之前被丢弃的一个比特位,进而不断迭代就可以得到后面的比特位,典型例题为2018 CISCN 初赛 oldstreamgame
看一下题目:
1 |
|
很显然,我们知道了mask的值,而flag则为lfsr的种子,长度为$32$位。虽然爆破也是可行的,但此处不使用爆破做法,二是递推求出lfsr的种子。
$32$位的lfsr,告诉了我们只需要知道输出的最开始的$32$个数字,我们就可以递推求出seed,代码如下:
1 |
|
Update 2021.7.29 增加一个更简单易懂的脚本
1 |
|
PART 3[64 digs]
可以求出mask的,例题为**[AFCTF2018]Tiny LFSR**,64位是无法爆破的
详细内容请见文章21Jan2,发布时间为2021.1.21
PART 4[256 digs]
我们来看这样一道题目**[De1CTF2019]Babylfsr**
1 |
|
题目给出了一个长度为$256$位的lfsr和长度为$504$位的输出结果,并告诉你KEY以及FLAG的一些特征(sha256后的值前$4$位是$1224_h$)。
CTF WIKI提到:如果我们知道了$2n$位输出结果,就可以把mask求出来,进而求出key,这个算法就是BM算法,其时间复杂度为$O(n^2)$,空间复杂度为$O(n)$,$n$为lfsr的比特位数,这道题是$256$。
然后我们就可以得到mask的值,如下的矩阵运算
这个时候我们就求出了mask值,紧接着就是求key值了。
然后我们回到题目中:$256$位的lfsr,我们要知道$512$位才可以求出最后的结果,但目前我们只知道了$504$位,缺失$8$位,因此我们可以爆破最后$8$位,得到$256$个可能的mask值,然后我们再用这$256$个mask值恢复得到$256$个key值,根据题目给出的约束条件就可以确定最后的key值了。
上面讲的应该都算是比较详细的了,直接上一下sage的脚本,注意$\det=0$求逆矩阵会报错,因此要进行一次$\det!=0$的判断
1 |
|
只给出了所有可能的key值,最后筛选很简单的,脚本就不放了