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)