介绍了一些流密码的相关概念、经典算法及其攻击方法。
一维拼图?
流密码一般逐 bit/byte 处理信息。一般来说
- 流密码的密钥长度会与明文的长度相同。
- 流密码的密钥派生自一个较短的密钥,派生算法通常为一个伪随机数生成算法。
伪随机数生成器 (PRNG)
用来生成接近于绝对随机数序列的数字序列的算法,电子计算机本身只能产生伪随机序列。
一般来说,PRNG 会依赖于一个初始值 seed 来生成对应的伪随机数序列。只要 seed 确定了,PRNG 所生成的随机数就是完全确定的,因此其生成的随机数序列并不是真正随机的,且序列具有周期性。
随机性的严格性
类别 | 随机性 | 不可预测性 | 不可重现性 |
---|---|---|---|
弱伪随机数 | ✅ | ❌ | ❌ |
强伪随机数 | ✅ | ✅ | ❌ |
真随机数 | ✅ | ✅ | ✅ |
一般来说,密码学中使用的随机数是第二种。
随机序列:不能可靠重复产生、概率服从均匀分布(产生每个比特概率为1/2,任意两个比特统计上相互独立)。给定两个串判断是否随机,只能通过产生其的方法去判断。
分类
目前通用的伪随机数生成器主要有
- 线性同余生成器,LCG
- 线性回归发生器
- Mersenne Twister
- xorshift generators
- WELL family of generators
- Linear feedback shift register,LFSR,线性反馈移位寄存器
问题
通常来说,伪随机数生成器可能会有以下问题:
- 随机数序列周期偶尔会比较小。
- 连续值之间关联密切,可以反推。
- 输出序列的值的大小很不均匀。
密码学安全伪随机数生成器 (CSPRNG)
一般而言,CSPRNG 的要求可以分为两类:
- 通过统计随机性测试。CSPRNG 必须通过 next-bit test,也就是说,知道了一个序列的前 k 个比特,攻击者不可能在多项式时间内以大于 50% 的概率预测出来下一个比特位。这里特别提及一点,姚期智曾在 1982 年证明,如果一个生成器可以通过 next-bit test,那么它也可以通过所有其他的多项式时间统计测试。
- 必须能够抵抗足够强的攻击,比如当生成器的部分初始状态或者运行时的状态被攻击者获知时,攻击者仍然不能够获取泄漏状态之前的生成的随机数。
反馈移位寄存器 (FSR)
一般的,一个 n 级反馈移位寄存器如下图所示:
-
$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:] + '}')
相关攻击
若有 NLFSR,其输出函数 Combine() 的结果 S_i 和其中某一个参数 X_i 的相关系数 $P_i \ge 0.6$(列真值表相等的比率),那么我们一般可以认为,X 对应的 LFSR_i 是能够被还原出的。
既然单个 X_i 与 S_i 的相关系数一定是 P_i(与 X 的产生方式完全无关),那么对整个序列而言,相关系数也应趋于 P_i。也就是说,对于既定的 S 序列(依托于正确的 X 序列) 和 正确的 X 序列,相关系数为 P_i。既然我们知道 S 和 X 的产生方式,那枚举 key 就完事。(已知 mask 求 key)
因为相关系数 P_i 偏离 0.5 较大,那么若有足够长的 NLFSR 流,输出就越满足相关系数,基本上不太可能有多解。
快速相关攻击
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]))