乱数生成のソースを表示

[[Category:セキュリティ]]
[[en:Random number generation]]
[[Wikipedia:Random number generation]] より:
:''乱数生成器 (RNG) とはパターンの存在しない (つまりランダムな) 数字や記号の羅列を生成するための計算法または物理デバイスのこと。''

ランダムなデータの生成はアプリケーションによってはとても重要なことです。([[ディスク暗号化]]などに用いる) 暗号鍵の作成や[[ディスクの完全消去|ディスクの完全消去]]、暗号化された[[ソフトウェアアクセスポイント]]など。

== カーネル内蔵の RNG ==
カーネルに含まれている RNG である [[wikipedia:ja:/dev/random|/dev/{u}random]] は暗号鍵の作成などに使われるような高いセキュリティレベルを必要とするランダムデータの生成を行うときに使うことを強く推奨されます。この乱数生成器はデバイスドライバなどの情報源から環境ノイズをエントロピープールに集めます。

{{ic|man random}} コマンドではライブラリ関数の man ページ [http://man7.org/linux/man-pages/man3/random.3.html random(3)] が表示されてしまうので注意してください。{{ic|/dev/random}} デバイスに関する情報が必要なときは {{ic|man 4 random}} を実行して表示される [http://man7.org/linux/man-pages/man4/random.4.html random(4)] を読んで下さい。

=== /dev/random ===
{{ic|/dev/random}} は4096ビット (512バイト) のエントロピープールを使用してランダムデータを生成します。エントロピープールが空になると、プールがまた補充されるまで待機します (これには時間がかかります)。{{ic|/dev/random}} は暗号鍵 (SSL, SSH, dm-crypt の LUKS など) の生成のために設計されており、HDD の中身の消去に使うのは現実的ではありません。システムに[[Wikipedia:Hardware_random_number_generator#Using_observed_events|十分なエントロピーが収集される]]まで止まってしまって、ディスクの消去にものすごく時間がかかるためです。エントロピーが枯渇しているような環境だと (例: リモートサーバー)、永遠に終わらないかもしれません。巨大なディレクトリで検索コマンドを実行するとか、X でマウスを動かすなどをすればエントロピープールは段々と溜まっていきますが、そもそもプールサイズ自体がディスクの消去を行うには不十分な造りになっています。

{{ic|/proc/sys/kernel/random/entropy_avail}} と {{ic|/proc/sys/kernel/random/poolsize}} を比較することでシステムのエントロピープールを目で追うことができます。

Linux カーネル 2.4 ではエントロピーのプールサイズを変更できるように書き換え可能な {{ic|/proc}} エントリが出来ましたが、新しいカーネルでは {{ic|read_wakeup_threshold}} と {{ic|write_wakeup_threshold}} しか書き換えできないようになっています。現在、プールサイズはカーネルの {{ic|/drivers/char/random.c}} の275行目でハードコード (決め打ち) されています:

{{bc|/*
 * Configuration information
 */
#define '''INPUT_POOL_WORDS 128'''
#define '''OUTPUT_POOL_WORDS 32'''
...}}

カーネルのプールサイズは {{ic|INPUT_POOL_WORDS * OUTPUT_POOL_WORDS}} で求めることができ、既に述べたように、4096ビットとなります。
{{Warning|あなたの [http://everything2.com/title/Compromising+%252Fdev%252Frandom 制御下] にない環境では {{ic|/dev/random}} を使って''重要な''暗号鍵を生成してはいけません。例えば、共有サーバーの環境などを想定してください。別の環境で鍵を作成してから転送するようにしましょう。暗号学者 D. J. Bernstein はこの問題を [http://blog.cr.yp.to/20140205-entropy.html Mark Twain の名言] で説明しています。}}

=== /dev/urandom ===
{{ic|/dev/random}} と反対に、{{ic|/dev/urandom}} はプールが充填されるのを待たず、既存のエントロピープールのデータを再利用します。{{ic|/dev/urandom}} の出力は {{ic|/dev/random}} から得られるのと比べて含まれるエントロピーが少なくなりますが、ディスクの徹底消去や[[ディスクの完全消去#ブロックデバイス暗号化の準備|ブロックデバイス暗号化の準備]]、LUKS キースロットの消去などの目的には十分です。それでも、巨大なドライブを処理する場合は莫大な時間が費やされます [http://www.2uo.de/myths-about-urandom/] [http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/] [https://www.mail-archive.com/cryptography@randombit.net/msg04748.html]。

{{Warning|長期間の暗号鍵を生成するのに {{ic|/dev/urandom}} は推奨されません。}}

== 高速な RNG ==
長い暗号鍵の生成などは行わないアプリケーションの場合、パフォーマンスとセキュリティの折り合いをつけて[[Wikipedia:ja:擬似乱数|擬似乱数生成器]]を使うこともあります。Arch Linux のリポジトリには以下のような擬似乱数生成器が存在します:
* [[Haveged]]
* [[en2:Frandom|Frandom]]
* [[rng-tools]]

また、[[Wikipedia:Yarrow_algorithm|Yarrow]] (FreeBSD/OS-X) や [[Wikipedia:Fortuna_(PRNG)|Fortuna]] (Yarrow の後継) のような[[Wikipedia:ja:暗号論的擬似乱数生成器|暗号論的擬似乱数生成器]]もあります。

== 参照 ==
* [http://www.ietf.org/rfc/rfc4086.txt  RFC4086 - Randomness Requirements for Security] (Section 7.1.2 for /dev/random)
* [http://lkml.indiana.edu/hypermail/linux/kernel/1302.1/00479.html Linux Kernel ML] - discussion on patching /dev/random for higher throughput (February 2013)
* [http://eprint.iacr.org/2013/338 A challenge on /dev/random robustness] (June 2013) 
* [http://eprint.iacr.org/2014/167 An analysis of low entropy state] behaviour of /dev/random, Yarrow, Fortuna and new model approach (March 2014)  
* [http://www.random.org/randomness/ Randomness] - 様々な RNG について説明している科学記事
* [http://www.fourmilab.ch/random/ ENT] - A simple program for testing random sequences (entropy, Chi square test, Monte Carlo, correlation, etc.)
* [http://www.codeproject.com/Articles/795845/Arduino-Hardware-Random-Sequence-Generator-with-Ja DIY HRNG] - One example of a low-cost, DIY Arduino HRNG