PHP中的随机数

php中常用的随机数产生函数是rand()和mt_rand()。但是生成的是伪随机数,不能应用于生成安全令牌、核心加解密key等。否则会产生一些安全问题。

何时自动播种

都知道,同一个种子产生的随机序列完全相同,因此种子在随机数中起着至关重要的地位。

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

那么问题是,php中何时会自动播种呢?如果每次调用随机数都会自动播种那么破解出种子也没有意义。

查看源码发现,每次调用mt_rand()都会先检查是否已经播种。如果已经播种就直接产生随机数,否则系统进行自动播种。也就是说每个php进程期间,只有第一次调用mt_rand()会自动播种。接下来都会根据这个第一次播种的种子来生成随机数。

那么接下来进行测试。

首先是在本地命令行:

1
$ php -r "echo mt_rand().' '.mt_rand().' '.mt_rand().' '.mt_rand();"

生成了4个随机数:272444184 1241931419 1575764393 1197993479。
那么接下来用 php_mt_seed 工具来爆破种子,此工具可以根据第一个生成的随机数来猜测可能的种子,其实就是枚举测试了。

1
$ ./php_mt_seed 272444184

一共找到了10个种子,选择自己的php版本,挨个手动播种进行测试:

1
$ php -r "mt_srand(2294193663); echo mt_rand().' '.mt_rand().' '.mt_rand().' '.mt_rand();"

发现2294193663这个种子结果完全一致。

这种方式每个进程期间共用一个种子,每个php命令行都是一个进程。如果再重复生成随机数的过程,由于不是同一个进程种子当然不一样。

那么web服务器中的php呢?由于php的运行模式、web服务器种类(apache、nginx)等不同,有可能每个进程只处理一个请求,也有可能一个进程处理多个请求之后才会被回收,当然超时也会被回收。这块查了一些资料,网上说的也不是很清楚,具体的还不是很明白。

做个测试:

开个简单的web服务,php-fpm 5.6,nginx:

1
<?php echo mt_rand().' '.mt_rand(); ?>

编写脚本,分别用两台不同出口IP的客户端访问:

1
2
3
4
5
6
7
import requests
import time
res = []
for i in range(3):
res += requests.get(url='http://xxx').text.split()
time.sleep(10)
print(res)

相差5s运行脚本,这样就可以间隔拿到随机数了。两个客户端的随机数如下:

1
2
['1063882594', '83620778', '792103107', '325549112', '409866403', '177599907']
['311111307', '285085670', '1274478122', '721750928', '260625958', '1103889931']

爆破下种子,这与3521803456这个种子的结果一致。

1
1063882594 83620778 311111307 285085670 792103107 325549112 1274478122 721750928 409866403 177599907 260625958 1103889931 1560118614 1060634432 1320660042

因此可以发现对一段时间内的请求,服务器是用同一个进程处理的。这无疑加大了rand()和mt_rand()的利用难度,使之较为安全。因为你根本不知道服务器何时会回收进程,也就不知道何时会播种,也不知道你这次请求的第一个随机数其实是播种后产生的第几个随机数,无法爆破种子。除非,网站几乎没人访问,或者夜黑风高之时。

当然某次访问如果产生第一个随机数时恰好播种,会产生极大的危险。

mt_rand()

php的mt_rand()函数是基于MT19937随机数生成算法而来。
函数原型是:mt_rand ( int $min , int $max ) : int
如果没有提供可选参数 min 和 max,mt_rand() 返回 0 到 mt_getrandmax() 之间的伪随机数。
如果设定范围,php5和php7的算法稍有不同:
php5:

1
2
3
4
5
6
7
8
int RAND_RANGE(__n, __min, __max, __tmax) {
(__n) = (__min) + (long) ((double) ((double) (__max) - (__min) + 1.0) * ((__n) / ((__tmax) + 1.0)));
}

number = (long) (php_mt_rand(TSRMLS_C) >> 1);
if (argc == 2)
RAND_RANGE(number, min, max, PHP_MT_RAND_MAX);
RETURN_LONG(number);

而php7为:(php_mt_rand() % (max-min+1)) + min

现在php_mt_seed最新版4.0对两种算法都已支持。直接爆破种子即可。

顺便一提,php_mt_seed工具中存在范围和未知随机数的使用方式。
假设有这样10个带范围的随机数,前2个随机数未知:

1
2
3
4
5
6
7
8
9
<?php
mt_srand(0x8fffffff);
mt_rand(200, 2000).', ';
mt_rand(100, 1000).', ';
for ($i=0; $i<4; $i++) {
echo mt_rand(200, 2000).', ';
echo mt_rand(100, 1000).', ';
}
?>

得到:
1005, 230, 1780, 514, 885, 486, 926, 713
那么可以这样写命令:

1
$ ./php_mt_seed 200 2000 200 2000 100 1000 100 1000 1005 1005 200 2000 230 230 100 1000 1780 1780 200 2000 514 514 100 1000 885 885 200 2000 486 486 100 1000 926 926 200 2000 713 713 100 1000

每个随机数都包括四个参数,实际最小值,实际最大值,范围最小值,范围最大值。如果随机数已知,那么实际最小值和实际最大值相同,就是实际值。如果未知,那么实际最小值和实际最大值可以是范围最小值和范围最大值,也可以是0,0。但貌似不能混用。

rand()

php7中的rand()同mt_rand(),srand()同mt_srand()。

php5 中的rand函数调用的是glibc中的random()。其实现算法可以简化为如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#define MAX 1000
#define seed 1
#define PHP_RAND_MAX 2147483647

int main() {
int r[344+MAX];
int i;
r[0] = seed;
for (i=1; i<31; i++) {
r[i] = (16807LL * r[i-1]) % PHP_RAND_MAX;
if (r[i] < 0) {
r[i] += PHP_RAND_MAX;
}
}
for (i=31; i<34; i++) {
r[i] = r[i-31];
}
for (i=34; i<344; i++) {
r[i] = r[i-31] + r[i-3];
}
for (i=344; i<(MAX+344); i++) {
r[i] = r[i-31] + r[i-3];
printf("%d\n", ((unsigned int)r[i]) >> 1);
}
return 0;
}

r[344]就是生成的第一个随机数。
设定范围的算法与php5中mt_rand()的设定范围的算法相同。

爆破种子

rand()函数要爆破种子没有现成的工具用,因此我自己根据rand()的算法写了一个多进程的脚本用,C很久没写了,勉强能用。8核CPU爆破完需要大约15分钟。
MAX_POOL是进程数,PHP_RAND_MAX是getrandmax()获得的随机数的最大值,Linux下是2147483647,Windows下是32767。res是取了范围后的随机数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdlib.h> 
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>

#define MAX_POOL 8
#define MIN 10
#define MAX 2000
#define PHP_RAND_MAX 2147483647

static int res[] = {1803, 1415, 1733, 1069, 760, 344, 1232, 137};
static int count = (int)(sizeof(res) / sizeof(res[0]));

int is_eq(int i, int x);
int get_data(unsigned int seed);
int RAND_RANGE(int __n, int __min, int __max, int __tmax);

int is_eq(int i, int x) {
if (x == res[i])
return 1;
else
return 0;
}

int get_data(unsigned int seed) {
int r[count+344];
int i;
r[0] = seed;
for (i=1; i<31; i++) {
r[i] = (16807LL * r[i-1]) % PHP_RAND_MAX;
if (r[i] < 0) {
r[i] += PHP_RAND_MAX;
}
}
for (i=31; i<34; i++) {
r[i] = r[i-31];
}
for (i=34; i<344; i++) {
r[i] = r[i-31] + r[i-3];
}
for (i=344; i<(count+344); i++) {
r[i] = r[i-31] + r[i-3];
int ans = ((unsigned int)r[i] >> 1);
ans = RAND_RANGE(ans, MIN, MAX, PHP_RAND_MAX);
if (!is_eq(i-344, ans))
return 0;
}
printf("======== find seed %u ========\n", seed);
return 1;
}

int RAND_RANGE(int __n, int __min, int __max, int __tmax) {
int x = (__min) + (long) ((double) ( (double) (__max) - (__min) + 1.0) * ((__n) / ((__tmax) + 1.0)));
return x;
}

int main(int argc, char const *argv[]) {
pid_t pid;
int i;
for (i=0; i<MAX_POOL; i++) {
pid = fork();
if (pid != 0)
break;
}
if (pid == -1) {
printf("Process %d fork error\n", i);
}

if (pid == 0) {
printf("ParProcess working. Pid=%d.\n", getpid());
}
else {
printf("SubProcess %d working. Pid=%d.\n", i, getpid());
unsigned int every = (unsigned int)(0xffffffff / MAX_POOL);
for (unsigned int start=i*every; start<0xffffffff && start<(i+1)*every; start++) {
get_data(start);
if ((start % 20000000) == 0) {
double t = start - i*every;
printf("Process: %d %.2f\%\r", i, t/every*100);
fflush(stdout);
}
}
}
return 0;
}

找到了一个种子:3381418098

一个规律

从rand函数的生成算法入手,其实是有规律的。由于r[i] = r[i-31] + r[i-3],如果同一种子连续生成了31个随机数,那么之后的随机数是可以预测的,尽管由于位移和设定范围时的算法影响。至于到底 r[i] 和 r[i-31] + r[i-3] 有什么规律,这一点网上的文章目前没有一篇说的清楚,因此自己尝试:

首先用同一种子随机生成10到10000的100万个随机数:

1
<?php for($i=0; $i<1000000; $i++) { echo rand(10, 10000).' ';} ?>

1
$ php -f t.php > res.txt

用python编写脚本读取数据,统计 r[i]+r[i+28]r[i+31] 的差值,看有什么规律:

1
2
3
4
5
6
7
8
9
NUM = 1000000
data = [int(x) for x in open('res.txt').read().split()]
save = {}
for i in range(NUM-31):
t = data[i] + data[i+28] - data[i+31]
save[t] = save[t]+1 if t in save else 1
print(save)

# {10001: 249677, 10: 250196, 10000: 249970, 9: 250126}

惊讶的发现,r[i] + r[i+28] - r[i+31] 的值肯定是 min、max、min-1、max+1 中的一个,并且概率相等。
更进一步,其实预测一个随机数时,只可能有两种情况,差值要么是min或min-1,要么就是max、max+1,这是由于移位时的误差,不会同时存在四种情况。
现在模拟预测一下,编写脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
MIN = 10
MAX = 10000
NUM = 1000000
possible = (MIN, MAX, MIN-1, MAX+1)
data = [int(x) for x in open('res.txt').read().split()]
for i in range(31, NUM):
ans = []
for x in possible:
tmp = data[i-3] + data[i-31] - x
if MIN <= tmp <= MAX:
ans.append(tmp)
if (data[i] not in ans) or (len(ans) != 2):
print(data[i], ans)

没有输出任何结果,预测正确。
至于这之间更严密的数学推导,限于姿势水平,就不做了。

因此,如果要向后预测 n 位,现在将可能结果减小到了 2^n 个。用 python 写了个预测脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Node(object):
def __init__(self, data=0, parent=None, lchild=None, rchild=None):
self.data = data
self.parent = parent
self.lchild = lchild
self.rchild = rchild

class BTree(object):
def __init__(self, data=None):
self.head = Node(data)
self.leaves = self.head

if __name__ == '__main__':
strs = "QWERTYUIOPASDFGHJKLZXCVBNM1234567890qwertyuiopasdfghjklzxcvbnm"
rand_str = "N34sgD93L32HrROKJ9B6Rpzt6YvbHqE"
MIN = 0
MAX = 61
N = 10
possible = (MIN, MAX, MIN-1, MAX+1)
num = [strs.find(x) for x in rand_str]
assert len(rand_str) >= 31
print(num)

tree = BTree(num[0])
for i in range(1, len(num)):
tmp = tree.leaves
tree.leaves = Node(num[i], tmp)
tmp.lchild = tree.leaves

tree.leaves = [tree.leaves]
for i in range(N):
leaf = []
for node in tree.leaves:
tmp = node
for j in range(30):
tmp = tmp.parent
if j == 1:
a = tmp.data
if j == 29:
b = tmp.data
for posb in possible:
tmp = a + b - posb
if MIN <= tmp <= MAX:
if node.lchild == None:
node.lchild = Node(tmp, node)
else:
node.rchild = Node(tmp, node)
leaf.append(node.lchild)
leaf.append(node.rchild)
tree.leaves = leaf

save = []
for node in tree.leaves:
tmp1 = []
tmp2 = node
for i in range(N):
tmp1.append(tmp2.data)
tmp2 = tmp2.parent
ans = ''
for i in tmp1[::-1]:
ans += strs[i]
save.append(ans)

for x in save:
print(x)

例子

参考