random(4)

random, urandom − 乱数デバイス

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

操作の理論

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

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

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

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

エクスポートされたインタフェース — 出力

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

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

他の 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 プラットフォーム向けに書き ました。 FreeBSD に移植したのは 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/urandom

歴史

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

FreeBSD 10.0 October 21, 1995 FreeBSD 10.0