manページ  — RANDOM

random, urandom – 乱数デバイス

解説 操作の理論 エクスポートされたインタフェース — 出力 エクスポートされたインタフェース — 入力 謝辞 関連項目 関連ファイル 歴史

このデバイスはデバイスドライバなどから環境ノイズを集め、暗号での利用に適当な 良い乱数を返します。暗号での利用はもちろん、この数は TCP シーケンス番号のための 乱数の種や、ランダムなだけでなく攻撃者の予想が難しい数が望ましいその他の ところでも良いものです。

コンピュータはとても予測しやすい装置です。従ってコンピュータで本当に乱数を 作ることは — アルゴリズムを使って簡単に作れる疑似乱数とは 対照的に — 非常に難しいです。 不幸にも、攻撃者が疑似乱数生成器の乱数の列を推量することはとても簡単です。 そしてあるアプリケーションにとっては、これは受け入れられません。 そこでその代わりに、コンピュータの環境から「環境ノイズ」を集めて、それを使って 乱数を作る必要があります。「環境ノイズ」は外部の攻撃者には見るのが難しいもので なければなりません。Unix 環境では、これはカーネル中で行うのが最善です。

環境からの乱数源には、キーを押す間のタイミングやいくつかの割り込みの 間のタイミング、そして (a) 非決定論的で (b) 外部の観察者から 測定するのが難しいその他の事象が含まれます。 この源からの乱数は「エントロピのたまり場」に加えられます。 「エントロピのたまり場」は周期的に CBC モードの MD5 圧縮関数を使って かき混ぜられます。 乱数がエントロピのたまり場でかき混ぜられるときに、ルーチンは 何ビットの乱数が乱数生成器の内部状態に蓄えられたかを 見積り ます。

乱数が要求されると、カウンタと「エントロピのたまり場」の 内容の和の MD5 ハッシュをとることにより、乱数が得られます。 MD5 ハッシュを使う理由は乱数生成器の内部状態を外にさらすのを防げるからです。 MD5 ハッシュはたまり場を保護しますが、たまり場から作られる乱数はそれぞれ 内部状態から得られる情報をいくらか漏らします。そのため情報量が増えると 外の攻撃者は乱数生成器の内部状態についていくらか推測してみることが できるようになります。 この理由からルーチンは乱数を出力するとき、エントロピのたまり場に含まれている 「真の乱数」のビット数の内部での見積りを減らします。

もしこの見積りが 0 になっても、ルーチンは乱数を作り続けることができます。 しかしながら、攻撃者が乱数生成器の出力や MD5 アルゴリズムを解析して ルーチンの出力の推測に成功するかも知れません。 最悪の場合、カウンタとばれていない秘密に対して MD5 ハッシングしたもの と同じになるので、 Phil Karn (エントロピのたまり場から乱数を取り出すのに、カウンタを加えた MD5 を使う機構を考えた人物) はこれを「実用的な乱雑さ」と呼んでいます。 もし MD5 が強力な暗号ハッシュであれば、これはかなり攻撃に耐えられるはずです。

エクスポートされたインタフェースは 3 つあります。第 1 はカーネルの内部から 使うことを意図したものです。

void get_random_bytes(void *buf, int nbytes);

このインタフェースは要求されたバイト数の乱数を返し、それを要求されたバッファに 置きます。

他の 2 つのインタフェースは /dev/random と /dev/urandom の 2 つのキャラクタ型デバイスです。 最大でもエントロピのたまり場に含まれる (乱数生成器により見積もられた) ビット数の乱数しか返さないので /dev/random デバイスは非常に高品質の乱数が必要なとき (例えば、鍵の生成) の使用に ふさわしいです。

/dev/urandom デバイスはこの制限がなく、要求されただけのバイトを返します。 エントロピのたまり場が再蓄積する時間を与えずに多くの乱数を要求すると、 乱数の質が低くなります。 しかしながら、多くのアプリケーションにとってはこれは受け入れられるでしょう。

デバイスから環境ノイズを集める現在のエクスポートされたインタフェースは 次の 2 つです。

void add_keyboard_randomness(unsigned char scancode); void add_interrupt_randomness(int irq);

1 番目の関数は「エントロピのたまり場」へのランダムな入力として、scancode は もちろん、キーを押す間のタイミングも使います。

2 番目の関数はエントロピのたまり場へのランダムな入力として割り込みの間の タイミングを使います。すべての割り込みが良い乱数源という訳ではないことに 注意して下さい！例えば、タイマ割り込みは良い選択ではありません。なぜなら 割り込みの周期性が非常に規則的なため攻撃者が予測できるからです。 ディスク割り込みのタイミングはより予測できないので、ディスク割り込みの方が より良いです。ルーチンは割り込みのタイミングの 1 次と 2 次のデルタを取ることで 特定の割り込みチャンネルが提供するランダムさが何ビットかを見積もろうとします。

元の中心となるコードは Theodore Ts'o が Linux プラットフォーム向けに書きました。 BSD Free に移植したのは rndcontrol(8) ユーティリティ も書いた Mark Murray です。

この乱数生成器を構成する考えは Pretty Good Privacy の乱数生成器と Phil Karn との個人的な議論から得たものです。この設計はさらに私一人で 修正したので、いかなる欠陥も私だけの責任であり、PGP の著作者や Phil に 帰するべきではありません。

MD5 変換のコードはパブリックドメインである Colin Plumb の実装から 取りました。MD5 暗号チェックサムは Ronald Rivest により発明され、 RFC 1321、 "The MD5 Message Digest Algorithm" で解説されています。

この話題に関するこれ以上の予備知識は Donald Eastlake, Steve Crocker, Jeff Schiller による RFC 1750、"Randomness Recommendations for Security" から 得られるでしょう。

rndcontrol(8)

/dev/random /dev/urandom

random, urandom ファイルは FreeBSD 2.1.5 で登場しました。