MT19937 位流状态恢复:中文位才消耗 bit 的错位修正与 getrandbits(50000) 预测
ctf/crypto · verified
一句话结论
题目用 random.getrandbits(50000) 生成位流,但只有明文中文字符才消耗 1 bit(bit=1 时码点 +9997,bit=0 不变,非中文不消耗);因此不能按“每个非标点字符”对齐,而要用已知明文段提取出 624×32=19968 个 bit、untemper 恢复 MT19937 状态、克隆 RNG 预测剩余 bit,再按“中文位”规则还原全文并计算 SHA-256。
原理
- 位流生成:
huge = random.getrandbits(50000);把huge按 32-bit 切块,每块format(v,'032b')拼成full_bit_stream(MSB-first),等价于把 MT19937 连续 32-bit 输出按位展开。 - 加密规则:遍历明文每个字符;只有“中文字符”(本题自定义范围
'一' <= ch <= '龥')才消耗 1 个 bit: - bit=0:字符不变;
- bit=1:字符码点
+9997; - 非中文:原样输出,不消耗 bit。
- 错位陷阱:若按“除逗号句号外的所有字符都消耗 bit”来对齐,遇到非中文(数字、英文、标点)时不会消耗 bit,但错误实现会消耗,导致从某处开始整体错位,后续全盘乱码、SHA-256 对不上。
- 状态恢复:Python
random是 MT19937,内部 624 个 32-bit 状态;拿到连续 624 个getrandbits(32)的 tempered 输出即可untemper还原状态。本题 19968 个 bit 正好对应 624 个 32-bit 输出。 - 预测:
random.Random().setstate((3, tuple(state + [624]), None))克隆状态;继续getrandbits(32)补齐剩余 bit;再按“中文位”规则解密全文。 - 验证:对还原明文计算
sha256,按题目格式LilacCTF{<sha256>}提交。
触发条件
- 题目给出密文与部分已知明文(或可猜的 flag 前缀/固定文本),加密逻辑是“按明文字符类型决定是否消耗 PRNG bit”。
- 明文以中文为主,非中文字符不消耗 bit;已知明文段包含足够多中文字符(≥19968 个 bit)。
- 程序使用 Python
random/MT19937 且输出未做额外混淆;位流按 32-bit MSB-first 拼接。 - 可离线运行 Python
random并setstate。
利用步骤
- 读程序逻辑,确认
getrandbits(50000)、32-bit 切块、format(v,'032b')的位序,以及“只有中文消耗 bit”的规则。 - 用已知明文与密文逐字符对齐:对每个中文字符,比较
ord(c)-ord(p):0→bit 0,9997→bit 1;非中文跳过、不消耗 bit。 - 收集
624*32=19968个 bit,按 32 位一组转成整数(MSB-first),得到 624 个 tempered 输出。 - 对每个输出
untemper(逆向y ^= y>>11、y ^= (y<<7)&0x9d2c5680、y ^= (y<<15)&0xefc60000、y ^= y>>18)得到状态。 rng.setstate((3, tuple(state + [624]), None)),继续生成剩余getrandbits(32),补齐 50000 bit。- 按“中文位”规则解密:对每个密文字符,若
chr(ord(c)-9997)是中文或c本身是中文,则消耗一个 bit;bit=1 取-9997,bit=0 保持原字符;非中文原样输出、不消耗。 - 计算
sha256(plain).hexdigest(),拼成 flag;若 hash 不匹配,检查中文范围/位序/对齐起点。
PoC
import hashlib, random
MASK32 = 0xFFFFFFFF
def unshift_right_xor(y, shift):
x = 0
for _ in range(0, 32, shift):
x = y ^ (x >> shift)
return x & MASK32
def unshift_left_xor_and(y, shift, mask):
x = 0
for _ in range(0, 32, shift):
x = y ^ ((x << shift) & mask)
return x & MASK32
def untemper(y):
y = unshift_right_xor(y, 18)
y = unshift_left_xor_and(y, 15, 0xefc60000)
y = unshift_left_xor_and(y, 7, 0x9d2c5680)
y = unshift_right_xor(y, 11)
return y & MASK32
def recover_state(outputs):
st = [untemper(v) for v in outputs[:624]]
rng = random.Random()
rng.setstate((3, tuple(st + [624]), None))
return rng
# 1) 从已知明文段提取中文位(示例:known_plain/ciphertext 已对齐)
bits = []
for p, c in zip(known_plain, ciphertext):
if '一' <= p <= '龥':
d = ord(c) - ord(p)
if d == 0: bits.append('0')
elif d == 9997: bits.append('1')
else: raise ValueError("alignment error")
words = [int("".join(bits[i:i+32]), 2) for i in range(0, 624*32, 32)]
rng = recover_state(words)
# 2) 补齐剩余 bit(50000 bit 共 1563 个 32-bit 块)
full = "".join(bits[:624*32]) + "".join(f"{rng.getrandbits(32):032b}"
for _ in range((50000 + 31)//32 - 624))
full = full[:50000]
# 3) 按中文位规则解密
out, bi = [], 0
for ch in ciphertext:
back = chr(ord(ch) - 9997) if ord(ch) >= 9997 else None
if back and '一' <= back <= '龥':
b = int(full[bi]); bi += 1
out.append(back if b else ch)
elif '一' <= ch <= '龥':
b = int(full[bi]); bi += 1
out.append(chr(ord(ch) - 9997) if b else ch)
else:
out.append(ch)
plain = "".join(out)
print("LilacCTF{" + hashlib.sha256(plain.encode()).hexdigest() + "}")
说明:PoC 按原文的 getrandbits(50000)/中文位规则重写;known_plain 需足够长(≥19968 个中文 bit)。未在本机对附件复跑。
变体与关联
- MT19937 其他恢复:
getrandbits(k)的非 32 位输出、randrange截断、shuffle等需要额外建模;见 [[crypto-prng-mt19937-untemper-state-recovery-predict]]。 - 位序:
format(v,'032b')是 MSB-first;若程序用int.to_bytes/LSB-first,需反转每组 32 位。 - 字符规则:中文范围可能不同(GB2312、Unicode 区间、正则
一-鿿);按程序实际判断。 - 偏移:
+9997可能换成其他常量;用已知明文差值确定。 - 关联:[[ctf-crypto-mt19937-buggy-randbelow-z3-shuffle]](MT19937 变体)、[[crypto-prng-mt19937-seed-recovery-lfsr-noise-batch-alignment]](位流对齐)。
检测与防御
- 不要用
random做密码学:Pythonrandom是 MT19937,可预测;密钥/令牌应使用secrets/os.urandom或 CSPRNG。 - 检测:大量结构化明文、按字符类型条件消耗随机数、固定位流拼接等特征;CTF 中属于 PRNG 预测题。
- 防御:加密前对 PRNG 输出做密码学哈希/HKDF,或直接使用流密码(ChaCha20)并保密 key/nonce。