「乱数生成」の版間の差分
Kusakata.bot (トーク | 投稿記録) 細 (文字列「http://www.ietf.org/」を「https://www.ietf.org/」に置換) |
(同期) |
||
9行目: | 9行目: | ||
カーネルに含まれている RNG である [[wikipedia:ja:/dev/random|/dev/{u}random]] は暗号鍵の作成などに使われるような高いセキュリティレベルを必要とするランダムデータの生成を行うときに使うことを強く推奨されます。この乱数生成器はデバイスドライバなどの情報源から環境ノイズをエントロピープールに集めます。 |
カーネルに含まれている RNG である [[wikipedia:ja:/dev/random|/dev/{u}random]] は暗号鍵の作成などに使われるような高いセキュリティレベルを必要とするランダムデータの生成を行うときに使うことを強く推奨されます。この乱数生成器はデバイスドライバなどの情報源から環境ノイズをエントロピープールに集めます。 |
||
− | {{ic|man random}} コマンドではライブラリ関数の man ページ |
+ | {{ic|man random}} コマンドではライブラリ関数の man ページ {{man|3|random}} が表示されてしまうので注意してください。{{ic|/dev/random}} デバイスに関する情報が必要なときは {{ic|man 4 random}} を実行して表示される {{man|4|random}} を読んで下さい。 |
=== /dev/random === |
=== /dev/random === |
||
29行目: | 29行目: | ||
=== /dev/urandom === |
=== /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]。 |
||
+ | {{ic|/dev/random}} と反対に、{{ic|/dev/urandom}} は初期のランダムなシードを使ってストリーム暗号の元とします [https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=e192be9d9a30555aae2ca1dc3aad37cba484cd4a] (カーネル 4.8 以上)。 |
||
+ | |||
+ | ストリーム暗号を使用することで、ディスクの徹底消去や[[ディスクの完全消去#ブロックデバイス暗号化の準備|ブロックデバイス暗号化の準備]]、LUKS キースロットの消去などの目的に叶うような高品質な疑似乱数データを大量に生成します。 |
||
{{Warning|長期間の暗号鍵を生成するのに {{ic|/dev/urandom}} は推奨されません。}} |
{{Warning|長期間の暗号鍵を生成するのに {{ic|/dev/urandom}} は推奨されません。}} |
||
+ | |||
+ | システムの状態や乱数の目的によって使用価値は大きく変わります。例えば、システムが立ち上がったばかりなのか、あるいはエントロピープールを十分に満たすだけの時間を経ているのかは大変重要です。 |
||
+ | |||
+ | 以下の記事は様々な視点から {{ic|/dev/urandom}} の有用性を説明しています: |
||
+ | |||
+ | * [http://www.2uo.de/myths-about-urandom/ Myths about urandom] - 非常に勉強になりますが誤謬も含まれています。 |
||
+ | * [http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ Safely generate random numbers] - エントロピーの収集についてカーネルの仕組みを変更しようとしたときに考えるべきことを説明しています。 |
||
+ | |||
+ | Arch Linux の場合、{{ic|/dev/urandom}} には以下のことが当てはまります: |
||
+ | # 可能であればカーネルの {{ic|getrandom()}} システムコールを使ってください。{{ic|/dev/urandom}} が正しく初期化されていることを確認できます。{{man|2|getrandom}} を参照。 |
||
+ | # {{ic|/dev/urandom}} デバイスを使用して長期目的でエントロピーを生成する場合、正しく初期化されることを必ず確認してください。 |
||
+ | # 起動時に {{ic|/dev/urandom}} のエントロピーを使用する重要なサービスがある場合は注意してください。最近のシステムでもカーネルのエントロピー初期化は数秒かかることがあり、(仮想化環境など) 場合によってはさらに時間がかかります。カーネルは警告はしますが、いつまでもというわけではありません [https://patchwork.kernel.org/patch/9173499/]。 |
||
+ | |||
+ | 出力例: |
||
+ | $ dmesg | grep -e random: |
||
+ | ... |
||
+ | [ 0.844818] random: systemd-udevd: uninitialized urandom read (16 bytes read) |
||
+ | [ 7.022171] random: fast init done |
||
+ | [ 12.916705] random: crng init done |
||
+ | |||
+ | 上記の例では、プールを初期化する十分なエントロピーをカーネルが収集する前にデフォルトのブートターゲットに達してしまっています。systemd は起動の初期段階でエントロピーを必要とするため [https://github.com/systemd/systemd/issues/4167]、ブートプロセスでエントロピープールが枯渇してしまう可能性があります。 |
||
+ | |||
+ | 起動段階で問題があると、{{ic|/dev/urandom}} プールから十分な品質のエントロピーを得られないまま他のサービス (ウェブサーバーの [[OpenSSL]] セッションなど) が起動します。そして、OpenSSL の通常の設定では同じシードを使い続け、新しいシードを要求するのはセッションを再起動したときだけです。 |
||
== 高速な RNG == |
== 高速な RNG == |
||
43行目: | 69行目: | ||
== 参照 == |
== 参照 == |
||
* [https://www.ietf.org/rfc/rfc4086.txt RFC4086 - Randomness Requirements for Security] (Section 7.1.2 for /dev/random) |
* [https://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] - |
+ | * [http://lkml.indiana.edu/hypermail/linux/kernel/1302.1/00479.html Linux Kernel ML] - /dev/random のスループットを高めるパッチの議論 (2013年2月) |
− | * [http://eprint.iacr.org/2013/338 A challenge on /dev/random robustness] ( |
+ | * [http://eprint.iacr.org/2013/338 A challenge on /dev/random robustness] (2013年6月) |
− | * [http://eprint.iacr.org/2014/167 |
+ | * [http://eprint.iacr.org/2014/167 エントロピーが少ない状態での /dev/random, Yarrow, Fortuna の挙動の解析] (2014年3月) |
* [http://www.random.org/randomness/ Randomness] - 様々な RNG について説明している科学記事 |
* [http://www.random.org/randomness/ Randomness] - 様々な RNG について説明している科学記事 |
||
− | * [http://www.fourmilab.ch/random/ ENT] - |
+ | * [http://www.fourmilab.ch/random/ ENT] - ランダムシーケンスをテストするシンプルなプログラム (エントロピー, カイ二乗検定, モンテカルロ, 相関など) |
− | * [http://www.codeproject.com/Articles/795845/Arduino-Hardware-Random-Sequence-Generator-with-Ja DIY HRNG] - |
+ | * [http://www.codeproject.com/Articles/795845/Arduino-Hardware-Random-Sequence-Generator-with-Ja DIY HRNG] - 安価な DIY の Arduino HRNG の例 |
+ | * [https://eprint.iacr.org/2016/367 An Analysis of OpenSSL's Random Number Generator] - Paper on RNG reseeding risks in OpenSSL functionality |
||
+ | * [http://www.chronox.de/lrng/doc/lrng.pdf Linux Random Number Generator – A New Approach] - デバイスのアップデートに関する論文 (2017年3月) |
2018年2月16日 (金) 21:39時点における版
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/urandom
/dev/random
と反対に、/dev/urandom
は初期のランダムなシードを使ってストリーム暗号の元とします [1] (カーネル 4.8 以上)。
ストリーム暗号を使用することで、ディスクの徹底消去やブロックデバイス暗号化の準備、LUKS キースロットの消去などの目的に叶うような高品質な疑似乱数データを大量に生成します。
システムの状態や乱数の目的によって使用価値は大きく変わります。例えば、システムが立ち上がったばかりなのか、あるいはエントロピープールを十分に満たすだけの時間を経ているのかは大変重要です。
以下の記事は様々な視点から /dev/urandom
の有用性を説明しています:
- Myths about urandom - 非常に勉強になりますが誤謬も含まれています。
- Safely generate random numbers - エントロピーの収集についてカーネルの仕組みを変更しようとしたときに考えるべきことを説明しています。
Arch Linux の場合、/dev/urandom
には以下のことが当てはまります:
- 可能であればカーネルの
getrandom()
システムコールを使ってください。/dev/urandom
が正しく初期化されていることを確認できます。getrandom(2) を参照。 /dev/urandom
デバイスを使用して長期目的でエントロピーを生成する場合、正しく初期化されることを必ず確認してください。- 起動時に
/dev/urandom
のエントロピーを使用する重要なサービスがある場合は注意してください。最近のシステムでもカーネルのエントロピー初期化は数秒かかることがあり、(仮想化環境など) 場合によってはさらに時間がかかります。カーネルは警告はしますが、いつまでもというわけではありません [2]。
出力例:
$ dmesg | grep -e random: ... [ 0.844818] random: systemd-udevd: uninitialized urandom read (16 bytes read) [ 7.022171] random: fast init done [ 12.916705] random: crng init done
上記の例では、プールを初期化する十分なエントロピーをカーネルが収集する前にデフォルトのブートターゲットに達してしまっています。systemd は起動の初期段階でエントロピーを必要とするため [3]、ブートプロセスでエントロピープールが枯渇してしまう可能性があります。
起動段階で問題があると、/dev/urandom
プールから十分な品質のエントロピーを得られないまま他のサービス (ウェブサーバーの OpenSSL セッションなど) が起動します。そして、OpenSSL の通常の設定では同じシードを使い続け、新しいシードを要求するのはセッションを再起動したときだけです。
高速な RNG
長い暗号鍵の生成などは行わないアプリケーションの場合、パフォーマンスとセキュリティの折り合いをつけて擬似乱数生成器を使うこともあります。Arch Linux のリポジトリには以下のような擬似乱数生成器が存在します:
また、Yarrow (FreeBSD/OS-X) や Fortuna (Yarrow の後継) のような暗号論的擬似乱数生成器もあります。
参照
- RFC4086 - Randomness Requirements for Security (Section 7.1.2 for /dev/random)
- Linux Kernel ML - /dev/random のスループットを高めるパッチの議論 (2013年2月)
- A challenge on /dev/random robustness (2013年6月)
- エントロピーが少ない状態での /dev/random, Yarrow, Fortuna の挙動の解析 (2014年3月)
- Randomness - 様々な RNG について説明している科学記事
- ENT - ランダムシーケンスをテストするシンプルなプログラム (エントロピー, カイ二乗検定, モンテカルロ, 相関など)
- DIY HRNG - 安価な DIY の Arduino HRNG の例
- An Analysis of OpenSSL's Random Number Generator - Paper on RNG reseeding risks in OpenSSL functionality
- Linux Random Number Generator – A New Approach - デバイスのアップデートに関する論文 (2017年3月)