mt_rand 伪随机数攻击总结

前言

最近同事发现验证码接口在短时间内出现两个相同的验证码的神奇情况。
从代码中得知验证码是通过 mt_rand() 生成的随机数，遂开始了解 mt_rand() 的安全性。

伪随机数漏洞

mt_scrand() 播种 Mersenne Twister 随机数生成器种子。
mt_rand() 生成随机数。

mt_rand() 每次被调用都会根据种子 seed 和当前调用的次数 i 来计算出一个伪随机数。
当种子相同时，实际上生成的伪随机数是不变的，这就是伪随机数的漏洞所在。

种子从哪来？

PHP 7.x 8.0-8.1

PHP 在第一次使用随机数时进行 seeding，seeding 的熵仅有单一来源：系统当前的时间，单位微秒。
地址：https://github.com/php/php-src/blob/PHP-7.4.25/ext/standard/mt_rand.c

PHPAPI void php_mt_srand(uint32_t seed)
{
  php_mt_initialize(seed, BG(state));
  php_mt_reload();
  BG(mt_rand_is_seeded) = 1;
}


PHPAPI uint32_t php_mt_rand(void)
{
  uint32_t s1;
  if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
  	zend_long bytes;
	if (php_random_bytes_silent(&bytes, sizeof(zend_long)) == FAILURE) {
		bytes = GENERATE_SEED();
	}
	php_mt_srand(bytes);
}
  if (BG(left) == 0) {
  	php_mt_reload();
  }
  --BG(left);
  s1 = *BG(next)++;
  s1 ^= (s1 >> 11);
  s1 ^= (s1 <<  7) & 0x9d2c5680U;
  s1 ^= (s1 << 15) & 0xefc60000U;
  return ( s1 ^ (s1 >> 18) );
}

PHP 8.2-8.3

首先尝试通过 php_random_bytes_silent 进行 seeding，若失败回退到时间，但不太可能失败。

PHP 8.4+（未发布）

首先尝试通过 php_random_bytes_silent 进行 seeding，若失败回退到 php_random_generate_fallback_seed。
php_random_generate_fallback_seed 的熵非常高，包含了时间，pid，ASLR地址等，几乎不可预测。

攻击方式

计算种子

地址：https://www.ambionics.io/blog/php-mt-rand-prediction
给定间隔 226 个值的两个 mt_rand() 输出结果，例如第 1 和 228 个 mt_rand() 的输出结果。
这里的栗子是：种子为 12345678，获取第 124 个随机值和第 350 （124+226）个随机值。

通过大佬的脚本即可还原种子。

爆破种子

地址：https://github.com/openwall/php_mt_seed
只需要知道第一个随机数即可爆破出种子，有更多连续的随机数的话结果会比较准确。（这里用两个随机数就爆出来了）

爆破种子 - 里应外合

地址：https://github.com/moorejacob2017/exploiting_phps_rand_function
Jacob Moore 的研究，只需要知道 pid 与生成种子时系统的时间，即可爆出种子。比较适合做后门？

种子的构成

https://github.com/php/php-src/blob/PHP-8.1/ext/standard/php_rand.h

run_exploit.sh 会自动获取当前进程的 pid 和系统时间，即可爆破出种子。

重复随机数风险

在多进程的场景下，两个不同的请求进入同一个 pod 的两个不同的子进程，很有可能生成两个相同的种子，导致后面的随机数完全一致。例如使用 mt_rand 生成验证码的场景，你可能多次收到相同验证码。

加固建议

使用 PHP 中的 random_int() 或 openssl_random_pseudo_bytes() ，这些函数是密码学安全随机数（CSPRNG），据有良好的不可预测性。

李西瓜🍉