Linux カーネルの /dev/random について

UNIX 系 OS では、疑似乱数を生成するためのデバイスとして、 /dev/random が提供されている。 /dev/random から生成される疑似乱数の元ネタは予測不可能な値である必要がある。ハードウェアによる疑似乱数生成器が存在しない場合、ソフトウェアで何とかしないといけない。

Linux カーネルでは、疑似乱数の元ネタを各種デバイスドライバで生成される値を使用する。それら生成された値を、/dev/random ドライバで管理するエントロピー・プールに溜め込み、ユーザ空間から要求があった際に、エントロピー・プールから疑似乱数を生成し、提供される。

疑似乱数の元ネタを生成しているドライバをリストしてみる。（本当はもっとヒットするが、てきとうに割愛）

% head -n4 Makefile
VERSION = 3
PATCHLEVEL = 19
SUBLEVEL = 0
EXTRAVERSION = -rc5
% grep -n --exclude=drivers/char/random.c add_.\*_randomness **/*.c
block/blk-core.c:2549:      add_disk_randomness(rq->rq_disk);
drivers/char/hw_random/core.c:79:static void add_early_randomness(struct hwrng *rng)
drivers/char/hw_random/core.c:86:       add_device_randomness(bytes, bytes_read);
drivers/char/hw_random/core.c:98:   add_early_randomness(rng);
drivers/char/hw_random/core.c:354:      add_hwgenerator_randomness((void *)rng_fillbuf, rc,
drivers/char/hw_random/core.c:430:      add_early_randomness(rng);
drivers/input/input.c:152:  add_input_randomness(vals->type, vals->code, vals->value);
drivers/rtc/rtc-wm831x.c:112:       add_device_randomness(&reg, sizeof(reg));
drivers/scsi/scsi_lib.c:703:        add_disk_randomness(req->rq_disk);
drivers/usb/core/hub.c:2447:        add_device_randomness(udev->serial, strlen(udev->serial));
drivers/usb/core/hub.c:2449:        add_device_randomness(udev->product, strlen(udev->product));
drivers/usb/core/hub.c:2451:        add_device_randomness(udev->manufacturer,
kernel/irq/handle.c:176:    add_interrupt_randomness(irq, flags);
kernel/time/posix-cpu-timers.c:428: add_device_randomness((const void*) &tsk->se.sum_exec_runtime,
net/core/dev.c:1293:        add_device_randomness(dev->dev_addr, dev->addr_len);
net/core/dev.c:5842:    add_device_randomness(dev->dev_addr, dev->addr_len);
net/core/dev.c:6346:    add_device_randomness(dev->dev_addr, dev->addr_len);
(略)

予め確認したところ、 add_xxx_randomness という関数が /dev/random (drivers/char/random.c)ドライバで提供されているカーネル関数であり、引数で渡された値をエントロピー・プールに蓄えるらしい。その関数を呼び出すデバイスドライバ郡が上記となる。尚、疑似乱数の元ネタを各デバイスドライバで「生成」すると前述したが、「生成」といっても、デバイスからの入力データをユーザ空間に転送する過程で、その入力データを /dev/random ドライバに横流しするだけのようである。

また、エントロピー・プールが枯渇している場合は、/dev/random からは疑似乱数が取得できない。 Linux カーネルにおける /dev/random の仕様としては、十分なエントロピーがない場合は、/dev/random からの read が block される。（Non-blocking で read した場合は EAGAIN となる。）

実際にその状態を確認してみる。取得に先立ち、エントロピーの（貯蔵）状態を確認してみる。

% uname -rv
3.13.0-32-generic #57-Ubuntu SMP Tue Jul 15 03:51:08 UTC 2014
% cat /proc/sys/kernel/random/entropy_avail
894

そして、/dev/random から値を取得してみる。

% hexdump -C /dev/random
00000000  74 2d 94 82 8a 22 e5 87  a8 37 36 94 c6 05 a0 9f  |t-..."...76.....|
00000010  2a 26 c4 ec a5 49 a6 80  c8 ca 4f d7 5e 1b e6 fd  |*&...I....O.^...|
00000020  ce 39 a3 ce 7c 84 05 0a  07 1a d6 87 46 63 29 b5  |.9..|.......Fc).|
00000030  c7 62 b5 12 2c d8 b3 6f  43 4f 0e 85 5d 8e bb 49  |.b..,..oCO..]..I|
00000040  e9 98 46 d8 75 2d 3f 21  ec a5 05 9e 9a 53 ab 1b  |..F.u-?!.....S..|
00000050  87 c1 cb a0 86 08 11 ff  41 5a 4f 04 cf cc d7 cb  |........AZO.....|
00000060  e0 c8 53 e3 e4 88 92 1c  0d a9 3e 0c db 1a 4f 5d  |..S.......>...O]|
^C

hexdump コマンドは、EOF まで read し続けるが、0x70 バイト分のデータを表示したところで停止した。これは、エントロピーが不足し、/dev/random からの read が block されているから。（SIGINT して終了させる。）その直後、再度エントロピー状態を確認してみると、以下のような結果となった。

% cat /proc/sys/kernel/random/entropy_avail
23

確かに、読み出し前とは値が少なくなっていた。

Linux カーネルの /dev/random ドライバを確認してみると、/dev/random が read された際に、エントロピーの状態とその閾値を比較して block している箇所は以下のような実装となっていた。

static ssize_t
_random_read(int nonblock, char __user *buf, size_t nbytes)
{
(略)
                 wait_event_interruptible(random_read_wait,
                         ENTROPY_BITS(&input_pool) >=
                         random_read_wakeup_bits);

ENTROPY_BITS(&input_pool) は、procfs の entropy_avail で取得できる値である。対して、閾値となる random_read_wakeup_bits という変数は、以下のように定義されている。

/*
 * The minimum number of bits of entropy before we wake up a read on
 * /dev/random.  Should be enough to do a significant reseed.
 */
static int random_read_wakeup_bits = 64;

従って、/proc/sys/kernel/random/entropy_avail が 64 以上であれば、疑似乱数を取得できることになる。そんな /dev/random であるため、扱いに注意が必要である。たまたま体験した例では、Wi-Fi の WPA-PSK である。

WPA-PSK では、アクセスポイントとステーション間の 4way-handshake でお互いに疑似乱数が必要となるが、 Linux 用 wpa_supplicant ではその疑似乱数の取得に /dev/random を Non-blocking で使用し、 /dev/random から疑似乱数が取得できない場合、 4way-handshake を中断させてしまい、接続に失敗する。

もしそうなった場合、各種デバイスドライバからエントロピー・プールが貯め込まれるのを待てば解決するのだが、すぐに貯まるものでもない。ユーザ空間で直接、/dev/random を叩き、エントロピーを貯めこむためのツールもあるようだが、いずれにしても、暗号化のための鍵生成等、無意識に /dev/random は使われていると思うので、特殊な環境においては、エントロピー・プールの状態には注意が必要かもしれない。

/dev/random がダメなら /dev/urandom を使えばいいじゃない、という意見もあるが、それはまた別の話。