TetCTF-2020th

roger

分析一下源码，可知程序使用python的random模块连续生成了2019个随机数，我们可以选择查看这2019个随机数中任意2个随机数的值，我们的任务是预测出接下来要产生的第2020个随机数的值，如果预测成功即可获得flag。

通过查阅python的random模块，可以得知其在生成随机数时使用了梅森旋转算法，且其版本为MT19937，即该PRNG采用32位的state和32位的输出，我们可以找一版python的MT19937 Mersenne Twister PRNG来看一下（p.s. 维基百科上提供了梅森旋转算法的伪代码，有兴趣的读者可以自己实现一版，这同样也是cryptopals当中的一个任务）：

class MT19937RNG:
    def __init__(self, seed):
        self.MT = [0] * 624
        self.index = 0
        self.MT[0] = seed & 0xffffffff
        for i in range(1, 623+1):
            self.MT[i] = ((0x6c078965 * (self.MT[i-1] ^ (self.MT[i-1] >> 30))) + i) & 0xffffffff

    def generate_numbers(self):
        for i in range(0, 623+1):
            y = (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] ^ (2567483615)

    def extract_number(self):
            if self.index == 0:
                self.generate_numbers()
            y = self.MT[self.index]
            y = y ^ (y >> 11)
            y = y ^ ((y << 7) & (0x9d2c5680))
            y = y ^ ((y << 15) & (0xefc60000))
            y = y ^ (y >> 18)
            self.index = (self.index + 1) % 624
            return y

审计代码可知，该PRNG在初始化时会建立一个长度为624的数组MT，使用extract_number函数来生成随机数，第一次生成随机数时会调用generate_numbers函数来更新MT数组的值，之后每连续生成624个随机数，都会使用generate_numbers函数来更新MT数组的值。而extract_number函数的过程是可逆的，这意味着如果我们知道一个randomnum，我们是可以求出其对应的MT的。另外，如果我们知道了MT[2019]，可以很容易的根据extract_number计算出randomnum[2019]（即第2020个随机数），因此我们的重点只需放在generate_numbers函数，来想办法计算出MT[2019]即可。

观察generate_numbers函数可以发现，由于generate_numbers函数是每生成624个随机数调用一次，即MT[i+624]的值是由MT,MT[i+1]和MT[i+397]生成的，我们令i=1395，此时即MT[2019]可以由MT[1395],MT[1396],MT[1792]这3个数计算而来，但是我们只能获取最多2个数的值，还缺少一个数的值无法获取。

继续观察generate_numbers函数的运算流程，发现在关于MT参数的运算为(self.MT & 0x80000000)，其运算结果不是0（当0<=MT<0x80000000时）就是0x80000000（当0x80000000=<MT<=0xffffffff时），即我们可以遍历所需要的3个参数中第一个参数的值，另外两个MT的值采用程序提供的接口来获取，这样就有50%的概率可以计算出正确的MT[2019]的值，然后再计算出randomnum[2019]的值尝试提交。由于正确的概率想到高，因此尝试几次即可获得flag。

将上述推导写成python代码形式如下：

import random
from pwn import *

def USR(x, shift):
    res = x
    for i in range(32):
        res = x ^ res >> shift
    return res

def USL(x, shift, mask):
    res = x
    for i in range(32):
        res = x ^ (res << shift & mask)
    return res

def randomnum_to_MT(v):
    v = USR(v, 18)
    v = USL(v, 15, 0xefc60000)
    v = USL(v, 7, 0x9d2c5680)
    v = USR(v, 11)
    return v

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

def solve(a, b):
    res = []
    MT_iadd1, MT_iadd397 = randomnum_to_MT(a), randomnum_to_MT(b)
    for msb in range(2):
        y = (msb * 0x80000000) + (MT_iadd1 & 0x7fffffff)
        MT_i = MT_iadd397 ^ (y >> 1)
        if (y % 2) != 0:
            MT_i = MT_i ^ 0x9908b0df
        res.append(MT_to_randomnum(MT_i))
    return res

while True:
    s = remote("207.148.119.58", 6666)
    s.sendline("1396")
    s.sendline("1792")
    guess = []
    for _ in range(2019):
        a = s.recvline().strip()
        if "Nope" not in a:
            guess.append(int(a))

    res = solve(*guess)
    s.sendline(str(res[0]))
    resp = s.recvline().strip()
    if "TetCTF" in resp:
        print resp
        exit(0)

执行脚本即可得到flag：

TetCTF{y0u_4r3_1nd33d_4_pr0ph3t}

monkeyman

非常喜欢学逆向论坛，资源我先收下了！