CTF中针对梅森旋转算法的攻击手法
CTF中梅森旋转算法的知识总结与应用
CTF中针对梅森旋转算法的攻击手法
前置知识
梅森旋转算法就是在解题中比较常见的MT19937,有32位,64位
在random中生成随机数的方式是这种方式
加密过程如下,只是简单的了解了一下,一般情况下这个加密过程不会考,但不排除魔改的可能
class MT19937:
n = 624
m = 397
a = 0x9908b0df
b = 0x9d2c5680
c = 0xefc60000
kInitOperand = 0x6c078965
kMaxBits = 0xffffffff
kUpperBits = 0x80000000
kLowerBits = 0x7fffffff
register = [0] * n
state = 0
# 将数字变为 32 位整数
def _int32(self, x):
return x & 0xffffffff
# 初始化寄存器状态
def seed(self, seed):
self.register[0] = seed
for i in range(1, self.n):
self.register[i] = self._int32(self.kInitOperand *
(self.register[i-1] ^ self.register[i-1] >> 30) + i)
def __init__(self, seed = None):
if seed:
self.seed(seed)
# 旋转
def twist(self):
for i in range(self.n):
x = self._int32((self.register[i] & self.kUpperBits) +
(self.register[(i + 1) % self.n] & self.kLowerBits))
self.register[i] = self.register[(i + self.m) % self.n] ^ (x >> 1)
if x & 1 != 0:
self.register[i] ^= self.a
self.state = 0
# 提取
def extract(self):
if self.state >= self.n:
self.twist()
x = self.register[self.state]
x ^= x >> 11
x ^= (x << 7) & self.b
x ^= (x << 15) & self.c
x ^= x >> 18
self.state += 1
return self._int32(x)
def __call__(self):
return self.extract()对于去预测这个随机数生成器,这对于预测下一位,我们可以手动恢复
class MT19937Recover:
#左移位恢复
def unshiftRight(self, x, shift):
res = x
for i in range(32):
res = x ^ res >> shift
return res
#右移位恢复
def unshiftLeft(self, x, shift, mask):
res = x
for i in range(32):
res = x ^ (res << shift & mask)
return res
#提取伪随机数逆向
def untemper(self, v):
v = self.unshiftRight(v, 18)
v = self.unshiftLeft(v, 15, 0xefc60000)
v = self.unshiftLeft(v, 7, 0x9d2c5680)
v = self.unshiftRight(v, 11)
return v
#通过输出参数逆向
def go(self, outputs, forward=True):
result_state = None
assert len(outputs) >= 624
ivals = []
for i in range(624):
ivals.append(self.untemper(outputs[i]))
if len(outputs) >= 625:
challenge = outputs[624]
for i in range(1, 626):
state = (3, tuple(ivals+[i]), None)
r = random.Random()
r.setstate(state)
if challenge == r.getrandbits(32):
result_state = state
break
else:
result_state = (3, tuple(ivals+[624]), None)
rand = random.Random()
rand.setstate(result_state)
if forward:
for i in range(624, len(outputs)):
assert rand.getrandbits(32) == outputs[i]
return rand
mtc = MT19937Recover()实际应用
在比赛中,为了实现比较高效的恢复,可以不用这个代码,直接调用python中的内置函数即可恢复状态进行预测
对于常规的题目,一般是给你多个预测数进行恢复,如果不够624常规恢复的话,可能要进行爆破了等操作,具体问题,具体分析,一般还会有其他漏洞
例如新春杯里
已知输出的数,尝试预测后面的数,这个是常见的基础题
from extend_mt19937_predictor import ExtendMT19937Predictor
p = ExtendMT19937Predictor()
for x in leak[:need]:
p.setrandbits(x, 128)
#前面是恢复,后面是进行预测后续的数
k = p.predict_getrandbits(500)
r = p.predict_getrandbits(512)还有一种方式,可以应对不同参数的加密,用矩阵状态破解,这个要用sage来解
def extract_number(x):
x ^^= x >> 11
x ^^= (x << 7) & 2636928640
x ^^= (x << 15) & 4022730752
x ^^= x >> 18
return x & 0xffffffff
T = []
for i in range(32):
x = 1 << (31 - i)
x = extract_number(x)
T.append(x.digits(2, padto=32)[::-1])
T = matrix(GF(2), T)
def untemper(leak):
Z = matrix(GF(2), ZZ(leak).digits(2, padto=32)[::-1])
X = T.solve_left(Z)
return reduce(lambda x, y: (ZZ(x) << 1) + ZZ(y), list(X[0]))还有这个题,是对random的拓展,对random函数进行了魔改,导致无法正常恢复
题目放插件里了,太大了,大家可以先试着做做
random原函数
def _randbelow_with_getrandbits(self, n):
getrandbits = self.getrandbits
k = n.bit_length()
r = getrandbits(k)
while r >= n:
r = getrandbits(k)
return r魔改后
def _randbelow_with_getrandbits(self, n):
getrandbits = self.getrandbits
k = n.bit_length() - 1
r = getrandbits(k)
while r >= n:
r = getrandbits(k)
return r对于random(n),本质上是调用了_randbelow(n)
魔改后
18.bit_length() == 5
k = 4
getrandbits(4)结果范围只有0 ~ 15,而不是原来的0 ~ 17
对于130也如此
结果范围到0 ~ 127
a_i = randrange(18) 实际是 getrandbits(4)
b_i = randrange(130) 实际是 getrandbits(7)
所以说,a_i 是 MT19937 输出的高 4 bit,b_i 是下一次 MT19937 输出的高 7 bit
这就回到了MT19937恢复这个问题上了
这里用到了z3恢复,恢复过程也比较复杂难懂。下面通过流程图来简单说一下z3解密过程
[ 624个符号未知数: s_0 到 s_623 ]
│(经 twist_z3 矩阵旋转)
[ 生成几千个带有未知数表达式的输出 out_a, out_b ]
│(遍历 gift 中的每个字节 value)
[ 猜测 a -> 计算 mask -> 推导明文 b ] ─── (过滤掉不合法的 ASCII b)
│(如果是合法组合)
[ 约束条件:out_a 的高4位 == a AND out_b 的高7位 == b ]
│(收集所有合法组合,通过 Or 注入求解器)
[ solver.add( Or( 组合1, 组合2, ... ) ) ]
│(调用 solver.check())
[ Z3 自动解方程方程组 ─── 产出真实确定的状态数组 ]之后恢复出来后,预测 shuffle,将shuffle逆向出来,这样就可以得到flag
exp
import sys
import random
from z3 import *
sys.set_int_max_str_digits(0)
N = 624
M = 397
MATRIX_A = 0x9908B0DF
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7FFFFFFF
def temper_z3(y):
y = y ^ LShR(y, 11)
y = y ^ ((y << 7) & BitVecVal(0x9D2C5680, 32))
y = y ^ ((y << 15) & BitVecVal(0xEFC60000, 32))
y = y ^ LShR(y, 18)
return y
def twist_z3(mt):
new_mt = []
for i in range(N):
y = (mt[i] & BitVecVal(UPPER_MASK, 32)) | (mt[(i + 1) % N] & BitVecVal(LOWER_MASK, 32))
v = mt[(i + M) % N] ^ LShR(y, 1)
v = If((y & BitVecVal(1, 32)) == BitVecVal(1, 32), v ^ BitVecVal(MATRIX_A, 32), v)
new_mt.append(v)
return new_mt
def build_outputs(initial_state, count):
outputs = []
mt = initial_state
idx = N
for _ in range(count):
if idx >= N:
mt = twist_z3(mt)
idx = 0
outputs.append(temper_z3(mt[idx]))
idx += 1
return outputs
def recover_state(gift):
state = [BitVec(f"s_{i}", 32) for i in range(N)]
need_outputs = len(gift) * 2
outputs = build_outputs(state, need_outputs)
solver = Solver()
for i, value in enumerate(gift):
out_a = outputs[2 * i]
out_b = outputs[2 * i + 1]
a_top4 = Extract(31, 28, out_a)
b_top7 = Extract(31, 25, out_b)
cases = []
for a in range(16):
mask = pow(a, 2 * i, 17) & 0xF
b = value ^ mask
if 0 <= b < 128:
cases.append(
And(
a_top4 == BitVecVal(a, 4),
b_top7 == BitVecVal(b, 7)
)
)
if not cases:
raise RuntimeError(f"no possible case at gift index {i}")
solver.add(Or(*cases))
if i >= 2500:
break
result = solver.check()
if result != sat:
raise RuntimeError(f"z3 failed: {result}")
model = solver.model()
recovered = [model.evaluate(x).as_long() for x in state]
return recovered
def buggy_randbelow(r, n):
k = n.bit_length() - 1
value = r.getrandbits(k)
while value >= n:
value = r.getrandbits(k)
return value
gift_int = 0
#注意要加上密文
c = ""
gift = gift_int.to_bytes(6500, "big")
print("recovering MT19937 state...")
recovered_state = recover_state(gift)
print("state recovered")
r = random.Random()
internal = tuple(recovered_state + [624])
r.setstate((3, internal, None))
for _ in range(len(gift)):
buggy_randbelow(r, 18)
buggy_randbelow(r, 130)
swaps = []
for _ in range(2024):
for i in reversed(range(1, len(c))):
j = buggy_randbelow(r, i + 1)
swaps.append((i, j))
arr = list(c)
for i, j in reversed(swaps):
arr[i], arr[j] = arr[j], arr[i]
flag = "".join(arr)
print("flag:", flag)