介绍了一些流密码的相关概念、经典算法及其攻击方法。

一维拼图？

流密码一般逐 bit/byte 处理信息。一般来说

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

伪随机数生成器 (PRNG)

用来生成接近于绝对随机数序列的数字序列的算法，电子计算机本身只能产生伪随机序列。

一般来说，PRNG 会依赖于一个初始值 seed 来生成对应的伪随机数序列。只要 seed 确定了，PRNG 所生成的随机数就是完全确定的，因此其生成的随机数序列并不是真正随机的，且序列具有周期性。

随机性的严格性

类别	随机性	不可预测性	不可重现性
弱伪随机数	✅	❌	❌
强伪随机数	✅	✅	❌
真随机数	✅	✅	✅

一般来说，密码学中使用的随机数是第二种。

随机序列：不能可靠重复产生、概率服从均匀分布（产生每个比特概率为1/2，任意两个比特统计上相互独立）。给定两个串判断是否随机，只能通过产生其的方法去判断。

问题

通常来说，伪随机数生成器可能会有以下问题：

随机数序列周期偶尔会比较小。
连续值之间关联密切，可以反推。
输出序列的值的大小很不均匀。

密码学安全伪随机数生成器 (CSPRNG)

一般而言，CSPRNG 的要求可以分为两类：

通过统计随机性测试。CSPRNG 必须通过 next-bit test，也就是说，知道了一个序列的前 k 个比特，攻击者不可能在多项式时间内以大于 50% 的概率预测出来下一个比特位。这里特别提及一点，姚期智曾在 1982 年证明，如果一个生成器可以通过 next-bit test，那么它也可以通过所有其他的多项式时间统计测试。
必须能够抵抗足够强的攻击，比如当生成器的部分初始状态或者运行时的状态被攻击者获知时，攻击者仍然不能够获取泄漏状态之前的生成的随机数。

反馈移位寄存器 (FSR)

一般的，一个 n 级反馈移位寄存器如下图所示：

fsr

$a_0,\ a_1,\ …,\ a_{n-1}$ 为初态
F 为反馈函数或者反馈逻辑。如果 F 为线性函数，那么我们称其为线性反馈移位寄存器（LFSR），否则我们称其为非线性反馈移位寄存器（NFSR）。

若这里的 F 是在 GF(2) 上的线性反馈函数，则可如此表示：(其中 $C_i$ 为 0 or 1)

$F(a_0,\ a_1,\ …,\ a_{n-1})=c_{n-1} a_0\oplus c_{n-2} a_1\oplus ··· \ \oplus c_0 a_{n-1}$
$a_{i+n} = F(a_i,\ a_i+1,\ …,\ a_{i+n-1})$

一般来说，反馈移位寄存器都会定义在某个有限域上，从而避免数字太大和太小的问题。

线性反馈移位寄存器 (LFSR)

LFSR 的反馈函数一般如下：$a_{i+n}=\sum\limits_{j=1}^{n}c_ja_{i+n-j}$

对于一个 n 级的 LFSR 来讲，其最大周期为2^n-1

多数情况下，考察方式可以概括为：给出反馈函数和输出序列，要求我们反推出初始状态。另外大多数情况下，初始状态的长度我们也是已知的。

例题

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

可以推出每一次的 out，也即 lastbit of (R&mask)，mask已知，则可表达为：

$lastbit = R_3\oplus R_5 \oplus R_8\oplus R_{12} \oplus R_{20} \oplus R_{27} \oplus R_{30} \oplus R_{32}$

则知道前 31 个 lastbit 后，现在的 R 由原R_1 与 lastbit_(1~31) 组成，又知道 lastbit_32，则可推出原R_1。由此反推，可推出原R。

import binascii
mask = 0b10100100000010000000100010010100
key = 0x20fdeef8
flag = 0
mul = 1
NBITS = 32
for i in range(NBITS):
    aim = key & 1
    key >>= 1
    i = (key & mask) & 0xffffffff
    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    key |= (aim ^ lastbit) << (NBITS - 1)
    flag += (aim ^ lastbit) * mul
    mul <<= 1
    print(flag)
print('flag{' + hex(flag)[2:] + '}')

快速相关攻击

参见深入分析CTF中的LFSR类题目（二）。

2n 序列已知，如何获取抽头序列和初始序列？

其中 ${s_i},{a_i}$ 分别为密文序列与抽头序列。

例如构造如上 n*n 的矩阵和 1*n 的抽头序列，然后带入 2n 序列求解。

拿到抽头序列后，用对单个 lfsr 的方法去还原初始序列。
B-M 算法

B-M algorithm

见 Post - Algorithm 相关。

线性同余生成器(LCG)

\[N_{i+1}\equiv AN_i+B\ (mod\ M)\]

LCG 根据以上递归公式生成，其中 A, B, M 是设定常数。

LCG 的周期最大为 M，但大部分情况都会少于 M。要使 LCG 达到最大周期，应符合以下条件：

B, M 互质；
M 的所有质因数都能整除 A-1；
若 M 是 4 的倍数，A-1 也是；
A, B, N[0] 都比 M 小；
A, B 是正整数。

详见 https://zeroyu.xyz/2018/11/02/Cracking-LCG/，写的不错。（其中介绍了四种攻击情况）

例题

nctf 2019 LCG，Writeup

MT19937 (梅森旋转算法)

之所以叫做是梅森旋转算法，是因为它的最大循环节是 2 ^ 19937 - 1，也即梅森素数。

used in rand() in Ruby, random module in Python and mt_rand() in PHP.

如果知道某一轮 twist 中任意的 state[i], state[i + 1]，那么可以得到 state[(i + 397) % 624]。

若知道任意的连续 624 个 state，那无敌了。

Mersenne Twister 最常见的实现方式使用 624 个 32 bits 的初始状态。这些整数按顺序分发 (分发前对每个初始数进行转换)，分发完后对该状态应用某种算法以获取下一组 624 个整数。

但这样的伪随机数生成器是有问题的，详见用2个随机值破解PHP的MT_RAND函数

以及可以通过得到连续的 624 个输出，还原出原来的 624 个 states，再根据原算法推算出接下来每个 state 下一次的 value，从而算出接下来的输出。

32 bits - MT19937 python code:

def _int32(x):
    return int(0xFFFFFFFF & x)
  
class MT19937:
    # 根据seed初始化624的state
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
  
    # 提取伪随机数
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)
  
    # 对状态进行旋转
    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
  
            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

参考：坏猴子的MT19937详解、30C3CTF2013 Guess

这里介绍一下如何由已知 state 推导出原来的 state（以 Python 3 为例）：

乱数生成过程如下，不再多说：

tmp = state
tmp ^= (tmp >> 11)
tmp ^= (tmp << 7) & 0x9d2c5680
tmp ^= (tmp << 15) & 0xefc60000
tmp ^= (tmp >> 18)
return tmp

由 old_state 生成 new_state 的过程如下：

y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff);
nx = y >> 1
if (y & 1) == 1:
  nx ^= 0x9908b0df
nx ^= state[(i + 397) % 624]
new_state[i] = nx

不难发现 MSB of (nx ^ state[(i + 397) % 624]) 和 LSB of y 保持一致。

所以若已知 new_state[i], old_state[(i + 397) % 624]，我们就能推导出 MSB of old_state[i] and old_state[i] without MSB。

如此一来就可以先利用 new_state[i], old_state[(i + 397) % 624] 推出 MSB of old_state[i]，再利用 new_state[i - 1], old_state[(i - 1 + 397) % 624] 推出剩余部分。

Tips：state[0] 之所以能推出来，是因为 seed 在产生 state 之前已进行了一轮转换。

显然，__init__ 可逆；而不管是生成乱数的过程 extract_number 还是每 624 组为一轮的 twist，都是线性的，故可以将生成随机数的过程看作是位与位之间的线性变换（单个位的影响）。也即，我们可以将其看作 $GF(2^n)$ 上，$X·T=Y$ 的矩阵运算。其中 $X$ 与 $Y$ 为 1xn 的向量，$T$ 则为 nxn 的矩阵。（同组之中，n 应当为 32 的倍数；不同组之间应为 624 * 32 的倍数）

2020 pwnhub公开赛 CoinFlip2

import random
count = 0
while True:
    print("Progress: %s/50" % count)
    coin = random.getrandbits(1)
    if int(input("Your guess: ")) == coin:
        print("Correct!")
        count += 1
        if count == 50:
            print(open("flag").read())
            exit()
    else:
        print("Wrong!")
        count = 0

以上代码对每个 32bits 输出截取其 MSB。如果我们能够拿到这样的 32 * 624 个输出，并得到其线性变换所对应的满秩矩阵 T，那么我们就能还原出 32 * 624bits 输入。

由于我们想要预测接下来的状态，故我们最好能够得到连续的 624 个 states。所以在 states to outputs 为线性变换的前提下（无论 state 实际上是什么，只要输入输出的位置保持不变，变换矩阵 T 都是固定的），我们可以进行黑盒测试：即设置 X = [1, 0, 0, 0, …, 0, 0] 得到 Y，此时 Y 就是 T 的第 1 行；由此类推，重复 32 * 624 次得到整个 T；然后根据远端的 Y 还原出 states。

但由坏猴子测试，发现这样得到的 T 并不是满秩的，求解出来的 states[0] 总是不正确的，但我们可以由 state[1 ~ 623] 还原出 state[0]，进而达成目标。

Xorshift

似乎有简单的操作方法，但👴懒得写了

关于 y = x ^ x >>/<< a & MASK 的攻击方法：

对于每一次操作，都必定有 BIT(y, i) = BIT(x, i) for which i = hibits(a)/lobits(a)。故可以通过每次得到 a bits 部分的相邻 a bits 来还原出整个 x。

def getbits(x, st, size):
    return (x >> st) & ((1 << size) - 1)

def re_lxorshift(y, shift, mask = 0xffffffff, xbits = 32):
    # get x s.t. y = x ^ ((x << shift) & mask)
    for i in range(shift, xbits, shift):
        y ^= (getbits(y, i - shift, shift) & getbits(mask, i, shift)) << i
    return y & ((1 << xbits) - 1)

def re_rxorshift(y, shift, mask = 0xffffffff, xbits = 32):
    # get x s.t. y = x ^ ((x >> shift) & mask)
    y <<= shift
    mask <<= shift
    xbits += shift
    for i in range(xbits - 2 * shift, -1, -shift):
        y ^= (getbits(y, i + shift, shift) & getbits(mask, i, shift)) << i
    xbits -= shift
    y >>= shift
    return y & ((1 << xbits) - 1)

类多项式乘法

def calc(m,p):
    res = 0
    lens = len(hex(p)[2:])
    for i in bin(m)[2:]:
        res*=2
        res^=m if i=='1' else 0
        res^=p if len(hex(res)[2:]) == lens else 0
    return res

若把以上这段代码看作 GF<2> 下的多项式乘法，p 为（多项式）模数，那么这段代码描述的就是在模域 p 下，多项式 m 在 GF<2> 上进行平方的计算。

这样的加密，如果给出 calc(m, p) 要求 m, 那么相当于求一个平方根。最粗暴的方法是用给出的 calc(m, p) 继续进行平方，在一个周期后必定能找到其平方根。

不过我仍对其的多解性和优雅程度保持怀疑态度。

RC4

简介

RC4 是一种密钥长度可变的加密算法。加、解密使用相同密钥，逐字节加密。突出优点是容易实现。现在已被列为不安全的加密算法。

加密流程

初始化 S 和 T 数组，
初始化置换 S 。（这两个过程被称为 KSA，密钥调度算法）
生成密钥流并加/解密。（PRGA，伪随机数生成算法）

KSA

for i in range(256):
    S[i] = i
    T[i] = Key[i % keylen]

j = 0
for i in range(256):
    j = (j + S[i] + T[i]) % 256
    swap(S[i], S[j])

PRGA

res = []
i = j = 0
for c in plain:
    i = (i + 1) % 256
    j = (j + S[i]) % 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) % 256
    res.append(chr(ord(c)^S[t]))

流密码算法介绍