熵不起得随机数

0x00 前言

2龙好早以前说，能不能把这篇文章翻了，我拿到文章一看，有点意思，但是很多东西我不清楚，然后在维基百科上看了一些关于Entropy（熵）和PRNG（伪随机生成器）和RNG（随机数生成器）的文章，很拖沓，坑却越挖越大，今天打算跟随原文的过程的说一下这篇文章所说到的事情，但是不是完整的翻译。

直到我看完之后才想起来，这个事情Superhei曾经在Discuz的代码里也提出过：http://www.80vul.com/dzvul/sodb/14/sodb-2008-14.txt，也是：http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/。

文章里出现一个Entropy（熵），我这里引用一下wikipeida中文的一段话来解释下这个东西。

英语文本数据流的熵比较低，因为英语很容易读懂，也就是说很容易被预测。即便我们不知道下一段英语文字是什么内容，但是我们能很容易地预测，比如，字母e总是比 字母z多，或者qu字母组合的可能性总是超过q与任何其它字母的组合。如果未经压缩，一段英文文本的每个字母需要8个比特来编码，但是实际上英文文本的熵 大概只有4.7比特。

接下来是文章，总体来说：能力有限，如存在错误，请多多指出。 注：文章内token,salt,nonce，PRNG,RNG这些缩写我只注了一次，而seed有些地方写成了随机数种子，有些地方写了seed。

0x01 细节

随机值在PHP中很常见，在框架内或者类库中你都可能看到用它生成的token（令牌），salt（盐值），这些都被当做一种输入放到对应的函数内，随机数很常见很常用。

生成一个范围内的随机数，一个随机的用以加密的密匙，一个不可以被猜测到的可用于验证用户权鉴的字符，生成一个sessionid什么的，我们都会用到随机。

但是这些使用中都存在一个隐患，如果攻击者可以预测你用RNG（随机数生成器）或者PRNG（伪随机数生成器）生成的随机结果会是什么，那他也差不多能知道你最后生成token是什么，或者nonce（一次性验证的凭证）是什么，所以，好的随机数必须是不可以被预测到得随机数。

但是作者认为，在PHP内存在两个关于随机数的弱点：

1，信息泄露。
2，熵池不足。

信息泄露的意思是，在随机数生成过程中能泄露过程中的一些东西，例如伪随机数种子的值，有了这个随机数的结果也可以更简单的获取到。

熵池不足的意思是，随机数初始的内部状态或者随机数种子的组成的成分就很有限，大概就在一个范围内，PRNG生成的结果也就在一个可能猜到的范围内。

两个对PHP编写的代码来说，都不算好消息。

什么产生了随机值呢？

很多人都搞不清楚什么是随机值，可能有些人觉得用unique产生的值和其他随机数比的话，前者更安全一点，后者可能很容易就获取到了，我实际上不认同这个。

关于随机数的讨论应该基于目的，如果你期望使用的随机数是不可被预测的，重要的，那你的随机数就应该不可被预测。

影响随机数的强度的是生成用的熵，熵简单来说是到字节的不确定性，举个例子，我拿出个2进制的字符，它就包含0和1，如果攻击者什么都不知道，好，我们的熵是2，如果攻击者知道结果一定是1，我们的熵就是0比特了，因为能否预测这个需求是和不确定性相反的。

这个在PHP里比较明显，mt_rand生成的随机值永远只是数字，它不输出字符串，特殊字符什么的，所以攻击者只需要尝试数字，如果我们使用/dev/random来生成随机数会比前者的熵池更大。

而且，mt_rand不是真的随机数生成器，它是PRNG（伪随机生成器），采取的是一种被称为梅森旋转的算法，用以生成高质量的伪随机数，它会采用随机数种子来生成随机数的值。

你可以本地测试一下下面的代码

#!php
mt_srand(1361152757.2);

for ($i=1; $i < 25; $i++) {
    echo mt_rand(), PHP_EOL;
}

产生的随机数看上去是不是很正常，也没什么问题，你再运行一次你会发现结果还是一样的，这不保证在PHP的版本变化后还是如此，但是在过去流行的版本里，是这样的。 如果攻击者可以获取随机数种子，他就可以预测用梅森旋转算法生成的mt_rand的值。 这个特性让随机数种子变成了能否预测的关键。

在PHP内的随机数

PHP使用的三种PRNG算法，所以如果攻击者可以获取随机数种子，那么就知道对应算法的结果。

1，线行同余方法 例如：lcg_value
2，梅森旋转算法 例如 mt_rand
3，原生C语言支持的函数 例如rand

以上实际上在内部函数也复用了，例如array_rand，uniqid，也就是说攻击者如果可以跑一遍所有可能的随机数种子，那么以上所有的值它都可以获取。

为了生成可靠的随机数，PHP也使用外置的熵池，比如openssl_pseudo_random_bytes() 使用Linux系统上的/dev/urandom，或者mcrypt_create_iv()使用了Windows上使用了CSPRNG（Windows密码安全伪随机数生成器），但是这取决于OpenSSL和Mcrypt扩展在PHP里没有开。 /dev/urandom其实也是个PRNG，但是它使用/dev/random 产生高熵池难以预测的种子。

这些告诉我们：

如果需要不被预测的随机数，你的选择是使用openssl_pseudo_random_bytes()，你可以退而设置MCRYPT_DEV_URANDOM使用mcrypt_create_iv()，你也可以直接读/dev/urandom，如果失败了，你也没有别的选择了，你只能反复使用现有的随机数或者密匙进行混合。

理论就是这样，我们来看看我们如何利用知识去实践。

攻击PHP的RNG

在实践中，PHP的PRNG都用于各种非常重要的地方。

openssl_pseudo_random_bytes()函数只在PHP5.3提供，并且在5.3.4以上的windows上才有，PHP也是在那个版本在Windows上支持mcrypt_create_iv()函数，基于此Windows只支持MCRYPT_RAND影响着rand函数的值，所以5.3之前的有很多应用可能没有较强的随机数生成器。

想想我们在线的服务，使用了下面的代码：

$token = hash('sha512', mt_rand());

好，一步一步来黑了它。 该脆弱应用的特性： 这不是详细的特性，脆弱特性可以和这份列表有不少出入。

1. 这个服务器使用mod_php，允许keepalive时多请求被同一个PHP进程处理。

这是很重要的，每个php进程的种子只会生成一次，如果我们可以对一个PHP进程发送两次请求，PHP会使用同一个种子。

2. 这个服务器存在CSRF token，密码重置或者者账户确认链接，它们都是使用了mt_rand生成的token。

为了猜测随机数种子，我们需要一个PHP生成的随机数，无论是mt_rand的结果还是再进行了一下哈希运算，最主要的是要和第二步我们猜测下一个随机数在同一个进程。

3. 知道一个脆弱的token生成算法

如果你在攻击一个开源应用你是可以知道这些的，或者收买一个雇员以获取私有的代码，或者前雇员，或者，你自己完全的猜测它的算法，有些token生成算法是简单又粗暴，有可能是mt_rand()或者md5一下mt_rand()，我在这里是假设使用SHA512，接下来我们会看到它也解决不了问题。

开始攻击

我们的攻击非常简单，我们要发送两个请求到PHP，服务器会keepalive并且接受第二个请求，接下来我们叫它们为请求A和请求B，获取A请求中的token，比如CSRF token，比如密码重置token，这个token将被严刑拷打，直到它供出它妈是谁，哦，不，它的seed是什么。

B请求更有趣了，让我们提交一个请求去重置管理员的密码，逻辑呢？逻辑是它们是同一个妈生的，哦不，同一个seed生成的(A请求的同一个进程，我们keepalive了）。我们解开A请求里的token的seed的时候，我们就可以用这个seed生成管理员重置密码的链接，并且点击它。

以下条件要在这次攻击里满足：

1，使用请求A去获取一个token，这个token我们可以推出seed的值。
2，使用请求B去拥有一个同样算法生成后放在应用数据库内用以修改密码的的token。
3，破解SHA512获取这个随机数被服务器加密之前的数是什么。
4，使用这个随机数我们去暴力破解出来这个随机数的seed是什么。
5，使用这个seed生成一个用以密码重设的token值。
6，使用我们的密码重设token去重设管理员的密码
7，获取管理员的账户玩一下。

好，我们开始吧

一步一步的来

第一步：发起请求A获取token

我目标的token和密码重设的token都依赖于mt_rand的输出，在我们的例子里，这是一个虚构的应用，它生成的token都是使用统一方案生成的，我们只需要找到CRSF的token并且存在哪里一会儿用。

第二步：发起请求B获取一个给管理员的密码token

这个请求就是很简单的提交一个密码重设的表单。这个token会存在数据库里发给用户一个email，这个token要能算出来，如果服务器的特性符合要求，这个请求会和请求A是同一个PHP进程处理的，因此能确认两个请求都使用了mt_rand去调用了同一个随机数种子。

第三步：破解请求A获取的SHA512后的token的原文

SHA512开发者们都比较敬畏，因为它是SHA-2家族的算法里目前最大的数字。但是无论如何来说，我们的目标使用它存在一个缺陷 - “随机值都只是数字” （也就是说它的不确定性或者说熵池，太弱了）。如果你去看mt_getrandmax()的返回值，你会发现mt_rand()返回的最大的数字也只是20亿1千4百7十万种组合。这种级别的数字你还是可以暴力破解的。

别这么快就听信我的话。如果你有最近代的低阶GPU。当我打算找出一个hash的值的时候，我选择专业的hashcat-lite。这个版本的hashcat是目前最快的暴力破解的工具之一，你可以在这里下载：http://hashcat.net/oclhashcat-lite/

Generate a token using the method I earlier prescribed using the following script: 用下面的脚本生成一个我刚才说到的token：

#!php
$rand = mt_rand();
echo "Random Number: ", $rand, PHP_EOL;
$token = hash('sha512', $rand);
echo "Token: ", $token, PHP_EOL;

这模仿我们从请求A能获取的那个SHA512后的hash，并且接下来我们把它放在hashcat里跑一下。

./oclHashcat-lite64 -m1700 --pw-min=1 --pw-max=10 -1?d -o ./seed.txt <SHA512 Hash> ?d?d?d?d?d?d?d?d?d?d

这是所有的参数的意思

-m1700: 定义hash的算法，1700的意思就是SHA512
-pw-min=1 定义hash加密之前的数字的最小的长度
-pw-max=10 定义hash加密之前数字的最大的长度
-1?d 定义我们自定义的字典是仅包含数字
-o ./seed.txt 输出的文件会被重写，别忘了不会有输出在屏幕上。
?d?d?d?d?d?d?d?d?d?d: 表示格式，最长10位，全是数字。

如果一切顺利，你的GPU也没有爆炸，hashcat几分钟内会找出随机数hash之前的原文是什么，是的，是几分钟，我先前花了一些时间去解释熵池是怎么工作的，然后你现在就可以在练习中明白，mt_rand()产生结果的可能性是如此的少，以至于SHA512加密后我的所有结果我们很短一段时间就计算结束了，使用hash去处理mt_rand的结果几乎没有什么用。

关于hashcat的一些其他用法可以参考之前drops的文章：GPU破解神器Hashcat使用简介

第四步：通过我们获取的随机数去恢复随机数种子

我们上面说到了，SHA512后的数字解出来只需要几分钟。这会告诉你接下来干什么，通过这个随机数，我们接下来要在跑一个脚本来暴力破解，这个工具叫做php_mt_seed。这是一个小工具，它的作用是取出mt_rand的结果并且暴力破解定位哪些随机数种子会生成那个我们刚才获取的随机数，你可以在http://download.openwall.net/pub/projects/php_mt_seed/下载对应的版本，如果出现问题的话，你可以选择一个老一点的版本（最新的版本在我在虚拟环境里测试的时候有些问题）。

./php_mt_seed <对应的随机数>

这要花比算SHA512要长的时间。它烧的是CPU，不过它会在CPU上尝试任何可能的随机数种子，这将会出现一个或多个随机数种子（也就是这些随机数种子都能产生这个数字）。

在上一步，我们暴力破解获取这个随机数的种子，因为mt_rand调用的种子数不多，这里有另外一个使用python编写的暴力破解mt_rand的工具：https://github.com/GeorgeArgyros/Snowflake

第五步：生成可用的token来尝试重置管理员的密码

Assuming that the total calls to mt_rand() across both Request A and Request B were just two, you can now start predicting the token with the candidate seeds using:

假设在请求A和请求B中调用mt_rand的最大次数是两次，接下来你可以使用我们获取的seed们（有候选的）来预测下一个token是什么。

#!php
function predict($seed) {
    /**
     * Seed the PRNG
     */
    mt_srand($seed);
    /**
     * Skip the Request A call to the function
     */
    mt_rand();
    /**
     * Predict and return the Request B generated token
     */
    $token = hash('sha512', mt_rand());
    return $token;
}

这个函数会返回对应的seed返回的下一个token。

0x02 附录

参考资料： 原文： http://phpsecurity.readthedocs.org/en/latest/Insufficient-Entropy-For-Random-Values.html#mcrypt_create_iv()/dev/random

Entropy 熵 http://en.wikipedia.org/wiki/Entropy http://zh.wikipedia.org/wiki/%E7%86%B5_%28%E4%BF%A1%E6%81%AF%E8%AE%BA%29

梅森旋转算法： http://en.wikipedia.org/wiki/Mersenne_twister http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95

PRNG 伪随机数生成器 http://en.wikipedia.org/wiki/PRNG

RNG 随机数生成器 http://en.wikipedia.org/wiki/Random_number_generator http://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8