TetCTF-2020th
分析一下源码，可知程序使用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 = * 624
self.index = 0
self.MT = seed & 0xffffffff
for i in range(1, 623+1):
self.MT = ((0x6c078965 * (self.MT ^ (self.MT >> 30))) + i) & 0xffffffff
def generate_numbers(self):
for i in range(0, 623+1):
y = (self.MT & 0x80000000) + (self.MT[(i+1) % 624] & 0x7fffffff)
self.MT = self.MT[(i + 397) % 624] ^ (y >> 1)
if (y % 2) != 0:
self.MT = self.MT ^ (2567483615)
def extract_number(self):
if self.index == 0:
self.generate_numbers()
y = self.MT
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，可以很容易的根据extract_number计算出randomnum（即第2020个随机数），因此我们的重点只需放在generate_numbers函数，来想办法计算出MT即可。观察generate_numbers函数可以发现，由于generate_numbers函数是每生成624个随机数调用一次，即MT的值是由MT,MT和MT生成的，我们令i=1395，此时即MT可以由MT,MT,MT这3个数计算而来，但是我们只能获取最多2个数的值，还缺少一个数的值无法获取。继续观察generate_numbers函数的运算流程，发现在关于MT参数的运算为(self.MT & 0x80000000)，其运算结果不是0（当0<=MT<0x80000000时）就是0x80000000（当0x80000000=<MT<=0xffffffff时），即我们可以遍历所需要的3个参数中第一个参数的值，另外两个MT的值采用程序提供的接口来获取，这样就有50%的概率可以计算出正确的MT的值，然后再计算出randomnum的值尝试提交。由于正确的概率想到高，因此尝试几次即可获得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))
resp = s.recvline().strip()
if "TetCTF" in resp:
print resp
exit(0)执行脚本即可得到flag：TetCTF{y0u_4r3_1nd33d_4_pr0ph3t}
非常喜欢学逆向论坛，资源我先收下了！
页:
[1]