# 提取伪随机数 defextract_number(self): ifself.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)
y = y ^ (y >> 11) y = y ^ ((y << 7) & 0x9D2C5680) y = y ^ ((y << 15) & 0xEFC60000) y = y ^ (y >> 18)
这些操作都是可逆的!我们可以编写untemper函数,从输出恢复原始状态。
位运算逆向分析:
每一步的动作都差不多,我们取一步分析: y = y ^ ((y << shift) & mask)
definverse_left_mask(res, shift, mask=0xffffffff, bits=32): """逆向 y = y ^ ((y << shift) & mask)""" tmp = res for i inrange(bits // shift): tmp = res ^ (tmp << shift) & mask return tmp
完整untemper
defuntemper(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
definverse_right_mask(res, shift, mask=0xffffffff, bits=32): tmp = res for i inrange(bits // shift): tmp = res ^ (tmp >> shift) & mask return tmp
definverse_left_mask(res, shift, mask=0xffffffff, bits=32): tmp = res for i inrange(bits // shift): tmp = res ^ (tmp << shift) & mask return tmp
defuntemper(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个随机数 withopen('random_numbers.txt', 'r') as f: outputs = [int(line.strip()) for line in f.readlines()[:624]]
# 再输出一些随机数 for _ inrange(624): print(random.getrandbits(32))
除了恢复内部状态之外多了一步逆twist
exp
import sys, re
M32 = 0xffffffff
definv_right(y, s): # 逆 y ^= y >> s x = y for _ inrange(32 // s + 1): x = y ^ (x >> s) return x & M32
definv_left(y, s, m): # 逆 y ^= (y << s) & m x = y for _ inrange(32 // s + 1): x = y ^ ((x << s) & m) return x & M32
defuntemper(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
deftemper(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)] assertlen(outs) == 624
n = len(enc) # flag 长度 s = 1000 + n # 第一条尾部输出的全局下标 k = 1248 - s # 尾部输出中属于状态 A1 的个数 assert0 <= k, "flag too long"
x = [untemper(v) for v in outs] C = x[k:] # A2 = twist(A1) 的头部原始状态值
defrecover_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 inrange(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 inrange(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
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): returnint(0xFFFFFFFF & x)
definverse_right_mask(res, shift, mask=0xffffffff, bits=32): tmp = res for i inrange(bits // shift): tmp = res ^ tmp >> shift & mask return tmp
definverse_left_mask(res, shift, mask=0xffffffff, bits=32): tmp = res for i inrange(bits // shift): tmp = res ^ tmp << shift & mask return tmp
defextract_number(y): y = y ^ y >> 11 y = y ^ y << 7 & 2636928640 y = y ^ y << 15 & 4022730752 y = y ^ y >> 18 return y&0xffffffff
defrecover(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
definv_twist(state): high = 0x80000000 low = 0x7fffffff mask = 0x9908b0df prev = [0]*624 for i inrange(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
defext_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 inrange(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 inrange(312): temp1 = bytes_to_long(output_iv[i][::-1]) for j inrange(4): mt_out_all.append(temp1 & 0xffffffff) temp1 = temp1 >> 32
mt_out2 = mt_out_all[620:-4]
mt2 = [] for i inrange(624): mt2.append(recover(mt_out2[i]))
mt1 = inv_twist(mt2)
key = 0 for i inrange(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)