PRNG MT Notes

huangx607087关于PRNG MT 的学习笔记

0x00 博客背景

9月25日做出的0xCTF上的PRNG2，不过那道题源码不小心被我删掉了Orz，一个月后会回顾一下之前的笔记，记录自己当时的学习过程

0x01 MT简介

梅森旋转(Mersenne Twister)是一个PRNG伪随机数发生算法，基于有限二进制字段上的矩阵递归（反正我也不懂），周期高达$2^{17399}-1$

步骤：
1.获得基础的梅森旋转链
2.对于旋转链进行旋转算法
3.对于旋转算法所得结果进行处理
注:该算法的实现过程中参数的选取主要取决于梅森素数

涉及变量：
$w$ ：加密长度，以bit为单位，$w$位整数。
$n$ ：递归长度
$m$：周期参数，用于第三阶段的偏移量
$a$：旋转矩阵的参数
$r$：低位掩码，即低位要提取的位数
$f$：初始化旋转链所需参数
$b,c$：TGFSR的掩码
$s,t$：TGFSR的位移量
$u,d,l$ 额外的梅森旋转所需要的掩码和位移量

0x02 加密方法

1.初始化，将传入的seed值赋值给$ MT_0 $作为初值，并递推得到旋转链
递推式：$MT_i=f×(MT_{i-1})$ xor $((MT_{i-1})>>(w-2))+i$

2.执行旋转算法
连接$MT_{i}$的高$w-r$位和$MT_{i+1}$的低$r$位，若这个组合后的二进制数末位为$0$，将其除以$2$.。否则将这个数除以$2$后再与$a$进行异或。假设我们最终得到的数字为$P$
所以我们的递推式为$MT_i=MT_{i+m}$ xor $P$

3.对于旋转算法所得结果进行处理：
设$x$为该序列下一个值，$y$是一个临时的中间变量，$z$是算法返回值
以下为处理过程：

y=x xor((x>>u)&d)
y=y xor((y<<s)&b)
y=y xor((y<<t)&c)
z=y xor(y>>l)

0x03 解密方法

解密关键：求出一个周期内的全部内容，然后就可以顺推得出前面所有的情况了

逆向处理。加密一共$4$步，都是异或运算，所以我们可以写出逆算法

我们先来看看加密的最后一步：z=y xor (y>>l)，很显然，这一操作时不影响$y$的最高$l$位的，所以$z$的最高$l$位就是$y$的最高$l$位，我们可以通过$y>>l$的高$2l$位（最高$l$位全是$0$），从而我们可以得到$y$的$2l$位，进而得到$y>>l$的高$3l$位…….

上面的可能有点抽象，在此举个例子：

$y=10110110_b,t=10011011_b,l=2,y/4=00101011_b$（已知量只有$t,l$）

根据$t$的高$2$位，我们知道$y$的高$2$位为$10_b$，我们可以得到$y/4$的高$4$位为$0010_b$，由于$y$的高$4$位异或$y/4$的高$4$位可以得到$t$的高$4$位，所以$y$的高$4$位可以算出来,进而我们就可以算法出$y$的高$6$位了……

这样，我们就可以把第4步逆出来了。

关于逆出第3步，$y_1=y$ xor$((y<<t)$&$c)$，我们可以发现：$y_1$的低$t$位就是$y$的低$t$位异或$c$的低$t$位求出来的结果，所以$y_1$的低$t$位与$c$的低$t$位异或以下即为$y$的低$t$位，进而我们可以得到$(y<<t)$的低$2t$位，模仿上面的方法得到$y$的所有位

第2步和第1步分别于第3步和第4步同理，我们可以直接放上解密脚本（这么好的代码当然不是我这个fw能写出来的）

# right shift inverse
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp
# left shift inverse
def inverse_left(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp
def extract_number(y):
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y&0xffffffff
def recover(y):
    y = inverse_right(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right(y,11)
    return y&0xffffffff
print(recover(0xf1c680f8))
'''
for i in s:
    print(recover(i))

y = extract_number(o)
print('y=',y,'o=',o)
print(recover(y) == o)
'''

MT32的一些基本属性：
$(w,n,m,r)=(32,624,397,31)$
$(a,f)=(9908B0DF_h,1812433253)$
$(u,d,s,b,t,c)=(11,FFFFFFFF_h,7,9D2C5680_h,15,EFC60000_h)$
$l=18$

0x04 具体题目中分析

0xCTF PRNG2详解

首先我们看一下源代码

from Crypto.Util.number import*
from secret import flag
assert flag[:6] == "0xCTF{"
class MT():
    def __init__(self, seed):
        self.state = [seed]+[0]*23
        self.flag = 0
        self.srand()
        self.generateNumbers()

    def srand(self):
        for i in range(23):
            self.state[i+1] = 1812433253 *  (self.state[i] ^ (self.state[i] >> 27)) - i
            self.state[i+1] &= 0xffffffff

    def generateNumbers(self):
        for i in range(24):
            y = (self.state[i] & 0x80000000) | (
                self.state[(i+1) % 24] & 0x7fffffff)
            temp = y >> 1
            temp ^= self.state[(i + 12) % 24]
            if y & 1:
                temp ^= 0x9908b0df
            self.state[i] = temp

    def getRandomBits(self):
        if self.flag == 24:
            self.generateNumbers()
            self.flag = 0
        bits = self.Next(self.state[self.flag])
        self.flag += 1
        return long_to_bytes(bits)

    def Next(self, tmp):
        tmp ^= (tmp >> 11)
        tmp ^= (tmp << 7) & 0x9d2c5680
        tmp ^= (tmp << 15) & 0xefc60000
        tmp ^= (tmp >> 18)
        return tmp
def Encrypt(key, char):
    key = bytes_to_long(key)
    temp = hex(pow(ord(char), 65537, 2**8-1) ^ key)[2:]
    return '0'*(32-len(temp))+temp
if __name__ == "__main__":
    mt = MT(getRandomNBitInteger(32))
    c = ''
    for i in range(len(flag)):
        c += Encrypt(b''.join([mt.getRandomBits() for _ in range(4)]), flag[i])
    print(c)

这道题对标准的MT进行一下分析：与标准算法相比，只有$n$的值从$624$变成了$24$。

然而一个很显然的事实是：我这个密码学fw根本看不懂这么长的代码，怎么办？答案当然是靠输出来调试调试程序究竟是如何运行的。通过加运行可以看到：对于每一位字符，这个处理器会处理$4$次，然而每一次，会对第$4$次求出的结果进行异或。。

题目给出了一个很长的$c$字符$16$进制字符串，所以我们可以用C++等工具，把字符串$c$分为$8$位一小组(每组刚好是$32$位二进制数)，$4$小组以大组。根据代码调试分析一下，每一大组的最后一个数字与明文对应的字符进行了异或操作，所以对于这$6$个数字来说，我们可以通过Win10自带的计算机(或者手搓)，可以得到异或前的数字，也就是程序最后输出的bytes

例如：第一行最后一个数为$617d7a88_h$我们可以根据第一个字符为'0'，推断出第一次异或的内容为$30_h$，进而得到异或前的bytes值为$617d7aB8_h$

根据题目assert内容，我们知道了字符串前$6$位，因此我们可以上脚本考虑恢复原来的寄存器内部的$24$位。

在这里有一个小细节：$x^{65537} \equiv x\mod 255$.因为$\phi(255)=128$，所以根据费马小定理有$x^{65536}\equiv 1\mod 255$，这个结论我们就推出来了。

把我们分割出来的前$24$个并进行简单处理过的十六进制数代入上面的求逆脚本，我们就可以得到第一组寄存器内的内容了。

简单地改一下代码初始化部分，删去__init__中的srand和generateNumbers。把初始化的seed参数和主函数中的getRandomNBitInteger(32)删去。然后每次输出mt.getRandomBits()，就可以得到一个个解（推荐$4$个一行，以$16$进制输出）

如果你是按照推荐的做法做的，我们可以一个一个比对一下(左边为程序输出结果，右边为给出来的数值)，此处为程序输出与给出数值第$7$到第$9$行的比较。

a46e5465 533477c6 3f7f5649 cc96ec79 | a46e5465 533477c6 3f7f5649 cc96ec49
8bebeb18 c6f90a3c 38ff0c8a 0837182e | 8bebeb18 c6f90a3c 38ff0c8a 0837181b
31ba3fa7 efaee340 f9b70a82 a6fafa6f | 31ba3fa7 efaee340 f9b70a82 a6fafa57

很显然，正如我们预期：最后的一个数字不一样，并且刚好有点略微的差别，这就说明这是个跟某个数异或过的结果，而那个数，恰好就是那一位字符的ASCII码值。我们只需要用C++的freopen提取出两处的第$4$位，然后异或一下就得出结果了(如果你用的C++务必把数值类型设置成unsigned而不是int，不然十六进制中大于等于$80000000_h$会被标记为负数，导致异或结果出错)

最后异或完成的结果就是flag。