随机数问题

前言

在 CTF 比赛中，有些时候可能会考一些关于 随机数的问题，其实考察的是两个函数，即 mt_rand() 和 mt_srand()。

前者用于生成随机数，后者则用于给随机数发生器播种。

函数的认识

mt_rand()

mt_rand — 通过梅森旋转（Mersenne Twister）随机数生成器生成随机值

参数 作用
min 可选的、返回的最小值（默认：0）
max 可选的、返回的最大值（默认：mt_getrandmax()）

具体参考：https://www.php.net/manual/zh/function.mt-rand.php

示例：

1
2
3
4
5
6
7
<?php 
echo mt_rand() . " ";
echo mt_rand() . " ";
echo mt_rand() . " ";
echo mt_rand() . " ";
echo mt_rand() . " ";
?>

程序运行结果：

image-20240218164012437

可以看到，每次程序运行得到的结果都不一样，那么有没有方法，让其每次运行得到的结果一样呢？答案是有的，那就是通过随机数种子，计算机本身无法实现真正的随机，而是通过某个种子进行计算之后得到的所谓伪随机值。

在 PHP 中使用的种子函数为：mt_srand()。

mt_srand()

mt_srand — 播下一个更好的随机数发生器种子

参数 作用
seed 用线性同余生成器生成的值填充状态，该生成器使用解释为无符号 32 位整数的 seed 进行播种。如果省略 seed 或为 **null**，则将使用随机无符号 32 位整数。
other 其他参数省略

详细请参考：https://www.php.net/manual/zh/function.mt-sran

示例：

1
2
3
4
5
6
7
8
<?php 
mt_srand(1234);   // 种子: 1234
echo mt_rand() . " ";
echo mt_rand() . " ";
echo mt_rand() . " ";
echo mt_rand() . " ";
echo mt_rand() . " ";
?>

程序运行结果：

image-20240218164612901

由于种子为 1234，每次程序运行使用相同的算法对 1234 进行运算。故而每次程序运行的结果都是一样的。

结论：

PHP 版本相近、种子一致，得到的随机数也一致。

例题-1

以下例题来自：Ctfshow web入门 暴破 web24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<?php
error_reporting(0);
include("flag.php");
if(isset($_GET['r'])){
    $r = $_GET['r'];
    mt_srand(372619038);
    if(intval($r)===intval(mt_rand())){
        echo $flag;
    }
}else{
    highlight_file(__FILE__);
    echo system('cat /proc/version');
}
?>

mt_srand() 函数的作用是播下一个更好的随机数发生器种子，当有了随机数种子的时候，那么每次运行得到的随机数也是固定的。

比如种子 372619038 得到固定随机数为 1155388967（当然可能PHP的版本有所差异，题目是PHP7.3的版本）

image-20231018164138215

这里我们本地使用 PHP7.2 进行测试得到的随机数为 1155388967，测试代码如下：

1
2
3
4
<?php 
mt_srand(372619038);
echo mt_rand(); // 1155388967
?>

image-20231018164257819

例题-2

以下例题来自：Ctfshow web入门 暴破 web25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
error_reporting(0);
include("flag.php");
if(isset($_GET['r'])){
    $r = $_GET['r'];
    mt_srand(hexdec(substr(md5($flag), 0,8)));
    $rand = intval($r)-intval(mt_rand());
    if((!$rand)){
        if($_COOKIE['token']==(mt_rand()+mt_rand())){
            echo $flag;
        }
    }else{
        echo $rand;
    }
}else{
    highlight_file(__FILE__);
    echo system('cat /proc/version');
}
?>

源码解读如下：

image-20231018215847154

由于种子是由 FLAG 的md5值，截取前8位转为十进制生成的，我们并不知道随机数种子是多少，因此这里需要使用php_mt_seed进行种子爆破。

首先我们先传入?r=0 会得到一个负的随机数

image-20231019185524562

1
2
# 当我们传入 ?r=0 的时候，此时获得的随机数 192346317
$rand = intval($r)-intval(mt_rand());

我们通过生成的随机数暴破出随机数种子，这里需要使用到 php_mt_seed 工具。

工具的安装地址：https://github.com/openwall/php_mt_seed

image-20231018221853368

通过在服务器的响应头中发现服务器的PHP版本为：php7.3

image-20231018222411323

接着使用 php_mt_seed 工具根据第一次生成的随机数枚举出 种子，我这里第一次生成的随机数为 192346317，

image-20231019185759780

由于服务器的PHP版本为 php7.3 因此我们这里得到的种子十进制为 1142351452，十六进制为 0x4416e65c，这里得到了随机数的种子。

这里我们准一个 PHP7+ 的环境，运行如下代码（模拟服务器生成随机数）：

1
2
3
4
5
<?php 
mt_srand(1142351452);
mt_rand(); // 服务器第一次生成随机数
echo mt_rand()+mt_rand(); // 服务器第二次生成随机数 将两次生成随机数的结果相加 即可得到服务器生成的随机数
?>

以上源码运行之后得到 2274592836，因此题目的mt_rand()+mt_rand()的结果为 2274592836。

题目源码：

1
2
3
if ($_COOKIE['token'] == (mt_rand() + mt_rand())) {
    echo $flag;
}

添加Cookie属性 token 字段值为：2274592836，并传入参数r其值为 192346317

image-20231019190037702

这里为什么传入r=192346317呢，观察如下代码：

1
2
3
4
5
6
7
8
9
10
11
<?php
# 第一次随机出来的值为 192346317, 当我们传入?r=192346317 - 第一次随机生成的值 = 0
$rand = intval($r) - intval(mt_rand());
// 这里只有$rand值为0的时候才会走if里面
if ((!$rand)) {
    if ($_COOKIE['token'] == (mt_rand() + mt_rand())) {
        echo $flag;
    }
} else {
    echo $rand;
}

例题-3

以下例题来自 GWCTF 2019 web 枯燥的抽奖 题目地址

DockerFile 项目地址：https://github.com/gwht/2019GWCTF/

访问题目出现如下页面：

image-20240218220337417

这里我们随便输入，点击提交，接着页面返回 “没抽中哦，再试试吧”。

image-20240218220447430

这里有个 小细节，点击提交，页面并没有刷新，这种情况只有两种可能，第一种 纯前端操作 第二种 通过 Ajax 发送请求。

我们右键查看前端代码：

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
$(document).ready(function() {
    $("#div1").load("check.php #p1");
    $(".close").click(function() {
        $("#myAlert").hide();
    });
    $("#button1").click(function() {
        $("#myAlert").hide();
        guess = $("input").val();
        $.ajax({
            type: "POST",
            url: "check.php",
            data: "num=" + guess,
            success: function(msg) {
                $("#div2").append(msg);
                alertmsg = $("#flag").text();
                if (alertmsg == "没抽中哦，再试试吧") {
                    $("#myAlert").attr("class", "alert alert-warning");
                    if ($("#new").text() == "") $("#new").append(alertmsg);
                } else {
                    $("#myAlert").attr("class", "alert alert-success");
                    if ($("#new").text() == "") $("#new").append(alertmsg);
                }
            }
        });
        $("#myAlert").show();
        $("#new").empty();
        $("#div2").empty();
    });
});

通过查看 JS 代码可以发现，这里是显然是通过 Ajax 发送 POST 请求到 check.php 文件。其传参值为：num=猜数字输入的值。

直接访问 check.php 文件，得到文件源码。

image-20240218221058297

对关键代码进行审计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
session_start();
$_SESSION['seed']=rand(0,999999999);
// 随机数种子为rand()函数随机生成的值
mt_srand($_SESSION['seed']);
$str_long1 = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
$str='';
$len1=20;
for ( $i = 0; $i < $len1; $i++ ){
    // 从str_long1随机取出20位
    $str.=substr($str_long1, mt_rand(0, strlen($str_long1) - 1), 1);       
}
# 将前10位作为一不小心偷看的部分输出到前端  我这里为: bF01Kk2aBz
$str_show = substr($str, 0, 10);
echo "<p id='p1'>".$str_show."</p>";

综上所述，我们知道了前10位，取到的随机值为 bF01Kk2aBz，那么我们编写脚本，获取每次生成的随机值：

1
2
3
4
5
6
7
8
str1 = 'abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
str2 = 'bF01Kk2aBz'

for i in str2:
    for j in range(0, len(str1)):
        if (i == str1[j]):
            print(j,end=" ")
            break

image-20240218224242377

但是这种数据，php_mt_seed 是不认识的，故而我们需要将其转为 php_mt_seed 能识别的随机数数据：

1
2
3
4
5
6
7
8
9
str1 = 'abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
str2 = 'bF01Kk2aBz'
res = ''
for i in str2:
    for j in range(0, len(str1)):
        if (i == str1[j]):
            res += str(j) + ' ' + str(j) + ' ' + '0' + ' ' + str(len(str1) - 1) + ' '
            break
print(res)

运行得到如下数据：

1
1 1 0 61 41 41 0 61 26 26 0 61 27 27 0 61 46 46 0 61 10 10 0 61 28 28 0 61 0 0 0 61 37 37 0 61 25 25 0 61

将其使用 php_mt_seed 暴破出随机种子即可。

image-20240218225014361

最终暴破出了 服务器的 PHP 版本为 7.1.0 +，其随机种子为：7937658，最后使用相同的代码，即可生成正确的字符串。

1
2
3
4
5
6
7
8
9
<?php
mt_srand(7937658); // 设置随机数种子
$str_long1 = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
$str='';
$len1=20;
for ( $i = 0; $i < $len1; $i++ ){
    $str.=substr($str_long1, mt_rand(0, strlen($str_long1) - 1), 1);       
}
echo $str;

运行得到：bF01Kk2aBzArx0IjGi2a，传入即可得到 FLAG。

image-20240218225306870

例题-4

考点：无需暴破还原 mt_rand() 种子

题目源码如下：

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
<?php 
session_start();
include("flag.php");
if ($_SESSION['init'] !== 1) {
    $_SESSION['init'] = 1;
    $_SESSION['key'] = rand();
}
$current = intval(time());
$str = '';
// 每3秒刷新一次
if ($current % 3 == 0) {
    $_SESSION['key'] = rand();
}
mt_srand($_SESSION['key']);
mt_rand();
mt_rand();
if (isset($_GET['num']) && is_numeric($_GET['num'])) {
    for($i=0;$i<intval($_GET['num']);$i++) {
        $str .= mt_rand() . " ";
    }
}
if ($_POST['key'] === strval($_SESSION['key'])) {
    echo $flag;
}
show_source(__FILE__);
if ($str != '') {
    echo "<p>{$str}</p>";
}
?>

根据代码的功能可以发现，种子由 rand() 函数随机生成存储到$_SESSION['key']，并且每3秒进行更新，重新生成。

以下代码的作用，就是生成 N 个 的随机数

1
2
3
4
5
6
7
8
if (isset($_GET['num']) && is_numeric($_GET['num'])) {
    for($i=0;$i<intval($_GET['num']);$i++) {
        $str .= mt_rand() . " ";
    }
}
if ($str != '') {
    echo "<p>{$str}</p>";  // 将生成N个的随机数输出到页面
}

image-20240219124643864

那么虽然我们知道其随机数，理论上来讲可以通过 php_mt_seed 工具进行暴破（**但是由于 php_mt_seed 是通过第一次 mt_rand() 生成的随机值进行暴破随机 **），而本道题进行了两次 mt_rand() 才输出了第三次随机的随机数。如下：

image-20240219145453034

因此我们拿到的第一个值，则是第三次随机的数，又因为每3秒刷新一次，使用 php_mt_seed 暴破则需要时间，故而该方法不可行。

这里的知识点涉及到：无需暴破还原 mt_srand() 种子

直接来看详细请移步文章：

1、从mt_rand()获取2个值：R000以及R227，中间间隔226个值；此外还需知道R000之前已生成的值的个数（用i表示）；

2、根据这些值算出加扰状态值；

3、异或这些状态值，推测出原始的状态值（s228）；

4、根据s228，推测出s0，获取种子。

无需暴破还原 mt_srand() 种子脚本：https://github.com/ambionics/mt_rand-reverse

image-20240219150236390

接着我们使用 reverse_mt_rand.py 进行计算种子：

1
2
3
4
5
python3 reverse_mt_rand.py 824793744 1480482850 123 1
# 824793744 为第124次 mt_rand() 得到的值
# 1480482850 则是往后间隔226次得到的值
# 123 表示 在 824793744 之前生成了多少次 mt_rand()
# 1 表示 版本是 PHP 7+ ，0 则表示是 PHP5+

image-20240219150341071

最终计算出种子为 11570033。知道用法之后，我们来看题。

先传入 ?num=228 生成 228 个随机数：

image-20240219150910461

接着取第一个作为 R000 最后一个 作为 R227 中间间隔为 226，刚好 228 个。最后使用脚本进行计算：

image-20240219151109579

最终得到种子为：1909862726，其中的 2 表示在 1070335843 产生之前，已生成随机值的个数，可以从下图中看到：

image-20240219151230119

通过响应头，得到 PHP 版本为，因此拼接为 0。

image-20240219151350574

image-20240219151259226

但是由于，每秒刷新一次随机种子，故而需要编写脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import requests
import re
import os
url = 'http://120.48.128.24:8080/?num=228'
request = requests.session()

for i in range(1,10):
    req = request.get(url)
    num = re.findall('<p>(.*?)</p>', req.text)
    num = num[0].strip().split(' ')
    key = os.popen(f'python3 reverse_mt_rand.py {num[0]} {num[227]} 2 0').read().strip()
    data = {
        "key": key,
    }
    req2 = request.post(url='http://120.48.128.24:8080/', data=data)
    if ("flag{" in req2.text):
        print(req2.text)
        break

脚本运行结果：

image-20240219151555665

最终得到 FLAG。