MT19937 截断输出 GF(2) 线性恢复:624×19968 状态矩阵、6 维零空间枚举与 shuffle 逆置换
ctf/crypto · verified
一句话结论
Python random 的每个输出位都是 19968 位初始状态的 GF(2) 线性函数;即使只拿到 getrandbits(16) 的高 15 位或高 8 位,也能对 19968 个基状态各跑一遍同样的采样流程建立矩阵,解线性方程组恢复 MT19937 状态;加入状态位固定约束后矩阵仍秩亏 6 维时枚举 64 个候选,再用后续 shuffle 的逆置换筛出正确状态并还原明文。
原理
- Python
random是 MT19937,内部状态为 624 个 32-bit 字,共624*32=19968bit。tempering 只含 XOR 与移位,是 GF(2) 上的线性变换;getrandbits(16)返回 16 个输出位,>>1/>>8取高 15/8 位,仍然是状态位的线性组合。 - 题目给出的 gift 按 2 字节一块采样:每块先丢弃一个
getrandbits(8),再取一个getrandbits(16),第i块若i % 64 == 0取高 15 位,否则取高 8 位。把这些位按顺序拼起来就是观测向量R。 - 对 19968 个基状态分别
setstate并执行完全相同的采样流程,每一行就是“该基状态对观测位的贡献”,组成19968 × L的 GF(2) 矩阵M。真实初始状态s满足M*s = R。 - 用
solve_left得到一个特解;再求左零空间。原文实测观测矩阵秩为 19932(19968 个未知位,零空间 36 维);题目又加入 30 个“部分状态位固定为 0”的增广约束,把零空间压到 6 维,因此有2^6=64个候选状态,需要逐一回放验证。 - 对每个候选重新
setstate,先按题目代码消耗 3108 组(8+16)bit,再执行 2025 次shuffle,就得到打乱后的下标序列x。原程序用c[x.index(i)]生成密文,所以逆置换就是按x把字符还原。 - 正确候选会输出可读 flag;错误候选只产生乱码,以此完成筛选。
触发条件
- 目标使用 Python
random(MT19937)生成“礼物”输出,且这些输出被截断(只暴露getrandbits(k)的高位)。 - 同一个 RNG 状态随后被用于加密、洗牌等可验证操作;攻击者知道消耗次数、
shuffle次数与密文结构。 - 观测位数量足以建立线性系统(本题约 16 万位对应 19968 个未知状态位)。
- 可在本地复现
setstate/getrandbits/shuffle行为,并知道是否有额外的状态固定约束。
利用步骤
- 读源码确认采样格式:每次丢弃多少 bit、取多少位、每 64 次是否有分支。
- 把 gift 按位展开成观测向量
R;用同样的采样函数对每个基状态1 << i生成矩阵行。 - 在 GF(2) 上解
M*s = R,得到特解与左零空间;按题目约束(如部分状态位为 0)增广方程。 - 枚举零空间的所有组合(本题 64 个),把候选位串切成 624 个 32-bit 字并
setstate。 - 按源码回放:消耗固定数量的
getrandbits,执行已知次数的shuffle。 - 用逆置换还原密文;保留可打印/匹配 flag 格式的候选。
PoC
from sage.all import *
from random import Random
from Crypto.Util.number import long_to_bytes
def sample_bits(rng, n=19968):
out = []
for i in range(n):
rng.getrandbits(8)
v = rng.getrandbits(16)
if i % 64 == 0:
out += [(v >> 1 >> b) & 1 for b in range(14, -1, -1)]
else:
out += [(v >> 8 >> b) & 1 for b in range(7, -1, -1)]
return out
# 1) 观测位(由 gift 按同样的 2 字节分块展开)
R = vector(GF(2), observed_bits)
# 2) 每个基状态一行
rows = []
for i in range(19968):
st = [0] * 624
st[i // 32] = 1 << (i % 32)
rng = Random()
rng.setstate((3, tuple(st + [624]), None))
rows.append(sample_bits(rng))
M = Matrix(GF(2), rows)
# 3) 特解 + 零空间枚举
s = M.solve_left(R)
K = M.left_kernel().basis()
for mask in range(1 << len(K)):
cand = s + sum((K[j] for j in range(len(K)) if mask >> j & 1), vector(GF(2), [0] * 19968))
bits = ''.join(map(str, cand))
state = [int(bits[32 * j:32 * j + 32], 2) for j in range(624)]
rng = Random()
rng.setstate((3, tuple(state + [624]), None))
for _ in range(3108):
rng.getrandbits(8); rng.getrandbits(16)
x = list(range(len(ct)))
for _ in range(2025):
rng.shuffle(x)
pt = ''.join(ct[x.index(i)] for i in range(len(ct)))
if 'flag{' in pt:
print(pt)
说明:这是原文思路的最小骨架;observed_bits、ct 和增广约束需按题目数据替换。未在本机复跑原题附件。
变体与关联
- 完整 32-bit 输出:直接
untemper624 个输出即可,不需要线性系统;见 [[ctf-crypto-mt19937-bitstream-chinese-alignment-state-recovery]]。 - 截断/错位输出:用基向量建矩阵是通用方法;未知位数、位序(MSB/LSB)或丢弃次数会改变矩阵形状。
shuffle逆置换:x.index(i)与shuffle次数必须精确回放;少一次/多一次都会得到完全不同的置换。- 种子恢复:若状态由 32-bit 种子初始化,也可只枚举种子;本题状态维度过大,故走线性系统。
检测与防御
- 不要用
random生成任何密钥、令牌或可验证的随机序列;使用secrets/os.urandom或 CSPRNG。 - 若必须用
random,输出经密码学哈希(如 SHA-256)后再使用,避免输出位直接暴露状态线性关系。 - 检测:同一进程的随机输出与后续加密/洗牌存在可验证关联、输出位数被截断等特征。