mt_rand()をパスワード生成に利用しないようにって言ったよね？

はじまり

あるところでmt_rand()を利用してパスワードを生成しているスクリプトを見つけたので、なぜmt_rand()を利用してはいけないのか具体的に検証してみた。

mt_rand()を利用した脆弱なパスワード生成コード

ここではMoodleに存在していた、CVE-2015-5267として報告された脆弱なパスワード（トークン）生成コードを使って、問題を検証する。記号が含まれていないとかどうでもいい。

function random_string ($length=15) {
    $pool  = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    $pool .= 'abcdefghijklmnopqrstuvwxyz';
    $pool .= '0123456789';
    $poollen = strlen($pool);
    $string = '';
    for ($i = 0; $i < $length; $i++) {
        $string .= substr($pool, (mt_rand()%($poollen)), 1);
    }
    return $string;
}

この関数は、パスワードリセット機能により送られる確認用メール送信時に利用され、URL中に埋め込まれる15文字のトークンを生成している。
このコードの想定どおりなら、(26+26+10)^15で149bit程度の強度のトークンが生成されることになる。

問題の検証

パスワード生成コード

この関数を利用して以下の様なスクリプトで10億個のパスワードを生成する。実際には24CPUのPCでpcntlを使い、240億個のパスワード生成を行っている。なお、後で本当に悪用が可能か確認する手順の問題でPHP 5.4を利用している。

passgen.php

<?php
$fp = fopen('/passwords', 'w');
for ($i=0; $i<1000; $i++) {
    $passwords = '';
    for ($j=0; $j<1000*1000; $j++) {
        mt_srand();
        $passwords .= random_string().PHP_EOL;
    }
    fwrite($fp, $passwords);
}
fclose($fp);

function random_string ($length=15) {
    $pool  = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    $pool .= 'abcdefghijklmnopqrstuvwxyz';
    $pool .= '0123456789';
    $poollen = strlen($pool);
    $string = '';
    for ($i = 0; $i < $length; $i++) {
        $string .= substr($pool, (mt_rand()%($poollen)), 1);
    }
    return $string;
}

sortしてuniq

生成された240億個のパスワードをsortしてuniqする。余談だがsortするだけで48時間以上かかった。
uniqした結果は、mt_srand()のシードである2^32に近い数値となっている。もっと沢山のパスワードを生成してやれば収束すると思われるが、私はやらない。
この結果から、mt_rand()を用いて長いパスワードを生成しても、32bitの強度しか得られないことが推測できる。

$ cat passwords | sort -o s_passwords
$ cat s_passwords | uniq > u_passwords 

$ ll -h
合計 779G
-rw-r--r--. 1 root root 358G  X月 XX XX:XX passwords
-rw-r--r--. 1 root root 358G  X月 XX XX:XX s_passwords
-rw-r--r--. 1 root root  63G  X月 XX XX:XX u_passwords

$ cat passwords | wc -l
24000000000

$ head passwords
Ird8JJsukrAzoWw
jG2JGZw0wiAMJu3
BbSVzYigCfu82hc
bJKqN3SSuXfkDsu
188aV6LHld2hbFj
MCjrSJMSqyKhnNF
5XV6cSfmaQYscs8
dwLxQY0U8rNJJzj
K8lEDOQ4ubXQz1s
DOTc2df4USC17x8

$ cat u_passwords | wc -l
4221559386

$ head u_passwords
00000N15n0ExpZb
00000ihQ6lTWGC3
00000uObYsWLn9D
00000yxDakR2vja
000011LZIS9PUei
00001LQDjhdYt6J
00001WWz4YSkjdx
00002Zs0xXQSj4P
00002uq1FXL1p2D
00003HEFfYYNrVA

$ echo 2^32 | bc
4294967296

実際に脆弱なトークンが生成されるのか確認

Moodle 2.5でテスト用サイトを構築し、パスワードリセット機能を使って実際に得られるトークンと比較してみる。Moodle 2.5はPHP 7.1で動作しないため、PHP 5.4を使用している。また、PHPはmod_php(DSO)を使用。
パスワードリセット操作を5回行い、以下のトークンが得られたが、全て生成したパスワードリストに含まれていた。数学的にどれくらい試行すれば確実なのか検討していないが、直感的には脆弱なトークンが生成される見当違いでは無いと感じられる。

DJn4kiOYPEaYxhD
SQLEOjWA3qRCBwz
i7YhLNq60y7MbB9
xa1DHsLCKApC4rQ
cuzP9uUDUeh4MrY

結論

mt_rand()を用いて149bitの強度を持つトークンを生成しようとしたが、実際には32bitの強度しか得られなかった。つまり15文字ではなく6文字しか無かったことになる。

おまけ: m % n は問題があるか？

@vf8974 さんからコメントがあった、mt_rand() % n で文字を決める処理に問題がないのだろうか？

文字が決まる確率

mt_rand()で得られる疑似乱数は、0～2,147,483,647となる。どの文字になるかは、これを62(26+26+10)で割った余りで決定することになる。
mt_getrandmax() % 62 が1になることから、余り0のA、余り1のBが他の文字より1つ現れる確率が高くなるはずである。もし擬似乱数の範囲が0～63だった場合は、AおよびBは他の文字の2倍の出現確率となってしまう。

$ php -r "echo mt_getrandmax();"
2147483647

$ php -r "echo mt_getrandmax() % 62;"
1

$ php -r "echo floor(mt_getrandmax() / 62);"
34636833

ただし、実際にはmt_getrandmax()で得られる値は、62と比較して非常に大きな値であるため、AまたはB:その他=34,636,834:34,636,833でしかなく、実際の出現確率は次の表に記載された値となる。この程度の差であれば、生成される数十文字程度のパスワードで使われる文字に偏りが出るとは考えにくいだろう。

文字	出現確率
A または B	1.61290327% (34,636,834/2,147,483,648)
その他の文字	1.61290322% (34,636,833/2,147,483,648)

検証してみる

この方法で生成した大量のパスワードがあるので、前述のpasswordsファイルを使って実際の偏りを確認してみる。
全部を集計すると非常に時間がかかるので、先頭の8GB分、524,288,000個のパスワードについて利用されている文字をカウントしてみた。
実際には最も使われていた文字はUで平均との比率で100.027%、逆に最も少なかった文字はRで同99.966%となっていた。前述の出現確率より疑似乱数のばらつきの影響の方が大きく出たと思われる。

以下は各文字の数をカウントしたvar_dumpになる。

array(62) {
  ["A"]=>
  int(126843325)
  ["B"]=>
  int(126811074)
  ["C"]=>
  int(126856799)
  ["D"]=>
  int(126837681)
  ["E"]=>
  int(126844249)
  ["F"]=>
  int(126838827)
  ["G"]=>
  int(126849189)
  ["H"]=>
  int(126865479)
  ["I"]=>
  int(126852455)
  ["J"]=>
  int(126834409)
  ["K"]=>
  int(126858435)
  ["L"]=>
  int(126840006)
  ["M"]=>
  int(126825180)
  ["N"]=>
  int(126847499)
  ["O"]=>
  int(126843783)
  ["P"]=>
  int(126816692)
  ["Q"]=>
  int(126844159)
  ["R"]=>
  int(126800422)
  ["S"]=>
  int(126858538)
  ["T"]=>
  int(126843684)
  ["U"]=>
  int(126877700)
  ["V"]=>
  int(126859511)
  ["W"]=>
  int(126831109)
  ["X"]=>
  int(126817568)
  ["Y"]=>
  int(126851341)
  ["Z"]=>
  int(126864319)
  ["a"]=>
  int(126804660)
  ["b"]=>
  int(126840360)
  ["c"]=>
  int(126841007)
  ["d"]=>
  int(126832857)
  ["e"]=>
  int(126865237)
  ["f"]=>
  int(126811432)
  ["g"]=>
  int(126810071)
  ["h"]=>
  int(126816053)
  ["i"]=>
  int(126855853)
  ["j"]=>
  int(126828351)
  ["k"]=>
  int(126860051)
  ["l"]=>
  int(126843233)
  ["m"]=>
  int(126863157)
  ["n"]=>
  int(126847387)
  ["o"]=>
  int(126843911)
  ["p"]=>
  int(126868865)
  ["q"]=>
  int(126866746)
  ["r"]=>
  int(126858408)
  ["s"]=>
  int(126857259)
  ["t"]=>
  int(126807707)
  ["u"]=>
  int(126813351)
  ["v"]=>
  int(126839930)
  ["w"]=>
  int(126870436)
  ["x"]=>
  int(126824485)
  ["y"]=>
  int(126848942)
  ["z"]=>
  int(126853395)
  [0]=>
  int(126846879)
  [1]=>
  int(126849249)
  [2]=>
  int(126843852)
  [3]=>
  int(126860574)
  [4]=>
  int(126872261)
  [5]=>
  int(126877169)
  [6]=>
  int(126846287)
  [7]=>
  int(126825370)
  [8]=>
  int(126857433)
  [9]=>
  int(126854349)
}