FSR反馈移位寄存器常见攻击方法

发表于 | 分类于

反馈移位寄存器（Feedback Shift Register），指给定前一状态，经过反馈函数F得到下一个随机位，将前一个状态左移或者右移后拼接上得到的随机位，作为下一个状态，从而产生持续的随机位。每次运算前，一般先与Mask进行与操作，控制哪几位参与运算。

线性反馈移位寄存器（Linear Feedback Shift Register）

反馈函数为线性函数，其中异或运算是最常见的单比特线性函数。异或除了直接使用^运算，通过模2加的方式也能达到异或的效果。

1
2
3
while p:
  q = q + p & 1 #+ is prior to &, so means plus, then mod 2
  p = p >> 1

求初始状态

根据生成规则，初始状态最后一位拼接n-1个生成位，运算后得到第n个生成位，由于生成位已知，因此可以逆推初始状态最后一位。同理，逐位往前推，可得到全部的初始状态位。（sample：oldstreamgame，CISCN-2018）

求Mask

长度为n的LFSR，知道长度为2*n的序列，可以通过高斯消元法（Gauss-Elimination）求得Mask，进而预测接下来的生成位。（sample：Guess-game，网鼎杯-2020-朱雀组；babylfsr，de1ctf-2019）

由于与操作&可以看做模2乘，异或操作^可以看做模2加，因此可以看做，初始状态位组成的(n*1)矩阵与Mask位组成的(1*n)矩阵相乘得到第一个生成位。由2*n位的序列，可以组成(n*n)矩阵，从而通过高斯消元法求得Mask。

1
2
3
4
[a1, a2, ..., an]           mask1       an+1
[a2, a3, ..., an+1]         mask2       an+2
...
[an, an+1, ..., a2n-1]      maskn       a2n

知道长度为2*n的序列，也可以通过Berlekamp-Massey算法，构造一个级数尽可能小的LFSR。

非线性反馈移位寄存器

常见的有三种

  • 非线性组合生成器，对多个LFSR的输出使用一个非线性组合函数
  • 非线性滤波生成器，对一个LFSR的内容使用一个非线性组合函数
  • 钟控生成器，使用一个（或多个）LFSR 的输出来控制另一个（或多个）LFSR的时钟

求初始状态

单个LFSR的输出序列和combine之后的LFSR的输出序列之间的相关性大于0.53，可以使用Fast Correlation Attacks（快速相关攻击），当抽头（就是Mask里为1的位）数量较少（小于10）的时候，作用效果会比较明显。利用开普敦大学（university of cape town）于2011年发布的一个关于快速相关攻击的项目fastcorrattack。（sample：zer0lfsr，0ctf-2019；streamgame3，强网杯-2018）