Fight For Freedom

03月 10

攻破随机数产生器(二)

我有拖延症啊。

0x00 前言

如今在各类开发中都缺少不了伪随机数的产生,可如果对于其中的随机算法不甚了解,不慎用随机算法,那么后果不言而喻。但是国内对这方面的文章资料甚少,由此,我把国内外的资料和论文等进行整理,对其中的一种常见随机算法进行了详细的分析。

0x01 背景

现在较为流行的伪随机算法(PRNG)当属梅森旋转算法,它已被用在了Ruby的rand()中,python的random模块中和php的mt_rand中等等,用途相当广泛。它是一个高质量的随机算法,但它并不是用来产生密码学意义上的安全值(cryptographic security),如果将它应用在开发的关键地方,比如token生成、session产生等,那将会导致被预测攻破的结果。下面的讲解都将以php为例,毕竟是最好的语言。

国外很早以前就发现了php的rand/mt_rand所可能产生的危害,80sec在多年前也提出来过,只是没多少人重视。其中比较出名的要数discuz密码重置漏洞(如下图),里面关键的id_hash用了mt_rand,但poc是采用暴力破解的方式去得到seed。


php在apache下是采用fastcgi的模式,也就是说每次对web的连接都是当前web系统从已fork好的进程去选一个提供给我们,然而在同一个进程中,seed是相同的,否则seed会变化。并且,使用apache和mod_php会使HTTP keep-alive的请求导致php对于在一个"session"中的每个请求使用相同的进程。所以,在实际场景中,我们需要保持keep-alive才能保证随机数是同一状态产生的。

php的rand()是基于系统的实现,用了弱线性反馈移位寄存器(LFSR),这里不作讲解。而mt_rand是PRNG,采取的是梅森旋转算法(Mersenne Twister),梅森旋转算法也是基于LFSR的,移位旋转,周期为一个梅森素数2^19937 -1。可用来生成高质量的伪随机数,它会采用随机数种子seed来生成随机数的值。

我们都知道如果攻击者可以获取到随机数种子seed,那么他就可以预测到mt_rand()所产生的随机值。因此,能不能反推回seed或seed能不能被暴力破解成为了攻破PRNG的关键。
(注: php内部实现梅森旋转算法与标准有一处极小的不同,据说是代码的bug。)

如果种子没有指定,那么它就会采取如下的方法生成32bit种子,这是可以破解的。

seed = (time()*pid)^(10^{6}*php_combined_lcg())
time(): leaked by the Date HTTP Header
pid: obtained through the session id preimage
php_combined_lcg(): obtained through the session id preimage

下面我们将从算法角度上去探究它会出现的问题。

 

0x02 梅森旋转算法

它包含了624个32位整数的状态,设i指向当前的整数。共有三步:
1. 初始化函数(initialize),用来产生种子seed;
2. 迭代函数(generate),从旧的状态中产生新的状态;
3. 提取函数(tamper),从当前的状态产生一个随机数。

初始化函数
以种子为基,不断从前面一个状态产生新状态,直到624为止:

def initialize_state(seed):
    state = [seed]
    for i in xrange(1, 624):
        prev = state[-1]
        elem = 0x6c078965 * (prev ^ (prev » 30)) + i
        state.append(uint32(elem))
    return state

 

状态迭代函数
每次624个元素都参与运算了的,保存在一个数组中。如下图:

def generate(s):
    for i in xrange(624):
        y = s[i] & 0x80000000
        y += s[(i + 1) % 624] & 0x7fffffff
        z = s[(i + 397) % 624]
        s[i] = z ^ (y » 1)
        
        if y % 2:
            s[i] ^= 0x9908b0df

提取函数

为了提升输出再循环的随机性,我们将现有状态与一个可逆的矩阵T相乘来产生伪随机数。这个T可用如下的函数来表示,被称为tempering matrix。

用现在的状态去产生伪随机数:

_TEMPER_MASK_1 = 0x9d2c5680
_TEMPER_MASK_2 = 0xefc60000
def temper(y):
    y ^= uint32(y » 11)
    y ^= uint32((y « 7) & _TEMPER_MASK_1)
    y ^= uint32((y « 15) & _TEMPER_MASK_2)
    y ^= uint32(y » 18)
    return y

由此,一般来说,我们可以将上述函数修改下,使用如下的方法去产生伪随机数:

class MersenneTwister:
    length = 624

    def __init__(self, seed=0):
        self.state = [0]*self.length
        self.index = 0

        self.state[0] = seed
        for i in xrange(1, self.length):
            t = 1812433253 * (self.state[i-1] ^ (self.state[i-1] >> 30)) + i
            self.state[i] = t & (2**32 - 1)

    def tamper(self):
        if self.index == 0:
            self.generate()

        y = self.state[self.index]
        y = y ^ (y >> 11)
        y = y ^ (y << 7) & 2636928640
        y = y ^ (y << 15) & 4022730752
        y = y ^ (y >> 18)

        self.index = (self.index + 1) % self.length
        return y

    def generate(self):
        for i in xrange(self.length):
            y = (self.state[i] & 0x80000000) + ((self.state[(i+1) % self.length]) & 0x7fffffff)
            self.state[i] = self.state[(i + 397) % self.length] ^ (y >> 1)
            if y % 2:
                self.state[i] ^= 2567483615


if __name__ == '__main__':
    mt = MersenneTwister(0)
    mt.tamper()

从上面可以得出,用户先给seed去初始化,并generate数组,最后在tamper函数中实现对当前的状态进行产生伪随机数。梅森旋转算法内部624个状态是按顺序使用的,提取函数会把所有的状态遍历完了再循环。

也就是说,对于攻击者而言,只要拿到内部的状态state,就可以完全预测出以后产生的伪随机数了。

 

0x03 攻破梅森旋转

想要攻破该算法,或者说这算法的“不足”,有两方面。一方面来自于最坏的打算--爆破,这完全在可接受的范围内(比如php_mt_rand工具等),另一方面则在于tamper函数是可逆的。该函数是一一映射的,每32bit的整数输入对应到一个输出,反之亦然。由此可反推回去,即从随机数可推得当前状态。

下面我们来看它是具体怎么操作的。以tamper函数中的一个小式子为例:

y ^= (y >> 18)

用二进制表示出来更清晰:

10110111010111100111111001110010    y
00000000000000000010110111010111```100111111001110010```    y >>> 18
10110111010111100101001110100101   y ^ (y >>> 18)

从上面我们可以直接得到原来的18bit,然后再通过移位异或将原来的值彻底给恢复出来。依次类推,可用如下的通用方法将其给算出来。

int unBitshiftRightXor(int value, int shift) {
  // we part of the value we are up to (with a width of shift bits)
  int i = 0;
  // we accumulate the result here
  int result = 0;
  // iterate until we've done the full 32 bits
  while (i * shift < 32) {
    // create a mask for this part
    int partMask = (-1 << (32 - shift)) >>> (shift * i);
    // obtain the part
    int part = value & partMask;
    // unapply the xor from the next part of the integer
    value ^= part >>> shift;
    // add the part to the result
    result |= part;
    i++;
  }
  return result;
}
int unBitshiftLeftXor(int value, int shift, int mask) {
  // we part of the value we are up to (with a width of shift bits)
  int i = 0;
  // we accumulate the result here
  int result = 0;
  // iterate until we've done the full 32 bits
  while (i * shift < 32) {
    // create a mask for this part
    int partMask = (-1 >>> (32 - shift)) << (shift * i);
    // obtain the part
    int part = value & partMask;
    // unapply the xor from the next part of the integer
    value ^= (part << shift) & mask;
    // add the part to the result
    result |= part;
    i++;
  }
  return result;
}

有了上面两个通用函数,我们可以将output推测到当前的状态:

int value = output;
value = unBitshiftRightXor(value, 18);
value = unBitshiftLeftXor(value, 15, 0xefc60000);
value = unBitshiftLeftXor(value, 7, 0x9d2c5680);
value = unBitshiftRightXor(value, 11);

只需要知道这个算法的输出,那么就可以逆推回去得到624个状态中的一个。接下来的一步就是,进一步得到该当前状态的初始状态。

int y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff);
int next = y >>> 1;
if ((y & 1L) == 1L) {
  next ^= 0x9908b0df;
}
next ^= state[(i + 397) % 624];

这是上面generate函数的主要功能。我们能看到这主要涉及了s[i]、s[(i+1)%624]、s[(i+397)%624]三个初始状态。为了方便看generate是如何操作的,我们用二进制来表示下:

现在目的是想求到初始状态state[i],那么我们来看看能否从后往前推回去。我们可以异或state[i+397]从第7步到第6步。然而从第6步逆推回第五步需要看y是否为奇数。如果不是,则没有这步操作。但是我们可以先看看从第4步到第5步的移位,很明显,在第5步的第1位bit一直为0,所以第6步和0x9908b0df异或后,第一位bit变成了1。因此可以通过这个来判断它是否与0x9908b0df异或了。

到此时,我们算出了初始的state[i]的第一个bit,还有state[i + 1]中间的30bit,我们要得到state[i+1]的最后1bit又不得不判断y是否为奇数,如果是,根据运算,state[i + 1]的最后1bit就为1,否则为0。

但是我们要算的是state[i]的值,即使得到了state[i+1]的最后31bit也没用啊。不过可以用上述的方法去求得state[i-1]的值,然后就可得到state[i]的最后31bit值,进而得到state[i]。所以可用如下算法:

for (int i = 623; i >= 0; i--) {
  int result = 0;
  // first we calculate the first bit
  int tmp = state[i];
  tmp ^= state[(i + 397) % 624];
  // if the first bit is odd, unapply magic
  if ((tmp & 0x80000000) == 0x80000000) {
    tmp ^= 0x9908b0df;
  }
  // the second bit of tmp is the first bit of the result
  result = (tmp << 1) & 0x80000000;

  // work out the remaining 31 bits
  tmp = state[(i - 1 + 624) % 624];
  tmp ^= state[(i + 396) % 624];
  if ((tmp & 0x80000000) == 0x80000000) {
    tmp ^= 0x9908b0df;
    // since it was odd, the last bit must have been 1
    result |= 1;
  }
  // extract the final 30 bits
  result |= (tmp << 1) & 0x7fffffff;
  state[i] = result;
}

 

0x04 完善

假如我们从web应用中或从其它地方得到了624个产生的伪随机数,我们就可以完全预测到它后面将会产生的数。但如果我们不能得到624个连续的数,那么我们又将怎样地决定梅森算法的内部状态呢。

我们可以通过预测第625个与服务端所产生的下一个是否相匹配来判断,如果不相等,那说明我们可能错失了一些随机数。由此,我们可以不断地预测数和从服务端提取的伪随机数来比较,慢慢地缩小范围,从而可知我们错失了哪些state。

还有个存在的问题,可能在应用中输出的随机数是不全的,我们就无法用上面的技术了。为了避免这问题,我们把输出的每一bit都当作成内部状态的线性方程组,只要有足够的输出,我们就可以通过高斯消元等方法恢复出内部状态。php的伪随机数产生器mt_rand实际上稍微改动了标准的梅森旋转算法,不过随机性更差点。可用此工具进行验证。

真正好的随机数是不会通过之前给出的随机数能预测出后面的,很明显梅森旋转算法做不到这点,它会将内部状态“泄漏”出来。

0x05 总结

综合来说,梅森旋转算法本身的设计就不是为了产生密码学上所谓的安全随机数--不可预测,但它的确是一个很好的随机算法,可足够快速地产生健壮随机数。所以,以上所述的攻击方法并不能称为是它的一个“漏洞”或“疏忽”。

但作为攻击者的角度上讲,我们可获取的伪随机数往往是有限的,如果种子seed的范围不大,比如mt_rand的自动播种seed的范围为32bit内,我们就可用爆破的方法去破解出种子,代价并不大,可控且合理。但对于其它应用给出的seed如果足够大,我们就不能使用爆破,而是想办法获取到上述讲到的符合要求的伪随机数,然后再使用逆算法进行破解。

在很多php应用中,关于找回密码所生成的token,都是有问题的,mt_rand播种的seed范围太小,实在容易被破解,不过利用起来成本较高,攻破它我们需要考虑的只是代价问题。

0x06 防范

其实在现有的php中,开发者在安全因素比重很大的地方比如csrf或密码重置处的token等等,应该尽量避免使用php提供的伪随机数。如果应用中需要生成很重要的token,那么可以使用php扩展openssl_random_pseudo_bytes(),或者使用其它较好的熵源。

没有给出实际案例,如果下次在实际遇到了好的例子再分享出来吧。- -

参考资料:

https://www.reddit.com/r/netsec/comments/1pvfmv/phps_mt_rand_random_number_generating_function/
https://jazzy.id.au/2010/09/22/cracking_random_number_generators_part_3.html
http://www.sjoerdlangkemper.nl/2016/02/11/cracking-php-rand/
http://drops.wooyun.org/tips/1060
I Forgot Your Password: Randomness Attacks Against PHP Applications
Crypto 101

 

 

 

标签:none

还不快抢沙发

添加新评论

captcha
请输入验证码

最新文章

最近回复

  • lynahex:拜大佬
  • cdxy:师傅好
  • lynahex:十分感谢解惑,特别是解决问题的方法。
  • ld:1. 搜索CVE-2016-0701 进入 https://cv...
  • lynahex:好的。
  • xdxd:友链已加~~~希望有机会多多交流~~
  • lynahex:恩,重测了下是可以的。可能当时一些危险函数被我禁掉了。 thx
  • 过客:虽然博主文章过了好久了,本地system测试还是可以执行的
  • 友情链接

    分类

    其它