乱数生成

Wikipedia:Random number generation より:

乱数生成器 (RNG) とはパターンの存在しない (つまりランダムな) 数字や記号の羅列を生成するための計算法または物理デバイスのこと。

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

カーネル内蔵の RNG

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

man random コマンドではライブラリ関数の man ページ random(3) が表示されてしまうので注意してください。/dev/random デバイスに関する情報が必要なときは man 4 random を実行して表示される random(4) を読んで下さい。

/dev/random

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

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

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

/*
 * Configuration information
 */
#define INPUT_POOL_WORDS 128
#define OUTPUT_POOL_WORDS 32
...

カーネルのプールサイズは INPUT_POOL_WORDS * OUTPUT_POOL_WORDS で求めることができ、既に述べたように、4096ビットとなります。

警告: あなたの 制御下 にない環境では /dev/random を使って重要な暗号鍵を生成してはいけません。例えば、共有サーバーの環境などを想定してください。別の環境で鍵を作成してから転送するようにしましょう。暗号学者 D. J. Bernstein はこの問題を Mark Twain の名言 で説明しています。

/dev/urandom

/dev/random と反対に、/dev/urandom はプールが充填されるのを待たず、既存のエントロピープールのデータを再利用します。/dev/urandom の出力は /dev/random から得られるのと比べて含まれるエントロピーが少なくなりますが、ディスクの徹底消去やブロックデバイス暗号化の準備、LUKS キースロットの消去などの目的には十分です。それでも、巨大なドライブを処理する場合は莫大な時間が費やされます。

警告: 長期間の暗号鍵を生成するのに /dev/urandom は推奨されません。

高速な RNG

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

• Haveged
• Frandom
• rng-tools

また、Yarrow (FreeBSD/OS-X) や Fortuna (Yarrow の後継) のような暗号論的擬似乱数生成器もあります。

参照

• RFC4086 - Randomness Requirements for Security (Section 7.1.2 for /dev/random)
• Linux Kernel ML - discussion on patching /dev/random for higher throughput (February 2013)
• A challenge on /dev/random robustness (June 2013)
• An analysis of low entropy state behaviour of /dev/random, Yarrow, Fortuna and new model approach (March 2014)
• Randomness - 様々な RNG について説明している科学記事
• ENT - A simple program for testing random sequences (entropy, Chi square test, Monte Carlo, correlation, etc.)
• DIY HRNG - One example of a low-cost, DIY Arduino HRNG