Linuxで扱う乱数に関する話

Pocket

これはLinux Advent Calendar4日目の記事です。

Unix系OSには、カーネルに乱数生成器を持つ実装が多くあります。乱数は暗号分野でも利用され、非常に重要な位置を占めています。Linuxにおける乱数に関する話題を取りあげてみます。

エントロピープール

一般的に、特別なハードウェアを持たない限り、真の乱数を計算機が生成することは困難です。Linuxでは、質の良い乱数を生成するためにエントロピープールと呼ばれる領域を持っています。エントロピープールには、キーボードの入力タイミングやストレージ、ネットワークなどで発生するハードウェア割り込みなどをもとにした推測の困難な情報(環境ノイズ)が蓄積されます。乱数の生成時には、このエントロピープールの内容を消費、加工します。

エントロピープールにどの程度情報がたまっているかを調べるには、/proc/sys/kernel/random/entropy_availを見ます。エントロピープールの上限値は/proc/sys/kernel/random/poolsizeをcatした出力値です(デフォルト値は4096) 。OpenPGPやSSLの鍵などを生成する際には、この値を確認した方がよいかもしれません。

// drivers/char/random.c
/*
 * Configuration information
 */
#define INPUT_POOL_WORDS 128
#define OUTPUT_POOL_WORDS 32
#define SEC_XFER_SIZE 512
#define EXTRACT_SIZE 10

// 途中略

static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
ctl_table random_table[] = {
        {
                .procname       = "poolsize",
                .data           = &sysctl_poolsize,
                .maxlen         = sizeof(int),
                .mode           = 0444,
                .proc_handler   = proc_dointvec,
        },
        {
                .procname       = "entropy_avail",
                .maxlen         = sizeof(int),
                .mode           = 0444,
                .proc_handler   = proc_dointvec,
                .data           = &input_pool.entropy_count,
        },

スペシャルデバイス

乱数を生成する特別なデバイスファイルには、/dev/randomと/dev/urandomの2種類があります。

/dev/randomは全ての乱数をエントロピープールから生成します。エントロピーが不足した場合は新たにたまるまでブロッキングされるため、あまり速度が出ません。乱数の質よりも速度に重点を置く場合には、/dev/urandomを使います。urandomを使う場合、エントロピープールを再利用して乱数を生成します。

havege

havegedを動かすことで、より多くの環境ノイズ(主にCPUの情報)をもとにしてエントロピープールを常に多い状態へと保つことができます。エントロピープールへの情報の追加は/dev/randomのioctrlインターフェースを用いています。また、havagedは単独の乱数生成アプリケーションとしても利用できます。

NeuG

g新部さんによるハードウェア乱数生成実装として、NeuGがあります。NeuGはSTM32F103上で動作し、チップに搭載されているA/Dコンバーターからの入力の量子化誤差を乱数生成に利用します。NueGの動作するハードウェアとしてFST-01があります。この記事を書いている2014年12月初頭では品切れ中ですが、今後追加生産・販売を予定しているそうです。

仮想化の問題

エントロピープールの情報は、予測が困難であるハードウェアからの情報に大きく依存しています。仮想マシンの場合、多くのハードウェアは仮想化されており、ハイパーバイザ等の配下にあります。したがって、物理マシンと比較すると質の良い乱数を生成させることがより困難となっています。セキュリティに十分な注意を払う必要がある場合には、信頼できない仮想マシン上での暗号鍵の生成などは控えた方が良いでしょう。

訂正

コメントでg新部さんからいくつかご指摘を頂きましたので修正・追記しました。FST-01はhttp://www.seeedstudio.com/より購入可能とのことです。詳細はコメントをご覧ください。

宣伝

この記事はFSIJ勉強会での解説をもとに得た知見を自分なりに記録したものです。FSIJでは定期的に勉強会を開催しています。GnuPGの開発者の一人であるg新部さんもいらっしゃるので、興味のある方はぜひお越しください。

 

Published
Categorized as Linux

By knok

I am a Debian Developer and a board member of Free Software Initiative (FSIJ).

3 comments

  1. NeuG紹介ありがとうございます(スペルが違うけど)。

    NeuGの本質は、A/Dコンバータの計測で不可避である量子化誤差を積極的に使う、ということで、環境からのノイズを入力とする、という考え方ではありませんので注意ください。使えるものは使うとの考えで後者も使いますけどこれは必須ではありません。

    つまり、サンプルを取る、計測する、ということは、サイコロを振るということであって、今時の高速の計測では、サンプルを取る度にエントロピーを拾えます、ということです。

    FST-01は http://www.seeedstudio.com から入手可能です。品切れではありません、よ。
    ただし、こちらで購入するとGnuk 1.0.1が入っているので、NeuGを自分でインストールしないといけません。

    Well Tempered Hacker で紹介された FST-01 の動画: http://www.youtube.com/watch?v=iDuhLQ43tvQ

    を参考にしてみてください。

    なんでこうなっているかというと、エントロピーを本当に真剣に気にする人は、インストールされたソフトウェアをどう信頼したらいいのか、ということも気になって、自分で簡単にできるところ(コンパイルとインストール)くらいは自分の手でやってみよう、という性質があるからです。

    欲しいヒトには、NeuG 1.0.xをインストールしたFST-01も飛石技術で受注して販売してます。フランス、香港、日本、アメリカの方々に販売実績があります。ドイツでは自分で作っている方もいます。

  2. 僕の知る限り、Linuxでネットワークからの割り込みはエントロピー源のひとつとはされてません(外部からコントロールできる可能性があるので)。
    ディスクの割り込みタイミングが源となりうるのは、ディスクの回転に不可避なゆらぎがある、という理屈です(カオス現象の一つ)。割り込みをまとめちゃうような最近の優秀なチップセットや、半導体のストレージでは、この目的では使えないことになり、こまっちゃいますね。

Comments are closed.