Zenn
⚰️

PHP の乱数実装がグダグダな話

2020/12/13に公開
PHP
tech

2022-07-19
これらの問題を解決する Random Extension 5.x 並びに Random Extension Improvement RFC が可決され、 master に merge されました。 PHP 8.2 より利用可能になります。

2022-06-18
これらの問題を解決するため、 PHP 8.2 に対して Random Extension 5.x の RFC が作成され、投票が始まっています

https://wiki.php.net/rfc/rng_extension

2021-01-15
PHP master (8.1 以降) にて mt_srand の自動初期化時に内部で Combined LCG が使われなくなった旨を追記しました

2020-12-19
orng 拡張が PECL で利用できるようになったので追記しました

2020-12-14
random_int() が Linux 上ではカーネルのスピンロックを取る関数であることを明記し、選択肢としてピュア PHP の乱数生成ライブラリがあることを追記しました。 (thanks @tadsan)

もともと メルセンヌ・ツイスタが壊れていた ことで有名な PHP の乱数実装ですが、実際の所は世の中で言われているよりも更にグダグダです。

何がどうしてグダグダなのか、そしてどうすれば良いのかを考えてみます。

壊れた Mersenne Twister 実装の問題

これは結構有名な話だと思います。優れた乱数生成器としての特性をもつメルセンヌ・ツイスタは PHP にも古くから実装されていましたが、その実装は PHP 7.1 で修正されるまで誤ったものでした。この実装は互換のために今も PHP に残されています。

ext/standard/mt_rand.c
#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
#define twist_php(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))

この実装の誤りによる乱数品質への影響は特に見られず、 TestU01 (乱数品質測定用ライブラリ) でも正しい実装との差は特に見られなかったようです。

この問題は PHP 7.1 で修正され、シード値に対する結果の互換性ために mt_srand() 関数に MT_RAND_PHP オプションが追加されました。今まで mt_srand() を特定のシード値で初期化した後生成される乱数に依存している実装は、このオプションによって互換性を維持することができます。

PHP 7.1 における srand() / rand() のエイリアス化の問題

PHP 7.1 では、上記のメルセンヌ・ツイスタの修正の他に srand() rand() 関数の mt_srand() mt_rand() 関数のエイリアス化の対応が盛り込まれました。

まず、 srand() を特定のシード値で初期化した後に rand() で生成される値に依存している実装が軒並み動かなくなるという問題が生じました。この問題については別途後述します。

エイリアス化により、以下のコードは PHP 7.1 未満とそれ以降で挙動が変わるようになってしまいました。

alias.php
<?php
mt_srand(1234);
rand(); // PHP 7.1 以降では内部で mt_rand() が呼ばれてしまい、乱数が消費されてしまう
echo mt_rand();

srand() rand() と libc への依存問題

PHP 7.1 にてメルセンヌ・ツイスタ関数へのエイリアス化が行われたため、 srand() rand() 関数の元の実装を呼び出すことはできなくなりました。 srand() を特定の値で初期化した後 rand() で生成される乱数に依存した実装は完全に動かなくなってしまいました。

とはいえ、そもそも srand() rand() 関数はもともとシステムの libc をそのままコールするような実装になっており、 libc 側の実装次第で結果が変わってしまう問題を抱え続けていました。

以下は Debian (GNU libc) と Alpine Linux (musl-libc) 上での srand() と rand() の結果です。シード値に対して生成される値が異なっていることがわかります。

$ docker run --rm -it php:7.0-cli -r 'srand(1234); echo rand() . PHP_EOL;'
479142414
$ docker run --rm -it php:7.0-cli-alpine -r 'srand(1234); echo rand() . PHP_EOL;'
1887660748

mt_rand() と Combined LCG の問題

[2021-01-15 追記]
変更が master に merge され (https://github.com/php/php-src/commit/53ee3f7f897f7ee33a4c45210014648043386e13) 、自動またはパラメータなしで初期化を行った場合に random_bytes 同様の方法でシード処理を行うようになりました。おそらく PHP 8.1 以降で入ると思われます。

mt_rand() 関数は事前に mt_srand() 関数でシードが行われていない場合、 Combined LCG というアルゴリズムによってシード値を生成するような仕組みになっています。

しかし、この Combined LCG がエントロピーとして用いているものは PID (もしくはスレッド ID) と時間情報だけです。

ext/standard/lcg.c
static void lcg_seed(void)
{
	struct timeval tv;

	if (gettimeofday(&tv, NULL) == 0) {
		LCG(s1) = tv.tv_sec ^ (tv.tv_usec<<11);
	} else {
		LCG(s1) = 1;
	}
#ifdef ZTS
	LCG(s2) = (zend_long) tsrm_thread_id();
#else
	LCG(s2) = (zend_long) getpid();
#endif

	/* Add entropy to s2 by calling gettimeofday() again */
	if (gettimeofday(&tv, NULL) == 0) {
		LCG(s2) ^= (tv.tv_usec<<11);
	}

	LCG(seeded) = 1;
}

このため、初期シード値がある程度推測可能です。もともと mt_rand() の結果をセキュアなことに使用すべきでない旨はマニュアルに書かれていますが...

特に最近ではコンテナ環境で動作していることも多く、 PID が固定値になってしまうことも十分考えられます。この場合エントロピーとして価値があるのは時間だけです。十分推測できてしまいます。

PHP 7.1 におけるメルセンヌ・ツイスタのモジュロ・バイアス問題

PHP 7.1 にてメルセンヌ・ツイスタの実装の修正がされましたが、そこで新たに 64bit 環境におけるモジュロ・バイアスのバグが盛り込まれてしまいました。

このバグについては Internals (開発者 ML) などでも言及されており、 PHP 7.2 で修正が行われました。

このバグは PHP 7.2 で修正されましたが、 PHP 7.1 と PHP 7.2 以降では同じ値で mt_srand() を初期化しても mt_rand() が異なる結果を返してくる可能性があります。とはいえ発生する状況は
極稀であるため、実質的にそこまで影響はないものです。

どうすればいいのか

シード値に対する一貫性が求められない場合

素直に random_int() を使ってください。 mt_srand() を呼ばずに mt_rand() を呼んでいるのであればほぼ単純置換で OK です。

ただし、 random_int() 関数は現状 Linux カーネル上ではスピンロックを用いて排他制御を行います。同一のホスト上で大量に呼び出す場合にはある程度考慮が必要です。

シード値に対する一貫性が求められる場合

  • PHP で実装された乱数生成ライブラリを使う
  • 気をつけて mt_srand() と mt_rand()を使う

そもそもなぜオブジェクトスコープの乱数生成機がないのか

Java など他言語の乱数生成器は、ステートをオブジェクトに内包しているため安全です。なぜ PHP はこのような実装になっていないのでしょうか。

と思ったのでPHP 拡張を作りました。

pecl コマンドが利用できる環境であれば、以下のコマンドでインストールできます。インストール後には php.ini で有効化が必要です。

$ pecl install orng

上記の実装にはオブジェクトスコープな乱数生成機として以下のものが実装されています。

  • \ORNG\GLibCRand: GNU libc 環境下での PHP 7.0 以下の srand() rand() と互換のある乱数生成器
  • \ORNG\MT19937: PHP 7.2 以降の正しいメルセンヌ・ツイスタと同等の乱数生成器
  • \ORNG\MT19937PHP: PHP 7.0 以下の壊れたメルセンヌ・ツイスタと同等の乱数生成器
  • \ORNG\MT19937MB: PHP 7.1 のモジュロ・バイアスバグを抱えたメルセンヌ・ツイスタと同等の乱数生成器
  • \ORNG\XorShift128Plus: ブラウザなどで実装されている XorShift128+ 実装の乱数生成器
GitHubで編集を提案

Discussion