随机数安全

密码学算法安全 随机数安全
密码学算法安全
发布日期:   2024-12-04
更新日期:   2024-12-04
文章字数:   2.3k
阅读时长:   9 分
阅读次数:  

一、伪随机数

1.1 伪随机数的概念

伪随机数（Pseudo-Random Number）是通过确定性算法生成的一系列数字，这些数字看似随机，但实际上是由一个初始值（种子，seed）通过特定的数学公式计算得到的。因此，伪随机数在本质上是可预测的，只要种子值和生成算法相同，输出的序列也将完全相同。

一般伪随机数分为两类：

  • 强伪随机数：难以预测的随机数
  • 弱伪随机数：容易预测的随机数（一般是漏洞高发点）

1.2 伪随机数的特点

  • 可重复性
    伪随机数的生成依赖于种子值，使用相同的种子可以生成相同的随机序列，这使得它在调试和测试中非常有用。

  • 近似随机性
    虽然伪随机数是通过确定性算法生成的，但它们在统计特性上接近真正的随机数，满足均匀分布、独立性等随机性要求，适用于大多数应用场景。

  • 效率高
    伪随机数生成通常比真随机数更快，且不依赖外部物理设备，易于在软件中实现。

1.3 真随机数与伪随机数的区别

真随机数与伪随机数的区别

二、伪随机数的安全问题

确定的算法+随机数种子=>可预测的随机数序列。

2.1 可预测性问题

2.1.1 问题描述

伪随机数生成器（PRNG）的输出依赖于种子值，一旦种子值被攻击者知道或猜测到，后续生成的所有伪随机数都可以被预测。这对密码学中的密钥生成、会话密钥等至关重要的数据是致命的。

2.1.2 实例

Linux内核的随机数预测漏洞（2016年）：由于种子熵不足，攻击者通过推测种子值预测了伪随机数，导致SSH会话密钥被破解。

2.1.3 解决方案

使用加密安全伪随机数生成器（CSPRNG）。CSPRNG通过使用安全的哈希函数、对称加密等算法，使得即使种子部分暴露，也无法预测未来的输出。

增加种子的熵（Entropy），从不可预测的物理来源获取种子，例如鼠标移动、键盘输入、系统噪声等。

2.2 周期性问题

2.2.1 问题描述

伪随机数生成器具有有限的周期，周期一旦被攻击者识别，输出的伪随机数序列就会重复。这在长时间运行的系统中会导致随机性退化，从而影响安全性。

2.2.2 实例

某些使用线性同余法（LCG）的系统在长时间运行后，其伪随机数输出进入了一个短周期，导致系统输出模式被攻击者利用。

2.2.3 解决方案

选择周期极长的PRNG，例如梅森旋转算法（Mersenne Twister, MT19937）。

结合多个随机数生成器，或在周期耗尽前重新注入新的随机熵。

三、伪随机数安全问题实例

3.1 PHP伪随机数生成

以PHP中的随机数作为示例，在PHP中，常用的两个随机数生成函数为rand()及mt_rand()。

rand()主要依赖glibc的random()，实现原理如下：

int main() {
    int r[1000];
    int i;
    r[0] = 1;
    for (i=1; i<31; i++) {
        r[i] = (16807LL * r[i-1]) % 2147483647;
        if (r[i] < 0) {
            r[i] += 2147483647;
        }
    }
    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<1000; i++) {
        r[i] = r[i-31] + r[i-3];
        printf("%d\n", ((unsigned int)r[i]) >> 1);
    }
    return 0;
}

这段代码首先初始化数组 r 的第一个元素为 1，然后通过一个线性同余生成器算法填充数组的前 31 个元素。接着，它将前 31 个元素的部分数值复制到数组的第 31 到 33 个位置。然后，从第 34 个元素开始，数组的每个元素都是前 31 个元素和前 3 个元素的和。最后，从第 344 个元素开始，程序打印出数组中每个元素的高 31 位值。这里使用了类型转换 (unsigned int) 和右移操作 >> 1 来获取高 31 位。

从中发现，当随机数多于32位时，可以对后续的随机数进行预测。

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<1000; i++) {
        r[i] = r[i-31] + r[i-3];
    }

在mt_rand函数中，可以根据mt_srand进行播种，如：

<?php
$seed = 6666;
mt_srand ($seed);
$ss = mt_rand();
?>

当随机数种子已知时，生成的随机数序列一致：

<?php
$seed = 6666;
mt_srand ($seed);
echo = mt_rand();
echo = mt_rand();
echo = mt_rand();
?>
两次运行的结果一致

两次运行的结果一致。

3.2 逆推伪随机数种子

同样的种子能生成固定的随机数，那么也能根据随机数在某种程度上逆推种子，可以通过开源工具php_mt_seed可以实现：

https://github.com/openwall/php_mt_seed 【地址】

  • 用法示例
$ php5 -r 'mt_srand(1234567890); echo mt_rand(), "\n";'
1328851649
$ time ./php_mt_seed 1328851649
    Pattern: EXACT
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xfc000000 - 0xffffffff, speed 16261.0 Mseeds/s 
    Version: 5.2.1+
    Found 0, trying 0x1e000000 - 0x1fffffff, speed 91.8 Mseeds/s 
    seed = 0x1fd65f9a = 534142874 (PHP 7.1.0+)
    Found 1, trying 0x26000000 - 0x27ffffff, speed 91.9 Mseeds/s 
    seed = 0x273a3517 = 658126103 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 2, trying 0x48000000 - 0x49ffffff, speed 91.9 Mseeds/s 
    seed = 0x499602d2 = 1234567890 (PHP 5.2.1 to 7.0.x; HHVM)
    seed = 0x499602d2 = 1234567890 (PHP 7.1.0+)
    Found 4, trying 0xfe000000 - 0xffffffff, speed 91.9 Mseeds/s 
    Found 4

由于是逆推，可能存在多值。

提供的随机数序列长度越长，逆推越精确。

3.3 实例分析

3.3.1 代码审计

以某国内赛事的题目为例讲解伪随机数安全：

function random_str($length = "32"){
    $set = array("a", "A", "b", "B", "c", "C", "d", "D", "e", "E", "f", "F",
    "g", "G", "h", "H", "i", "I", "j", "J", "k", "K", "l", "L",
    "m", "M", "n", "N", "o", "O", "p", "P", "q", "Q", "r", "R",
    "s", "S", "t", "T", "u", "U", "v", "V", "w", "W", "x", "X",
    "y", "Y", "z", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9");
    $str = '';
    for($i = 1; $i <= $length; ++$i) {
        $ch = mt_rand(0, count($set) - 1);
        $str .= $set[$ch];
    }
    return $str;
}

session_start();
$seed = rand(0,9999999999);
mt_srand($seed);
$ss = mt_rand();
$hash = md5(session_id() . $ss);
setcookie('SESSION', $hash, time() + 3600);
$filename = './up104Ds/' . random_str() . '_' . $_FILES['file-upload-field']['name'];
  • 代码审计
  1. random_str 函数：这个函数用于生成一个指定长度的随机字符串。它使用了一个包含大小写字母和数字的字符集 $set。通过循环，每次从字符集中随机选择一个字符并拼接到结果字符串 $str 中。
  2. **session_start()**：启动会话，这是 PHP 中用于管理用户会话的函数。
  3. $seed：生成一个随机种子，用于初始化随机数生成器，以确保每次生成的随机数序列都不同。
  4. **mt_srand($seed)**：使用 $seed 初始化 Mersenne Twister 随机数生成器。
  5. **$ss = mt_rand()**：使用 Mersenne Twister 算法生成一个随机数。
  6. **$hash = md5(session_id() . $ss)**：将会话 ID 和随机数 $ss 连接起来，然后使用 MD5 算法生成一个哈希值。
  7. **setcookie(‘SESSION’, $hash, time() + 3600)**：设置一个名为 ‘SESSION’ 的 cookie，其值为生成的哈希值，有效期为 1 小时（3600 秒）。
  8. $filename：构造一个文件名，该文件名由一个随机字符串和上传文件的原始文件名组成，用于保存上传的文件。

3.3.2 目标——预测文件名

文件名的组成如下：

'./up104Ds/' . random_str() . '_' . $_FILES['file-upload-field']['name'];
./up104Ds/+随机文件名+"_"+上传时的文件名

随机数的生成主要依赖于：

$ch = mt_rand(0, count($set) - 1);
$str .= $set[$ch];

3.3.3 解决思路

1）获取播种后第一次生成的随机数

$seed = rand(0,9999999999);
mt_srand($seed);
$ss = mt_rand();
$hash = md5(session_id() . $ss);
setcookie('SESSION', $hash, time() + 3600);

会话未建立时，session_id()的值为空，则$hash的值为md5(第一个随机数)

通过破解哈希值，的到第一个随机数：1608834717

2）推断种子

此时可以通过php_mt_srand反推随机数种子：

./php_mt_seed 1608834717

Found 0, trying 335544320 - 369098751, speed 49932190 seeds per second

seed = 353675865

3）推断随机数序列

mt srand(353675865);
echo mt_rand();
echo mt rand();
echo mt_rand ();
echo mt_rand();
./php mt_rand.php
1608834717
364052752
104617820
1855329673

4）预测文件名

预测出随机数序列之后，便可以预测出随机文件名的每一位，从而最终获得文件名。

最终可以绕过随机文件名防护，实现文件包含等漏洞的利用。

四、总结

伪随机数生成的安全性对许多应用至关重要，尤其是在密码学领域。为了确保伪随机数的安全性，必须考虑以下几个方面：

  1. 使用加密安全的伪随机数生成器（CSPRNG）。
  2. 增加种子熵，避免使用低熵或固定种子。
  3. 定期更新内部状态，避免周期性输出和回溯攻击。
  4. 选择高质量的算法，避免使用简单、过时的PRNG。

在高安全性场景下，建议结合硬件随机数生成器和加密安全算法，以提供更强的随机性和安全性。

文章作者: 司晓凯
文章链接: http://sxksec.cn/2024/12/04/mi-ma-xue-suan-fa-an-quan/sui-ji-shu-an-quan/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 司晓凯 !
密码学算法安全 随机数安全
赏
  目录