yohgaki's blog

Stefan Esser氏のブログでmt_srandとそれほどランダムでない乱数（mt_srand and not so random numbers)というエントリが8/17に掲載されています。気になっていたのでPythonの実装も調べてみました。

フォローアップ

乱数生成器は擬似乱数生成器

PHPの乱数生成器にはrandとmt_randの2種類がありますが、randはlibcのラッパー関数でmt_randはMersenne Twisterアルゴリズムを利用した乱数生成器です。乱数生成器といってもどちらも擬似乱数生成器なのでそれぞれ、srandとmt_srandで与えたシード同じであればその後に生成される乱数（擬似乱数）は同じになります。これはコンピュータサイエンス系の学科を専攻していれば常識ですが、ご存知でない方も少なくないと思います。

シードの予測

擬似乱数なのでシードが判れば、生成される乱数は予測できます。Stefan氏のブログに詳しく記述されているのでここで同じ説明はしませんが、この事をうまく利用すると擬似乱数で生成したランダムなはずのパスワードを推測可能になります。Stefan氏のブログにはWordPressのパスワードを推測する手法が詳しく解説されています。

Pythonの実装

PHPで起きる（起こっていた）ような脆弱性は他の言語やライブラリ、フレームワークでも同じように攻撃できる事が多いです。そこで、Python 2.6RC2の実装はどうなっているか、さっとソースを斜め読みですが眺めてみました。Modules/_randommodule.cにコードがあり、擬似乱数生成器にはPHPと同じMersenne Twisterが利用されシードもPHPと同じ32bitでした。

リファレンスではシードは次のように初期化されると書かれています。

seed( [x])
基本乱数生成器を初期化します。オプション引数 x はハッシュ可能な任意のオブジェクトをとり得ます。x が省略されるか None の場合、現在のシステム時間が使われます; 現在のシステム時間はモジュールが最初にインポートされた時に乱数生成器を初期化するためにも使われます。

乱数の発生源をオペレーティングシステムが提供している場合、システム時刻の代わりにその発生源が使われます（詳細については os.urandom() 関数を参照）。 バージョン 2.4 で 変更 された仕様: 通常、オペレーティングシステムのリソースは使われません

x が None でも、整数でも長整数でもない場合、 hash(x) が代わりに使われます。 x が整数または長整数の場合、x が直接使われます。

http://www.python.jp/doc/nightly/lib/module-random.html

コードとリファレンスマニュアルからはStefan氏がブログで書いているのと同じ手法が使える場合がある事が分かります。

蛇足ですがPHP 4.2.0からシードは自動的に行われます。Pythonの場合、/dev/urandomがあると利用するようですがPHPは利用しません。しかし、時刻とプロセスIDを利用し初期化されるようになっています。現在のPHPでは自分で

mt_srand(microtime()*1000000);

等の様に初期化するより、PHPに初期化を任せた方が安全です。

乱数生成器の取扱い

乱数生成器の出力をそのままユーザへ出力すると、シードを推測されしまうリスクが高くなります。乱数生成器からの出力はそのまま出力しないようにするべきです。できれば/dev/urandomのように乱数デバイスを利用するのが良いですが、固定でも良いのでランダムな文字列と一緒にハッシュ値を取った値にする等の方法を利用すべきです。

共有型Webホスティングサービスを利用しない理由は他にもいろいろありますが、理由の一つとして覚えておいて損はないと思います。