PHPのmt_rand関数が壊れている問題

PHPのmt_rand関数のtwistマクロに一文字タイポがあり、修正されたのですが

http://git.php.net/?p=php-src.git;a=commitdiff;h=a0724d30817600540946b41e40f4cfc2a0c30f80

でリバートされてしまいました。

追記

PHP 7.1からMT randのコードが修正されています。ユーザーコード（PHPスクリプト）からはアルゴリズムは選べません。Cモジュールの場合、旧アルゴリズムと修正済アルゴリズムから選択できるようになっています。

この他にもPHPのmt_rand()実装の場合、本来MT randは2^19937の状態を取り得るのですが、PHPはたったの2^32の状態でしか初期化できません。つまり、MT randアルゴリズムに較べて2^19902くらいPHPのmt_rand()は初期値は弱いことになります。（＝比較にならないほどPHPのmt_rand()は予測し易い）

パッチ

リバートのパッチはコレです。

index bc32f24..2dd05e7 100644 (file)
--- a/ext/standard/rand.c
+++ b/ext/standard/rand.c
@@ -146,7 +146,7 @@ PHPAPI zend_long php_rand(void)
 #define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */ #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */ 
-#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(v))) & 0x9908b0dfU))
+#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))
 
 /* {{{ php_mt_initialize
  */

修正しなくても実用的には問題がない、との判断もあったようです。そこでENTというエントロピーを分析するツールで簡単に確認してみました。

修正済の場合

Entropy = 7.954269 bits per byte.

Optimum compression would reduce the size
of this 4000000 byte file by 0 percent.

Chi square distribution for 4000000 samples is 250901.85, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 111.4725 (127.5 = random).
Monte Carlo value for Pi is 3.486975487 (error 10.99 percent).
Serial correlation coefficient is -0.049294 (totally uncorrelated = 0.0).

未修正の場合

Entropy = 7.954382 bits per byte.

Optimum compression would reduce the size
of this 4000000 byte file by 0 percent.

Chi square distribution for 4000000 samples is 250280.94, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 111.5000 (127.5 = random).
Monte Carlo value for Pi is 3.483663484 (error 10.89 percent).
Serial correlation coefficient is -0.049192 (totally uncorrelated = 0.0).

恐らく普通の疑似乱数が必要な場合の用途では問題はないと思われます。しかしこのテスト結果をもって、これで万全！とは行かずMT randが持つ非常に長い周期性が保たれているか？などの確認も必要です。※ もっと良いツールで検証した方もいました！こちらもあります。

暗号理論的に安全な乱数が必要な場合は、random_bytesかrandom_intを使用すべきです。（利用できない場合はopenssl_random_pseudo_bytesか/dev/urandomなどを利用する。random_bytes/int関数をPHPスクリプトで実装した物もあります。）

一応、修正すべきでは？と提案していますが、どうなるかは判りません。

他の問題

PHPのrand()とmt_rand()には別の問題もあります。getrandmax()、mt_getrandmax()を超える乱数の最大値（より正確には乱数の範囲）を指定すると乱数が奇数／偶数に偏る、という問題です。この問題は以前から知られていますが、修正されていません。

<?php
$loops = 1000;
// even に偏る
//$min = 1;
//$max = mt_getrandmax()*2+1;
// odd に偏る
$min = 0;
$max = mt_getrandmax()*2;

while ($loops--) {
    $v = rand($min, $max);
    $v%2 ? @$rand['odd']++ : @$rand['even']++;
    $v = mt_rand($min, $max);
    $v%2 ? @$mt_rand['odd']++ : @$mt_rand['even']++;
    $v = random_int($min, $max);
    $v%2 ? @$random_int['odd']++ : @$random_int['even']++;
}

var_dump($rand, $mt_rand, $random_int);

これを実行するとエラー無しに以下のような出力になります。（mt_getrandmax()は2^31-1ですが、64bit環境なのでより大きな値でも整数オーバーフローは起きていません）

array(1) {
  'odd' =>
  int(1000)
}
array(1) {
  'odd' =>
  int(1000)
}
array(2) {
  'even' =>
  int(487)
  'odd' =>
  int(513)
}

https://bugs.php.net/bug.php?id=69396 は新しいバグレポートですが、これより随分前にこの問題はレポートされていたと思います。今はOPEN状態のバグレポートが無いので、恐らくgetrandmax()以上の範囲を指定することがユーザースクリプトのバグだとして処理されたのだと思います。（Windowsだとgetrandmax()は2^15らしいので、よりrand()に注意が必要かも）

実際のrand()/mt_rand()の最大有効範囲は2^32なのですが、32bit環境でのint整数型との整合性を考えて敢えて小さい範囲にしたのだと思います。

getrandmax()/mt_getrandmax()より大きな値を範囲に利用することはあまり無いと思いますが、現在のPHPは無効（危険）な範囲を指定してもエラーは発生しないので注意が必要です。これは簡単なパッチでエラーを出すように直せます。

https://gist.github.com/yohgaki/1519f65dffd66735bafe

rand()/mt_rand()の戻り値は32/64bit環境の両方で同じになることが望ましいので、rand()/mt_rand()をより大きい範囲に対応できるようにするのは難しいです。

32bit環境では倍精度浮動小数点型を使い2^53の範囲まで、64bit環境では64bit整数を使い2^64の範囲までを使える新しい疑似乱数関数を追加するのが現実的かも知れません。

PHPスクリプトによる別の実装

AESを応用したシード可能（つまり同じランダム整数／バイト）を生成可能なPHPクラスの実装があります。利用可能なPHPは限定されますが、これは面白い実装です。128bit AESを利用しているので、128bitまでのシード付きのランダムな値を取得できます。（実際には整数型の範囲内までしか使えませんが、内部的には生成可能）このクラスは割り算／掛け算は行わす、範囲内の値が出てくるまで乱数を生成します。最大128回試行します。このため確率は低い（作者によると1/2^128）ですが乱数の生成に失敗する可能性もあります。PHP7で実装されたrandm_int()も似たような仕組みで範囲内の乱数を生成しています。こちらは成功するまでループするので失敗することはありません。同じ仕組みに改造しても良いかも知れません。

https://github.com/paragonie/seedspring