MT19937

CRYPTO · 知识域。梅森旋转算法(Python random / PHP mt_rand)攻击。标签:随机数恢复、随机数预测。

触发特征

  • Python random.*、numpy.random、PHP mt_rand、Ruby Random;输出足够多(624 个 32 位整数即可完整恢复)。
  • 提示"预测下一个随机数/token/验证码"。

随机数恢复(核心套路)

  • untamper:MT 输出经过 tamper(temp_y = y;y ^= y>>11;y ^= (y<<7)&0x9d2c5680;y ^= y<<15;y ^= y>>18),逆运算还原 32 位状态字;624 个连续输出 → 完整状态 → 用 random.setstate 克隆。
  • randcrack 库:喂 624 个 getrandbits(32) 后自动续预测;分次喂亦可。
  • 子集和种子恢复:种子空间小(时间戳)→ 枚举种子直接比对首输出。
  • 约束传播:输出不完整(部分位)时把 tamper 展成 GF(2) 线性约束用 Z3 求状态(2017+ 常用)。

随机数预测

  • 恢复状态后:验证码、token、洗牌结果(random.shuffle)、randint 边界(拒绝采样过程需复现)全部可预测。
  • random.choice/shuffle 的内部调用次序要按实现精确复现。

变体攻击

  • float 输出恢复:random.random() 只有 53 位且实为两个状态字拼接;GF(2) 魔法矩阵从 ~3360 个 float 恢复全状态(not_random 库,PHD CTF Quals 2012)→ 预测重置 token/session/CSRF。
  • time 种子:服务器重启/已知部署时间窗枚举种子(秒级 2^26 可行);配合 format-string 全局变量写偏移种子(2018)。
  • NTP 投毒:时钟偏移导致种子可偏移枚举,UUID 异或恢复状态(2018)。
  • PHP mt_rand:strtoke 状态 31 字从输出恢复(phpmta 系列);mt_srand(time()) 种子枚举。
  • V8 Math.random:XorShift128+ 非 MT,但同属"输出恢复状态"套路,Z3 QF_BV 求解,d0nutptr/v8_rand_buster(→ Web-暴力破解)。
  • logistic map 混沌 PRNG:高精度小数种子暴力(BYPASS CTF 2025)。

工具速查

from randcrack import RandCrack
rc = RandCrack()
for _ in range(624): rc.submit(random.getrandbits(32))
rc.predict_getrandbits(32)   # 之后任意预测

转向

  • 种子/状态来自更弱生成器 → LCG;预测目标为签名 nonce → DSA

例题

untemper 手写完整恢复

逆 tamper 还原 624 个状态字,克隆生成器:

def untemper(y):
    y ^= y >> 18
    y ^= (y << 15) & 0xefc60000
    for _ in range(7):
        y ^= (y << 7) & 0x9d2c5680
    y ^= y >> 11
    y ^= y >> 22
    return y

state = [untemper(o) for o in outputs]      # outputs: 624 个连续 32 位输出
random.setstate((3, tuple(state) + (624,), None))
random.random()                              # 之后任意预测

63 位输出(randrange)的符号化恢复

64 位平台上 randrange(sys.maxsize) 用 getrandbits(63),每个输出消耗两个状态字且丢 1 位——手工逆不动,用 Z3 符号化 tamper:

from z3 import *
def symbolic_temper(y):
    y = y ^ LShR(y, 11)
    y = y ^ ((y << 7) & 0x9d2c5680)
    y = y ^ ((y << 15) & 0xefc60000)
    y = y ^ LShR(y, 18)
    return y

mt = [BitVec(f'mt_{i}', 32) for i in range(624)]
s = Solver()
for i, out63 in enumerate(outputs):
    if 2*i + 1 >= 624: break
    y1, y2 = symbolic_temper(mt[2*i]), symbolic_temper(mt[2*i+1])
    s.add(Concat(Extract(31, 0, y1), Extract(31, 1, y2)) == out63)
s.check()
state = [s.model()[mt[i]].as_long() for i in range(624)]

应用面:session token/CAPTCHA/洗牌结果预测(→ 随机数预测节)。

评论