反馈移位寄存器

反馈移位寄存器

反馈移位寄存器（FSR）是流密码产生密钥流的一个重要组成部分。在 GF(2) 上的一个 n 级 FSR 通常由 n 个二元存储器和一个反馈函数组成。

线性反馈移位寄存器

如果这里的反馈函数是线性的，我们则将称为线性反馈移位寄存器（LFSR），反馈函数是寄存器中某些位的异或，这些位叫做抽头。此时该反馈函数可以表示为：

$f(a_1,a_2,...,a_n) = c_1a_1 \oplus c_2a_2 \oplus ... \oplus c_na_n$

其中 $c_i$ 为 0 或 1。

假如有一个 4 级的 LFSR，其初始状态为：

$(a_1,a_2,a_3,a_4) = (1,1,1,0)$

其反馈函数为：

$f(a_1,a_2,a_3,a_4) = a_1 \oplus a_4$

每移出一个数时，先按照反馈函数计算移入数，然后每个位均往右移一位，最右边的位被丢弃作为输出，最左边的位就是计算出的移入数。

如上面的 LFSR，第一个移入数是 $a_5 = a_1 \oplus a_4 = 1$，输出的第一个数就是 $a_1$，第二个移入数是 $a_6 = a_2 \oplus a_5 = 0$，输出的第二个数就是 $a_2$。依此类推，可以得到前 15 个输出序列为：1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1。

对于一个 n 级的 LFSR，其最大周期为 $2^n - 1$，即 n 级 LFSR 的输出序列在重复之前能够产生 $2^n - 1$ 位长的伪随机序列。不是 $2^n$ 是因为全 0 的状态将使 LFSR 无止境地输出 0 序列。当然只有特定反馈函数的 LFSR 才有最大周期，其生成多项式必须是本原多项式，多项式的阶为移位寄存器的级数。生成多项式是指抽头序列加 1 形成的多项式，本原多项式是指不能再分解因式的多项式。

如上面的 4 级 LFSR，其生成多项式为：$x^4 + x + 1$，这是一个本原多项式，并且多项式的阶为 $2^4 -1 = 15$，因此其最大周期为 $2^4 - 1 = 15$，15 位之后的序列就是之前的重复。再如一个生成多项式：$x^4 + x^3 + x^2 + 1$，这是一个本原多项式，但多项式的阶为 5，因此不具有最大周期。

多项式进行因式分解及计算阶可以用 sage：

var('x')
f = x^4 + x^3 + x^2 + x + 1
f.factor()

n = 4
P.<x>=GF(2^n,modulus=[1, 1, 1, 1, 1])  # 低次到高次的系数，多项式必须不可分解
print P.modulus()
print x.multiplicative_order()

有的 LFSR 为了保护初始状态不泄露，输出时会直接丢弃最右位，输出改为本次的移入数。因此其输出的第一个数其实为正常输出的第 $n+1$ 个数，这样就保护了 LFSR 的 $n$ 位初始状态。

例子

2018 CISCN 线上赛 oldstreamgame

flag = 'flag{aabbccdd}'
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', 'wb')
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).encode('l1'))
f.close()

分析可知：

• flag 为初始状态为 32 位。
• 此 LFSR 为输出移入数的 LFSR，知道输出序列的前 800 位，相当于知道 $a_{33}$ 至 $a_{833}$，求的是 $a_1$ 至 $a_{32}$。
• mask 第 1、3、6、13、21、25、28、30 位为 1，其余位均为 0。mask 与 R 做按位与运算，当且仅当 R 的第 1、3、6、13、21、25、28、30 为 1 时， i 才会出现 1。lastbit 为 i 各位异或的结果。

因此可以得出此 LFSR 的反馈函数为：

$a_1 \oplus a_3 \oplus a_6 \oplus a_{13} \oplus a_{21} \oplus a_{25} \oplus a_{28} \oplus a_{30}$

其不具有最大周期。如果输出序列够多，也许会重复，直接得出初始状态。但 800 个输出序列中没有重复。

由反馈函数可知，当移入第 64 位时：

$a_{64} = a_{32} \oplus a_{34} \oplus a_{37} \oplus a_{44} \oplus a_{52} \oplus a_{56} \oplus a_{59} \oplus a_{61}$

即：

$a_{32} = a_{64} \oplus a_{34} \oplus a_{37} \oplus a_{44} \oplus a_{52} \oplus a_{56} \oplus a_{59} \oplus a_{61}$

可以算出初始状态的最后一位，以此类推，可以算出所有初始状态：

$a_{31} = a_{63} \oplus a_{33} \oplus a_{36} \oplus a_{43} \oplus a_{51} \oplus a_{55} \oplus a_{58} \oplus a_{60} \\ \vdots \\ a_{1} = a_{33} \oplus a_{3} \oplus a_{6} \oplus a_{13} \oplus a_{21} \oplus a_{25} \oplus a_{28} \oplus a_{30}$

由于此 LFSR 的抽头最小的一位是第 1 位，因此可以算出 $a_1$。如果抽头最小一位是第 3 位，那么就求不出 $a_1$、$a_2$，就需要爆破这两位了。

脚本为：

with open('key', 'rb') as f:
    data = f.read()
key = ''
for x in data:
    key += bin(x)[2:].zfill(8)

a = [-1 for _ in range(32)] + [int(x) for x in key[:32]]
for i in range(32):
    a[31-i] = a[63-i] ^ a[33-i] ^ a[36-i] ^ a[43-i] ^ a[51-i] ^ a[55-i] ^ a[58-i] ^ a[60-i]
res = ''.join([str(x) for x in a[:32]])
res = hex(int(res, 2))[2:]
print(res)

矩阵分析

但如果代码很复杂，不好分析出反馈函数，就可以使用矩阵分析的方法得出反馈函数了。

使用 $c_i$ 表示反馈多项式的系数（0 或 1），而且已知 $2n$ 位输出序列，用 $a_i$ 表示，则可以得出下面 $n$ 个式子：

$\left\{ \begin{array}{c} a_{n+1} = c_{1}a_{1} + c_{2}a_{2} + ... + c_{n}a_{n} \\ a_{n+2} = c_{1}a_{2} + c_{2}a_{3} + ... + c_{n}a_{n+1} \\ \vdots \\ a_{2n} = c_{1}a_{n} + c_{2}a_{n+1} + ... + c_{n}a_{2n-1} \\ \end{array} \right.$

上式中的加为模 2 加，即异或，下同。将上式写成矩阵的形式：

$\begin{pmatrix} a_{n+1} \\ a_{n+2} \\ \vdots \\ a_{2n} \end{pmatrix} = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ a_2 & a_3 & \cdots & a_{n+1} \\ \vdots & \vdots & \ddots & \vdots \\ a_n & a_{n+1} & \cdots & a_{2n-1} \\ \end{pmatrix} \times \begin{pmatrix} c_{1} \\ c_{2} \\ \vdots \\ c_{n} \end{pmatrix} = A \begin{pmatrix} c_{1} \\ c_{2} \\ \vdots \\ c_{n} \end{pmatrix}$

如果矩阵 A 可逆，那么可解出 $c_i$：

$\begin{pmatrix} c_{1} \\ c_{2} \\ \vdots \\ c_{n} \end{pmatrix} = A^{-1} \begin{pmatrix} a_{n+1} \\ a_{n+2} \\ \vdots \\ a_{2n} \end{pmatrix}$

例子中知道 $2n$ 位输出序列，因此可以用矩阵分析。sage 脚本为：

with open('key', 'rb') as f:
    data = f.read()
key = ''
for x in data:
    key += bin(ord(x))[2:].zfill(8)

n = 32
array_1 = []
for i in range(n):
    for j in range(n):
        array_1.append(int(key[i+j]))
A = matrix(GF(2), n, n, array_1)

array_2 = []
for i in range(n):
    array_2.append(int(key[n+i]))
B = matrix(GF(2), n, 1, array_2)

c = A.solve_right(B)
for x in c:
    print x[0]

可以得到 $c_i$，即反馈函数。

非线性反馈移位寄存器

LFSR 安全性很低，因此使用非线性的反馈函数的反馈移位寄存器叫做非线性反馈移位寄存器 NLFSR。常见的 NLFSR 有：Geffe 发生器、J-K 触发器、Pless 生成器、钟控序列生成器、门限发生器等。

这里介绍 Geffe 发生器。

Geffe 发生器使用了 3 个 LFSR，以非线性方式组合而成。

3 个 LFSR 的输出分别为 $a_1$、$a_2$、$a_3$，那么 Geffe 发生器的输出为：

$b = (a_1 \wedge a_2) \oplus (\urcorner{a_1} \wedge a_3) = (a_1 \wedge a_2) \oplus (a_1 \wedge a_3) \oplus a_3$

这个发生器看起来很好，实质上很弱，不能抵抗相关攻击。

例子

De1CTF 2020 NLFSR

from flag import a, b, c, d, flag
assert flag == "De1CTF{" + ''.join([hex(i)[2:] for i in [a, b, c, d]]) + "}"
assert [len(bin(i)[2:]) for i in [a, b, c, d]] == [19, 19, 13, 6]

ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31


def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)


def combine():
    global a, b, c, d
    a = lfsr(a, ma)
    b = lfsr(b, mb)
    c = lfsr(c, mc)
    d = lfsr(d, md)
    [ao, bo, co, do] = [i & 1 for i in [a, b, c, d]]
    return (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do


def genkey(nb):
    s = ''
    for i in range(nb*8):
        s += str(combine())
    open("data", "w+").write(s)


genkey(128*1024)

仔细分析后就能发现：

• 4 个 LFSR 分别为 19、19、13、6 位，a、b、c、d 分别为四个 LFSR 的初始状态。

• 每个 LFSR 逻辑也很简单，反馈函数就是 mask 中有 1 的各位异或。各个 LFSR 是输出移入数的 LFSR。

• 此 NLFSR 的输出是把 4个 LFSR 的输出进行一定的运算得到的。

先来分析以下相关性：

import itertools

n_a, n_b, n_c, n_d = 0, 0, 0, 0
for x in itertools.product([0, 1], repeat=4):
    ao, bo, co, do = x
    res = (ao * bo) ^ (bo * co) ^ (bo * do) ^ co ^ do
    if ao == res:
        n_a += 1
    if bo == res:
        n_b += 1
    if co == res:
        n_c += 1
    if do == res:
        n_d += 1
print('ao: ', n_a / 16)
print('bo: ', n_b / 16)
print('co: ', n_c / 16)
print('do: ', n_d / 16)

可以发现，有 75% 的概率 ao 的值与此 NLFSR 的输出相同。并且第一个 LFSR 只有 19 位，因此可以爆破 a。为了增快速度，可以先尝试 data 的前 100 个，如果有多个结果，再增大数量进行筛选，数量越多实际概率就会越接近理论概率。

def lfsr(r, m):
    return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)


def bruteforce_a():
    for a in range(2**18, 2**19):
        tmp_a = a
        count = 0
        for n in data:
            tmp_a = lfsr(tmp_a, ma)
            if tmp_a & 1 == int(n):
                count += 1
        if 0.7 < count / len(data) < 0.8:
            print(a, count / len(data))


ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31

data = open('data', 'r').read()[:100]
bruteforce_a()

得到 a = 363445。

然后发现，有 75% 的概率 NLFSR 的输出与 ao、bo 的与值相同，也有 75% 的概率与 ao、bo 的同或值相同。

def bruteforce_b():
    for b in range(2**18, 2**19):
        tmp_a, tmp_b = a, b
        count = 0
        for n in data:
            tmp_a = lfsr(tmp_a, ma)
            tmp_b = lfsr(tmp_b, mb)
            if (tmp_a & 1) & (tmp_b & 1) == int(n):
                count += 1
        if 0.7 < count / len(data) < 0.8:
            print(b, count / len(data))


a = 363445
data = open('data', 'r').read()[:100]
bruteforce_b()

得到 b = 494934。

然后可以直接爆破 c 和 d。

def bruteforce_c_d():
    for c in range(2**12, 2**13):
        for d in range(2**5, 2**6):
            tmp_a, tmp_b, tmp_c, tmp_d = a, b, c, d
            is_get = True
            for n in data:
                tmp_a = lfsr(tmp_a, ma)
                tmp_b = lfsr(tmp_b, mb)
                tmp_c = lfsr(tmp_c, mc)
                tmp_d = lfsr(tmp_d, md)
                ao, bo, co, do = [i & 1 for i in [tmp_a, tmp_b, tmp_c, tmp_d]]
                if (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do != int(n):
                    is_get = False
                    break
            if is_get:
                print(c, d)


a = 363445
b = 494934
data = open('data', 'r').read()
bruteforce_c_d()

可以得到 c = 4406，d = 63。