MT19937 学习与攻击

mt19937学习

算法分析

MT19937的工作流程分为三个部分:

┌─────────────────────────────────────────────────────────┐
│ MT19937 工作流程 │
├─────────────────────────────────────────────────────────┤
│ 1. 初始化(Init) │
│ 输入:seed(种子) │
│ 输出:624个初始状态值(state[0..623]) │
│ │
│ 2. 状态旋转(Twist) │
│ 每使用624个随机数后执行一次 │
│ 将当前状态转换为下一组624个状态 │
│ │
│ 3. 提取随机数(Extract/Temper) │
│ 对状态进行一系列位运算,输出最终的随机数 │
│ 包括:右移11位、左移7位&mask、左移15位&mask、右移18位 │
└─────────────────────────────────────────────────────────┘

2.3 Python实现

def _int32(x):
return int(0xFFFFFFFF & x)

class MT19937:
# 初始化
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

2.3.1 伪代码



seed
│
▼
┌──────────┐
│ 初始化 │ init_genrand(seed)
│ 展开为 │ 或 init_by_array(seeds)
│ 624 状态 │
└────┬─────┘
│ index ← N (624)
▼
┌──────────────────────────────────────────────┐
│ │
│ extract_number() 被调用 │
│ │ │
│ ├── index >= N ? ──Yes──▶ twist() │
│ │ │ │
│ │ ├─ 用 state[i] │
│ │ │ 和 state[i+1] │
│ │ │ 和 state[i+397] │
│ │ │ 生成新 state │
│ │ │ │
│ │ └─ index ← 0 │
│ │ │
│ ▼ │
│ y ← state[index] │
│ index ← index + 1 │
│ │ │
│ ▼ │
│ temper(y): │
│ y ^= y >> 11 │
│ y ^= (y << 7) & 0x9D2C5680 │
│ y ^= (y << 15) & 0xEFC60000 │
│ y ^= y >> 18 │
│ │ │
│ ▼ │
│ return y ◀── 每 624 次循环一次 twist │
│ │
└──────────────────────────────────────────────┘

2.4 关键理解

由seed产生624个内部状态(mt[0])
一个内部状态(过extract_number函数后)对应的就是一个32位输出

内部状态用完后再过twist重新生成

攻击的核心思想:

  • 收集足够的输出 → 逆向恢复内部状态 → 预测未来输出
    收集需要一个完整的624输出,如果碰到twist那就恢复一个完整快之后再逆twist完整恢复

攻击思路

逆extract_number

原理

MT19937的extract_number函数对状态进行了一系列位运算(称为tempering):

y = y ^ (y >> 11)
y = y ^ ((y << 7) & 0x9D2C5680)
y = y ^ ((y << 15) & 0xEFC60000)
y = y ^ (y >> 18)

这些操作都是可逆的!我们可以编写untemper函数,从输出恢复原始状态。

位运算逆向分析:

每一步的动作都差不多,我们取一步分析:
y = y ^ ((y << shift) & mask)

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
"""逆向 y = y ^ ((y << shift) & mask)"""
tmp = res
for i in range(bits // shift):
tmp = res ^ (tmp << shift) & mask
return tmp

完整untemper

def untemper(y):
"""从MT19937的输出恢复原始状态"""
# 逆向 y = y ^ (y >> 18)
y = inverse_right_mask(y, 18)

# 逆向 y = y ^ ((y << 15) & 0xEFC60000)
y = inverse_left_mask(y, 15, 0xEFC60000)

# 逆向 y = y ^ ((y << 7) & 0x9D2C5680)
y = inverse_left_mask(y, 7, 0x9D2C5680)

# 逆向 y = y ^ (y >> 11)
y = inverse_right_mask(y, 11)

return y & 0xffffffff

# 验证
def test_untemper():
"""测试untemper是否正确"""
import random
rng = random.Random(12345)

# 获取一个随机数
output = rng.getrandbits(32)

# 用untemper恢复
recovered = untemper(output)

# 创建新的RNG,手动设置状态
rng2 = random.Random()
state = list(rng2.getstate()[1])
state[0] = recovered
rng2.setstate((2, tuple(state), None))

# 验证下一个随机数是否相同
# (注意:这里需要更完整的状态设置)
print(f"原始输出: {output}")
print(f"恢复状态: {recovered}")

test_untemper()

例题:[SUCTF2019]MT

4.4.1 题目代码
import random
import hashlib

# 生成大量随机数
with open('random_numbers.txt', 'w') as f:
for _ in range(1000):
f.write(str(random.getrandbits(32)) + '\n')

# 用下一个随机数生成flag
flag = "flag{" + hashlib.md5(str(random.getrandbits(32)).encode()).hexdigest() + "}"
print(flag)

从文件中读取前624个随机数,对每个随机数进行untemper,恢复内部状态再预测第1001个随机数就行

4.4.3 exp

import hashlib
import random

# ========== 步骤1:实现untemper ==========

def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ (tmp >> shift) & mask
return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ (tmp << shift) & mask
return tmp

def untemper(y):
"""从MT19937输出恢复原始状态"""
y = inverse_right_mask(y, 18)
y = inverse_left_mask(y, 15, 0xEFC60000)
y = inverse_left_mask(y, 7, 0x9D2C5680)
y = inverse_right_mask(y, 11)
return y & 0xffffffff

# ========== 步骤2:读取随机数并恢复状态 ==========

# 读取前624个随机数
with open('random_numbers.txt', 'r') as f:
outputs = [int(line.strip()) for line in f.readlines()[:624]]

print(f"[+] 已读取 {len(outputs)} 个随机数")

# 恢复内部状态
state = [untemper(y) for y in outputs]

# 注意:MT19937的状态格式需要调整
# Python的random模块状态格式:(version, state_tuple, gauss_next)
# state_tuple[0]必须是特定值,state_tuple[1:625]是624个状态

state_tuple = (3, ) + tuple(state) + (624, )

# ========== 步骤3:预测后续随机数 ==========

rng = random.Random()
rng.setstate((2, state_tuple, None))

# 跳过已经使用的624个随机数
for _ in range(624):
rng.getrandbits(32)

# 获取下一个随机数(用于生成flag的那个)
next_random = rng.getrandbits(32)
print(f"[+] 预测的随机数: {next_random}")

# ========== 步骤4:计算flag ==========

flag = "flag{" + hashlib.md5(str(next_random).encode()).hexdigest() + "}"
print(f"[+] Flag: {flag}")

逆向twist(向后恢复攻击)

原理

MT19937的twist操作会生成下一组624个状态。如果我们知道当前状态,可以通过逆向twist操作恢复上一组状态。

twist:

def twist(self):
for i in range(624):
y = _int32((self.mt[i] & 0x80000000) +
(self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = self.mt[(i + 397) % 624] ^ (y >> 1)
if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df

逆向思路:

  1. twist操作是线性的,可以用矩阵表示
  2. 在GF(2)上求解线性方程组
  3. 或者利用已知的624个输出,通过矩阵求逆恢复之前的状态

例题:

[V&N2020 公开赛]Backtrace

题目代码

import random
from Crypto.Util.number import bytes_to_long

flag = b"flag{xxxxxxxxxxxxxxxxxxxx}"

# 先跳过一些随机数
for _ in range(1000):
random.getrandbits(32)

# 用随机数异或加密flag
encrypted = bytes([b ^ random.getrandbits(8) for b in flag])

# 输出加密后的flag
print("encrypted_flag:", encrypted.hex())

# 再输出一些随机数
for _ in range(624):
print(random.getrandbits(32))

除了恢复内部状态之外多了一步逆twist

exp

import sys, re

M32 = 0xffffffff

def inv_right(y, s): # 逆 y ^= y >> s
x = y
for _ in range(32 // s + 1):
x = y ^ (x >> s)
return x & M32

def inv_left(y, s, m): # 逆 y ^= (y << s) & m
x = y
for _ in range(32 // s + 1):
x = y ^ ((x << s) & m)
return x & M32

def untemper(y): # 逆 temper(相反顺序撤销)
y = inv_right(y, 18)
y = inv_left(y, 15, 0xefc60000)
y = inv_left(y, 7, 0x9d2c5680)
y = inv_right(y, 11)
return y

def temper(y):
y ^= y >> 11
y ^= (y << 7) & 0x9d2c5680
y ^= (y << 15) & 0xefc60000
y ^= y >> 18
return y & M32

text = sys.stdin.read()
enc = bytes.fromhex(re.search(r'encrypted_flag:\s*([0-9a-fA-F]+)', text).group(1))
outs = [int(t) for t in re.findall(r'(?m)^\s*(\d+)\s*$', text)]
assert len(outs) == 624

n = len(enc) # flag 长度
s = 1000 + n # 第一条尾部输出的全局下标
k = 1248 - s # 尾部输出中属于状态 A1 的个数
assert 0 <= k, "flag too long"

x = [untemper(v) for v in outs]
C = x[k:] # A2 = twist(A1) 的头部原始状态值

def recover_y(i):
r = C[i] ^ C[i - 227] # = (y_i>>1) ^ mag_bit
if r >> 31: # 最高位 1 => 异或了 mag,y_i 为奇数
return ((r ^ 0x9908b0df) << 1) | 1
return r << 1

hi, lo = {}, {}
for i in range(227, s - 625 + 1): # s-625 = 375+n,覆盖 flag 所需范围
y = recover_y(i)
hi[i] = y & 0x80000000 # y_i 高位 -> B[i] 的 bit31
lo[i + 1] = y & 0x7fffffff # y_i 低 31 位 -> B[i+1] 的 bits0-30

# flag 第 t 字节的随机数 = temper(B[376+t]) >> 24
flag = bytes(enc[t] ^ (temper(hi[376 + t] | lo[376 + t]) >> 24) for t in range(n))
print(flag.decode(errors="replace"))

创宇杯

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randbytes
from secret import flag

key = randbytes(16)

while input(">>> "):
aes = AES.new(key, AES.MODE_CBC, iv=randbytes(16))
print("your gift: " + (aes.iv + aes.encrypt(pad(flag, 16))).hex())

分析

想了半天CBC,后面才反应过来是打mt19937
有连续randbytes,random输出一定要先想能不能打mt!

exp

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from random import randbytes
from pwn import *
from Crypto.Util.number import *

def _int32(x):
return int(0xFFFFFFFF & x)

def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp

def extract_number(y):
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return y&0xffffffff

def recover(y):
y = inverse_right_mask(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right_mask(y,11)
return y&0xffffffff

def inv_twist(state):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
prev = [0]*624
for i in range(623, -1, -1):
tmp = state[i] ^ state[(i + 397) % 624]
if tmp & high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<= 1
if i > 0:
prev[i] = (prev[i-1] & high) | (tmp & low)
else:
prev[i] = tmp & high
return prev

def ext_number(index):
y = mt1[index]
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return _int32(y)


io = remote("challenge.xiaoyuyc.com" ,33007)
output_iv = []
output_c = []
for i in range(312):
io.recvuntil(b">>> ")
io.sendline(b'1')
io.recvuntil(b'gift: ')
temp = io.recvline().strip().decode()
iv = bytes.fromhex(temp[:32])
c = temp[32:]
output_c.append(c)
output_iv.append(iv)
print("ok")

mt_out_all = []
for i in range(312):
temp1 = bytes_to_long(output_iv[i][::-1])
for j in range(4):
mt_out_all.append(temp1 & 0xffffffff)
temp1 = temp1 >> 32

mt_out2 = mt_out_all[620:-4]

mt2 = []
for i in range(624):
mt2.append(recover(mt_out2[i]))

mt1 = inv_twist(mt2)

key = 0
for i in range(4):
key |= ext_number(i) << 32*i
key = key.to_bytes(16,'little')

iv =output_iv[6]
c = bytes.fromhex(output_c[6])
aes = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(aes.decrypt(c), 16)
print(flag)

这个题有一点就是,第一个块624输出是残缺的,第一个输出拿去当了key,所以收集后面第二个块的624位输出再做逆twist就行