查看: 249|回复: 1

[Crypto] TetCTF-2020th

[复制链接]
发表于 2020-2-26 17:27:10 | 显示全部楼层 |阅读模式
分析一下源码,可知程序使用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}

温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
善莫大焉-2019

0

主题

87

帖子

0

精华

中级会员

Rank: 8Rank: 8

学币
223
荣耀
0
rank
0
违规
0

    发表于 2020-3-2 00:08:27 | 显示全部楼层
    非常喜欢学逆向论坛,资源我先收下了!
    关闭

    论坛公告上一条 /1 下一条

    快速回复 返回顶部 返回列表