mt_rand 随机数安全分析 - rivir-江sir

mt_rand 随机数安全分析

  • 2017-11-26
  • 620
  • 0

mt_srand() 和 mt_rand()

mt_srand()
为mt_rand()函数播种的函数

php manual 的解释是:

mt_srand : 播下一个更好的随机数发生器种子,用 seed 来给随机数发生器播种。 没有设定 seed 参数时,会被设为随时数。

Note: 自 PHP 4.2.0 起,不再需要用 srand() 或 mt_srand() 给随机数发生器播种 ,因为现在是由系统自动完成的。

mt_rand()
生成随机数的函数

php manual的解释为:生成更好的随机数,很多老的 libc 的随机数发生器具有一些不确定和未知的特性而且很慢。PHP 的 rand() 函数默认使用 libc 随机数发生器。mt_rand() 函数是非正式用来替换它的。该函数用了 » Mersenne Twister 中已知的特性作为随机数发生器,它可以产生随机数值的平均速度比 libc 提供的 rand() 快四倍。

如果没有提供可选参数 min 和 max,mt_rand() 返回 0 到 mt_getrandmax() 之间的伪随机数。

mt_rand()函数的两种适用场景

  • 指定范围参数,比如mt_rand(1,1000)
  • 不指定范围,让系统自动生成

如果我们自己指定范围的话,如果过小则很容易被爆破出来的,因此大多实际应用中都是不指定范围, mt_rand()函数默认范围是0到 mt_getrandmax()之间的伪随机数

我们来看下mt_getrandmax()函数的最大值是多少

发现mt_getrandmax()的最大值是2**31-1的大小,也就是说随机数的范围在0x00000000~0xffffffff 之间, 在这个范围内我们是可以爆破的,我们可以爆破在0x00000000~0xffffffff 之间的种子值,匹配生成的随机数是否和我们爆破的随机数相等, 爆破的工具已经有大牛用c写了php_mt_seed的一个工具

http://www.openwall.com/php_mt_seed/

php_mt_seed

我们来看下该工具爆破0x00000000~0xffffffff爆破的过程,爆破完也就几分钟的时间

比如一个很简单的程序:

我们用php_mt_seed去爆破我们的种子,如果种子值取得小,几乎是秒破的

php_mt_rand 工具只能用于爆破mt_rand()函数产生的随机数的种子值, 无论是否显式调用mt_srand()函数播种,但不能用于mt_rand(1,1000)这种指定范围的和rand函数的爆破

常见的三种用mt_srand() 播种的情况

  • 固定种子: 比如mt_srand(1000)

这种情况如果是调用mt_rand()函数用php_mt_seed工具几乎秒破

  • 动态种子

  • 程序自动播种
    这种情况也可以分为两种情况
  1. 用mt_srand()函数,种子值随机
  2. 程序隐式调用mt_srand()函数,不再需要用户来调用mt_srand()函数

这种情况就比较复杂,也比较符合实际情况

, 但问题来了,到底系统自动完成播种是什么时候,因为是隐式调用的,如果是每次调用mt_rand()函数都会自动播种,那么破解seed也就没有意义了,这样就会变成真随机数了

我们来找对应php源码来分析下:

php_mt_srand 是播种函数,根据注释我们我们知道该程序的大概功能是先初始化一个seed, 然后调用php_mt_reload 生成N个的随机数,并赋值标志位:mt_rand_is_seeded为1, 表示已经播种的意思

php_mt_rand是生成随机数函数, 我们看到这么一段

如果没有播种,就调用php_mt_srand函数播种,那么下一次调用mt_rand()函数时就会跳过这步

因此,其实可以知道,mt_rand()函数并不是每一次调用都会都会随机播种,那么什么时候会重新播种呢? 即什么时候mt_rand_is_seeded 标志位会被初始化为0呢? 这步赋值0的操作在源码basic_functions.c中有定义, 这里不细致贴了, 即在每个新进程开始的时候会初始化一次mt_rand_is_seeded

rand()

rand() 函数在产生随机数的时候没有调用 srand(),则产生的随机数是有规律可询的.

产生的随机数可以用下面这个公式预测 : state[i] = state[i-3] + state[i-31] (一般预测值可能比实际值要差1)

可以看到只需要产生前31个随机数,后面的32-50个随机数我们都可以用前面的随机数去预测后面的随机数值

我们来看几道题, 一个是EIS 上的一道随机数的题,源码为:

srand()的种子值是动态, 而MAX_NUM 的值也是未知,不太好确定种子的范围和rand随机数的范围, 通过观察发现随机数值基本都是3位数和2位数的,没有超过4位数的, 看到有大佬们直接猜测MAX_NUM位1000, 然后去爆破即可

这样写一个php脚本然后生成一个类似彩虹表的东西, 每次生成前三个随机数,对照以下彩虹表就可以预测出来第四个随机数了, 一般误差在+1左右,

这种做法虽然有一点猜测的做法,但也是合理的, 真正MAX_NUM 确实是1000, 如果出题人改成999,那么用于生成的字典会大大增多,如果是爆破900-1100的MAX_NUM值,大概需要200*1000=20000这样大小的字典

脚本如下:

第二种做法是写一个py脚本直接去爆破随机数,因为随机数的范围都是小于1000的,因此这些直接爆破0,1000即可

大概每个session 可以爆出2,3次就无法再次爆破了,也是有一点随机性在里面的

ps: 其实session()这个函数有点像随机数播种, 程序每次运行一次session函数,都会分配一个固定的sessionid, 上面这个程序把session放在前面,那么循环部分的sessionid都是一样的,和我们浏览器访问并没有很大区别, 但如果是把session()函数放到循环体里面,那么每次访问的sessionid的值都会变化,相当于1000个人同时访问一次站点, 前面相当于一个人访问了1000次站点

下面来看一到湖湘杯的题目:

mt_srand()函数用time()做种子值, 相当于已知的, 我们可以本地用time()这个种子值去预测pwd的值, 这第一层判断很容易绕过, 第二层的判断就有点迷了

发现这个第二层的判断为if ($_SESSION['userLogin'] == $_GET['login']), 只是简单的判断了下是否相等,而没有判断$_GET[‘login’] 这个值是否为空, 因为程序如果第一次加载,那么此时$_SESSION还没有赋值,$_SESSION[‘login’] 的内容自然是空, NULL===NULL, 很容易就绕过了第二层, 因此这题第二层判断形如虚设:

如果你的时间和服务器上面的时间不同步,即time()的值不相同话,需要去偏移一个大概范围去爆破

如果这题是改成如下

那么又该如何来解呢? 我才这个题目的愿意应该也是想这样考的, 这样的话难度大大提高

rand()函数在没有调用srand()的时候产生的随机数值是可以预测的, 需要通过这个缺陷去得到$_SESSION[‘userLogin’]的值, 具体实现之后有时间会在写一篇文章来分析

参考大佬们的博客:

http://mp.weixin.qq.com/s/3TgBKXHw3MC61qIYELanJg

http://wonderkun.cc/index.html/index.php/2017/03/16/php%E7%9A%84%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%9A%84%E5%AE%89%E5%85%A8%E6%80%A7%E5%88%86%E6%9E%90/

620 views

评论

还没有任何评论,你来说两句吧