ハードウェア乱数生成器は信頼できるか

How secure is Linux's random number generator? | Hacker News

Hacker Newsで話題になっていたので。

主に暗号用途には、予測不可能な乱数が必要となる。予測不可能というのは、実装と内部状態が知られていても、なお将来の乱数が予測できないということだ。

たとえば、擬似乱数としてよく使われる線形合同法(Linear congruential generator)は、以下のように書ける。

namespace lcg { 

thread_local unsigned int seed ;

void srand( unsigned int seed )
{
    lcg::seed = seed ;
}

int rand( void )
{ // glibcの使っている値を拝借
    seed = (1103515245 * seed + 12345) % 0x80000000 ;
    return static_cast<int>(seed) ;
}

}

この線形合同法は、高速に乱数を生成したい場合には便利だが、残念ながら予測可能なので、暗号用途には適していない。

Linuxカーネルが提供している/dev/randomは、様々なハードウェアやデバイスドライバーから生成される予測不可能な値をエントロピープールとして貯めこみ、ハッシュ化して予測不可能な乱数を作り出す。

問題は、そのような予測不可能な値というのは、それほど多くないし、頻繁に生成されない。そのため、/dev/randomの乱数生成の速度は非常に遅い。どのくらい遅いのか確認したければ、以下のように試してみるといい。

$ cat /dev/random

以前のLinuxカーネルは、エントロピープールのサイズを増やすことができた。ただ、プールが大きすぎると、乱数がある程度予測可能になってしまうという攻撃手段が見つかったので、今ではその機能は削られた。以前のLinuxカーネルはもっと多くのドライバーから値を取得していたが、多くのデバイスから得られる値は、外部からの操作によってある程度予測可能になるということが判明したので、今では/dev/randomのプールに使うデバイスもだいぶ減った。

予測不可能な乱数を高速に生成する需要はかなりある。そこで、IntelのIvy Bridgeでは、rdrandという命令が追加された。これは、CPUに組み込まれた乱数生成器によって、予測不可能な乱数を高速に生成することができる。

rdrandは十分に高速なのだが、別の問題がある。ハードウェアは信頼できるかという問題だ。IntelのCPUは信頼できるのか。

乱数が真に乱数らしいことを確かめるツールには、Dieharderがある。もちろん自由ソフトウェアだ。DieharderはDebianならパッケージ化もされており、apt-get install dieharderするだけでコンパイル済みのバイナリが入れられる。使い方も、乱数であることを確かめたいビット列をpipeで流しこむだけと簡単だ。

もちろん、rdrandは誰でも使える命令であり、すでにDieharderのようなソフトウェアもある以上、検証している人もいる。

A Smackerel of Opinion: Intel rdrand instruction revisited

ただし、Intelがその気になれば、rdrandの実装は、インクリメントされるカウンターをAESで暗号化したものにできる（暗号鍵はもちろんIntelやNSAが保持しているのだ）。この実装は、Dieharderのようなテストもパスする。

Linuxでrdrandをサポートする際にも、ハードウェアを信頼できるのかという議論がされている。

LKML: Matt Mackall: Re: [PATCH 1/2] random: Add support for architectural random hooks

Linusによれば、rdrandを直接使うのではなく、既存のエントロピープールに他の値と一緒に混ぜ込んでハッシュ化するので、まず問題にはならないだろうとしている。