「乱数生成」の版間の差分

提供: ArchWiki
ナビゲーションに移動 検索に移動
(内容が重複しているのでマージした)
(→‎参照: 情報を更新)
 
(2人の利用者による、間の5版が非表示)
1行目: 1行目:
[[Category:暗号]]
+
[[Category:暗号]]
 
[[en:Random number generation]]
 
[[en:Random number generation]]
 
[[Wikipedia:Random number generation]] より:
 
[[Wikipedia:Random number generation]] より:
7行目: 7行目:
   
 
== カーネル内蔵の RNG ==
 
== カーネル内蔵の RNG ==
カーネルに含まれている RNG である [[wikipedia:ja:/dev/random|/dev/{u}random]] は暗号鍵の作成などに使われるような高いセキュリティレベルを必要とするランダムデータの生成を行うときに使うことを強く推奨されます。この乱数生成器はデバイスドライバなどの情報源から環境ノイズをエントロピープールに集めます。
 
   
  +
{{Note|Linux RNG は近年大幅に改良されており、4.x および 5.x カーネルシリーズでは多くの変更が加えられています。そのため、それについて存在する情報の多くは古いものです。このページでは、Arch Linux の [[カーネル#公式にサポートされているカーネル|公式にサポートされているカーネル]] を含む最新のカーネルに適用できる現在の実装と動作について説明します。}}
{{ic|man random}} コマンドではライブラリ関数の man ページ {{man|3|random}} が表示されてしまうので注意してください。{{ic|/dev/random}} デバイスに関する情報が必要なときは {{ic|man 4 random}} を実行して表示される {{man|4|random}} を読んで下さい。
 
   
  +
[https://github.com/torvalds/linux/blob/master/drivers/char/random.c Linux カーネルの組み込み RNG] は、暗号的に安全な擬似乱数データを生成します。これは、ハードウェア RNG、割り込み、CPU ベースのジッターエントロピーなどのさまざまなソースから [[wikipedia:Entropy_(information_ Theory)|entropy]] を収集することによって機能します。単一のエントロピーソースのみに依存することはありません。エントロピーは [[wikipedia:ja:BLAKE_(hash_function)#BLAKE2|BLAKE2s 暗号化ハッシュ関数]] を使用して抽出され、[[wikipedia:ja:Salsa20#ChaCha_variant|ChaCha20]] CRNG (暗号化乱数ジェネレーター) をシードするために使用されます。カーネルが実行されている限り、エントロピーは収集され続け、CRNG は定期的に再シードされます。
=== /dev/random ===
 
{{ic|/dev/random}} は4096ビット (512バイト) のエントロピープールを使用してランダムデータを生成します。エントロピープールが空になると、プールがまた補充されるまで待機します (これには時間がかかります)。{{ic|/dev/random}} は暗号鍵 (SSL, SSH, dm-crypt の LUKS など) の生成のために設計されており、HDD の中身の消去に使うのは現実的ではありません。システムに[[Wikipedia:Hardware_random_number_generator#Using_observed_events|十分なエントロピーが収集される]]まで止まってしまって、ディスクの消去にものすごく時間がかかるためです。エントロピーが枯渇しているような環境だと (例: リモートサーバー)、永遠に終わらないかもしれません。巨大なディレクトリで検索コマンドを実行するとか、X でマウスを動かすなどをすればエントロピープールは段々と溜まっていきますが、そもそもプールサイズ自体がディスクの消去を行うには不十分な造りになっています。
 
   
  +
Linux RNG は、ユーザー空間がランダムデータを取得するための 3 つのインターフェイスを提供します:
{{ic|/proc/sys/kernel/random/entropy_avail}} と {{ic|/proc/sys/kernel/random/poolsize}} を比較することでシステムのエントロピープールを目で追うことができます。
 
   
  +
* {{man|2|getrandom}} system call
Linux カーネル 2.4 ではエントロピーのプールサイズを変更できるように書き換え可能な {{ic|/proc}} エントリが出来ましたが、新しいカーネルでは {{ic|read_wakeup_threshold}} と {{ic|write_wakeup_threshold}} しか書き換えできないようになっています。現在、プールサイズはカーネルの {{ic|/drivers/char/random.c}} の275行目でハードコード (決め打ち) されています:
 
  +
* {{ic|/dev/random}}
  +
* {{ic|/dev/urandom}}
   
  +
歴史的に、{{ic|/dev/random}} は {{ic|/dev/urandom}} よりも強力な乱数を提供すると考えられてきた。しかし、{{ic|/dev/random}} と {{ic|/dev/urandom}} の挙動は時間とともに収束し、x86-64 システム上では同等になっています。Arch Linux は x86-64 しかサポートしていないので、Arch Linux では {{ic|/dev/random}} は {{ic|/dev/urandom}} は等価です。(これは全ての x86-64 CPU に RDTSC 命令が存在するということは、[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/char/random.c?h=v6.1#n1205 CPU ベース jitterentropy アルゴリズム] が常にエントロピーを生成できるということであり、言うまでもなくほとんどの x86-64 CPU は [[wikipedia:RDRAND|RDRAND]] もサポートしているからです)
{{bc|/*
 
* Configuration information
 
*/
 
#define '''INPUT_POOL_WORDS 128'''
 
#define '''OUTPUT_POOL_WORDS 32'''
 
...}}
 
   
  +
他のアーキテクチャ (具体的には、高速サイクルカウンターを持たないアーキテクチャ) では、2 つの違いが残っています。それは、カーネルが CRNG が適切に初期化されたと推定するまで、{{ic|/dev/random}} ブロックをブロックすることです。 {{ic|/dev/urandom}} はそうではありません。したがって、一般的な場合、ユーザーとアプリケーションは、長期暗号鍵を生成するときに {{ic|/dev/random}} を使用するか、デフォルトで {{man|2|getrandom}} を使用するという従来のガイダンスに従う必要があります。
カーネルのプールサイズは {{ic|INPUT_POOL_WORDS * OUTPUT_POOL_WORDS}} で求めることができ、既に述べたように、4096ビットとなります。
 
{{Warning|あなたの [http://everything2.com/title/Compromising+%252Fdev%252Frandom 制御下] にない環境では {{ic|/dev/random}} を使って''重要な''暗号鍵を生成してはいけません。例えば、共有サーバーの環境などを想定してください。別の環境で鍵を作成してから転送するようにしましょう。暗号学者 D. J. Bernstein はこの問題を [http://blog.cr.yp.to/20140205-entropy.html Mark Twain の名言] で説明しています。}}
 
   
  +
{{ic|/dev/random}} は真のランダム データを提供することを目的とするのではなく、むしろ暗号的に安全なランダムデータ (現実世界のすべてのユースケースに十分なデータ) を提供することを目的としているため、それを読み取ってもカーネルのエントロピープールが枯渇することはなくなりました。したがって、{{ic|/proc/sys/kernel/random/entropy_avail}} には常に 256 が含まれている必要があります。これは、ChaCha20 キーのビット単位のサイズです。このファイルにさらに大きな値が含まれることを期待したり、値が "低すぎる" 場合にユーザーがアクションを実行することを期待した過去の文書は無視できます。
=== /dev/urandom ===
 
   
  +
== 代替案 ==
{{ic|/dev/random}} と反対に、{{ic|/dev/urandom}} は初期のランダムなシードを使ってストリーム暗号の元とします [https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=e192be9d9a30555aae2ca1dc3aad37cba484cd4a] (カーネル 4.8 以上)。
 
   
  +
暗号的に安全な乱数を必要としないアプリケーションは、単純に非暗号化乱数生成器 (例:{{man|3|random}}) を使用できます。
ストリーム暗号を使用することで、ディスクの徹底消去や[[ディスクの完全消去#ブロックデバイス暗号化の準備|ブロックデバイス暗号化の準備]]、LUKS キースロットの消去などの目的に叶うような高品質な疑似乱数データを大量に生成します。
 
   
  +
暗号的に安全な乱数を必要とするアプリケーションの場合、通常、カーネルの RNG 以外には何も必要ありません。歴史的に、カーネルの RNG はかなり遅く、可能な限り多くのエントロピーソースを活用していませんでしたが、その後、x86-64 で最大 400 MB/秒のスループットを提供し、より多くのエントロピーソースを利用できるように改良されました。[[ディスクの完全消去|ディスクの完全消去]] など、かなり高いスループットの乱数を必要とする場合でも、{{ic|/dev/urandom}} から読み取るだけで問題なく動作します。
{{Warning|長期間の暗号鍵を生成するのに {{ic|/dev/urandom}} は推奨されません。}}
 
   
  +
カーネルの RNG を直接使用しないことが合理的となるケースには、次のようなものがあります:
システムの状態や乱数の目的によって使用価値は大きく変わります。例えば、システムが立ち上がったばかりなのか、あるいはエントロピープールを十分に満たすだけの時間を経ているのかは大変重要です。
 
   
  +
* まれに、アプリケーションは、'''非常に''' 高いスループット、またはシステムコールのオーバーヘッドが許容できない非常に低いレイテンシーを備えた、暗号的に安全な乱数を必要とします。ユーザースペース CRNG はこの問題を解決できます。 ユーザー空間 CRNG は、再シードなどのモジュロを考慮して、カーネルの RNG と少なくとも同等の安全性を確保するために、カーネルの RNG からシードする必要があります。
以下の記事は様々な視点から {{ic|/dev/urandom}} の有用性を説明しています:
 
   
  +
* 一部のアプリケーションは、ユーザー空間 CRNG を使用して暗号的に安全な乱数を生成するための十分に確立された API がすでに存在するドメインで動作します。たとえば、アプリケーションが [[OpenSSL]] を使用している場合、OpenSSL の {{man|3|RAND_bytes}} を使用することが合理的である可能性があります。アプリケーションが Java で書かれている場合、[https://docs.oracle.com/javase/8/docs/api/java/security/SecureRandom.html {{ic|java.security.SecureRandom}}] を使用するのが合理的かもしれません。通常、これらの API の基礎となるユーザー空間 CRNG は、カーネルの RNG を使用して自動的にシードされます。
* [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] - エントロピーの収集についてカーネルの仕組みを変更しようとしたときに考えるべきことを説明しています。
 
   
  +
* カーネルの RNG にまだ組み込まれていない追加のエントロピーソースを使用したい場合は、カーネルの RNG を直接使用しない方が合理的かもしれません。たとえば、[[Haveged]] は、ジッターエントロピーを使用して生成されたランダムデータを提供できます。可能であれば、追加のエントロピーソースはカーネルの RNG を置き換えるのではなく、追加のエントロピーソースとカーネルの RNG の両方からユーザー空間 CRNG をシードすることによって、カーネルの RNG と組み合わせて使用​​する必要があります。追加のエントロピーを {{ic|/dev/random}} に書き込んでカーネルの RNG に組み込むことも可能ですが、カーネルの CRNG 再シードスケジュールにより、これが有効になるまでに最大 60 秒かかる場合があります。注: カーネルはすでに [[wikipedia:RDRAND|RDSEED]] およびその他のハードウェア乱数生成器をエントロピーソースとして使用しています。
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
 
   
  +
* カーネル RNG の改善:
上記の例では、プールを初期化する十分なエントロピーをカーネルが収集する前にデフォルトのブートターゲットに達してしまっています。systemd は起動の初期段階でエントロピーを必要とするため [https://github.com/systemd/systemd/issues/4167]、ブートプロセスでエントロピープールが枯渇してしまう可能性があります。
 
  +
** [https://git.kernel.org/linus/e192be9d9a30555a random: replace non-blocking pool with a Chacha20-based CRNG] - ChaCha20 CRNG 導入(2016年)
 
  +
** [https://git.kernel.org/linus/50ee7529ec4500c8 random: try to actively add entropy rather than passively wait for it] - CPU ベースのジッターエントロピーをフォールバックとして使用できるようにしました (2019)
起動段階で問題があると、{{ic|/dev/urandom}} プールから十分な品質のエントロピーを得られないまま他のサービス (ウェブサーバーの [[OpenSSL]] セッションなど) が起動します。そして、OpenSSL の通常の設定では同じシードを使い続け、新しいシードを要求するのはセッションを再起動したときだけです。
 
  +
** [https://lwn.net/Articles/808575/ Removing the Linux /dev/random blocking pool] - {{ic|/dev/random}} に {{ic|/dev/urandom}} と同様に CRNG を使用させ、"真" のランダム性を提供しようとしませんでした (2020)
 
  +
** [https://www.zx2c4.com/projects/linux-rng-5.17-5.18/ Random number generator enhancements for Linux 5.17 and 5.18] (2022)
== 代替案 ==
 
  +
** [https://git.kernel.org/linus/186873c549df11b6 random: use simpler fast key erasure flow on per-cpu keys] - CRNG 設計の簡素化と最適化 (2022)
 
  +
** [https://git.kernel.org/linus/e85c0fc1d94c5248 random: do not pretend to handle premature next security model] - 新しいエントロピーをより迅速に使用できるようにしました (2022)
長い暗号鍵の生成などは行わないアプリケーションの場合、パフォーマンスとセキュリティの折り合いをつけて[[Wikipedia:ja:擬似乱数|擬似乱数生成器]]を使うこともあります。Arch Linux のリポジトリには以下のような擬似乱数生成器が存在します:
 
  +
** [https://git.kernel.org/linus/48bff1053c172e6c random: opportunistically initialize on /dev/urandom reads] - x86 では {{ic|/dev/urandom}} を {{ic|/dev/random}} と同じくらい安全にしました (2022)
 
  +
* [https://www.random.org/randomness/ Randomness] - さまざまな RNG について説明した人気の科学記事
* [[Haveged]]
 
  +
* [https://www.fourmilab.ch/random/ ENT] - ランダムシーケンス (エントロピー、カイ二乗検定、モンテカルロ、相関など) をテストするための簡単なプログラム
* [[rng-tools]]
 
  +
* [https://eprint.iacr.org/2016/367 An Analysis of OpenSSL's Random Number Generator] - OpenSSL 機能における RNG 再シードのリスクに関する論文
 
[[Wikipedia:Yarrow_algorithm|Yarrow]] (macOS) や [[Wikipedia:Fortuna_(PRNG)|Fortuna]] (FreeBSD Yarrow の後継)のような[[Wikipedia:Cryptographically_secure_pseudorandom_number_generator|暗号的に安全な疑似乱数生成器]]もあります
 
 
== 参照 ==
 
* [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] - /dev/random のスループットを高めるパッチの議論 (2013年2月)
 
* [http://eprint.iacr.org/2013/338 A challenge on /dev/random robustness] (2013年6月)
 
* [http://eprint.iacr.org/2014/167 エントロピーが少ない状態での /dev/random, Yarrow, Fortuna の挙動の解析] (2014年3月)
 
* [http://www.random.org/randomness/ Randomness] - 様々な RNG について説明している科学記事
 
* [http://www.fourmilab.ch/random/ ENT] - ランダムシーケンスをテストするシンプルなプログラム (エントロピー, カイ二乗検定, モンテカルロ, 相関など)
 
* [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月)
 

2024年1月19日 (金) 04:37時点における最新版

Wikipedia:Random number generation より:

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

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

カーネル内蔵の RNG

ノート: Linux RNG は近年大幅に改良されており、4.x および 5.x カーネルシリーズでは多くの変更が加えられています。そのため、それについて存在する情報の多くは古いものです。このページでは、Arch Linux の 公式にサポートされているカーネル を含む最新のカーネルに適用できる現在の実装と動作について説明します。

Linux カーネルの組み込み RNG は、暗号的に安全な擬似乱数データを生成します。これは、ハードウェア RNG、割り込み、CPU ベースのジッターエントロピーなどのさまざまなソースから entropy を収集することによって機能します。単一のエントロピーソースのみに依存することはありません。エントロピーは BLAKE2s 暗号化ハッシュ関数 を使用して抽出され、ChaCha20 CRNG (暗号化乱数ジェネレーター) をシードするために使用されます。カーネルが実行されている限り、エントロピーは収集され続け、CRNG は定期的に再シードされます。

Linux RNG は、ユーザー空間がランダムデータを取得するための 3 つのインターフェイスを提供します:

歴史的に、/dev/random/dev/urandom よりも強力な乱数を提供すると考えられてきた。しかし、/dev/random/dev/urandom の挙動は時間とともに収束し、x86-64 システム上では同等になっています。Arch Linux は x86-64 しかサポートしていないので、Arch Linux では /dev/random/dev/urandom は等価です。(これは全ての x86-64 CPU に RDTSC 命令が存在するということは、CPU ベース jitterentropy アルゴリズム が常にエントロピーを生成できるということであり、言うまでもなくほとんどの x86-64 CPU は RDRAND もサポートしているからです)

他のアーキテクチャ (具体的には、高速サイクルカウンターを持たないアーキテクチャ) では、2 つの違いが残っています。それは、カーネルが CRNG が適切に初期化されたと推定するまで、/dev/random ブロックをブロックすることです。 /dev/urandom はそうではありません。したがって、一般的な場合、ユーザーとアプリケーションは、長期暗号鍵を生成するときに /dev/random を使用するか、デフォルトで getrandom(2) を使用するという従来のガイダンスに従う必要があります。

/dev/random は真のランダム データを提供することを目的とするのではなく、むしろ暗号的に安全なランダムデータ (現実世界のすべてのユースケースに十分なデータ) を提供することを目的としているため、それを読み取ってもカーネルのエントロピープールが枯渇することはなくなりました。したがって、/proc/sys/kernel/random/entropy_avail には常に 256 が含まれている必要があります。これは、ChaCha20 キーのビット単位のサイズです。このファイルにさらに大きな値が含まれることを期待したり、値が "低すぎる" 場合にユーザーがアクションを実行することを期待した過去の文書は無視できます。

代替案

暗号的に安全な乱数を必要としないアプリケーションは、単純に非暗号化乱数生成器 (例:random(3)) を使用できます。

暗号的に安全な乱数を必要とするアプリケーションの場合、通常、カーネルの RNG 以外には何も必要ありません。歴史的に、カーネルの RNG はかなり遅く、可能な限り多くのエントロピーソースを活用していませんでしたが、その後、x86-64 で最大 400 MB/秒のスループットを提供し、より多くのエントロピーソースを利用できるように改良されました。ディスクの完全消去 など、かなり高いスループットの乱数を必要とする場合でも、/dev/urandom から読み取るだけで問題なく動作します。

カーネルの RNG を直接使用しないことが合理的となるケースには、次のようなものがあります:

  • まれに、アプリケーションは、非常に 高いスループット、またはシステムコールのオーバーヘッドが許容できない非常に低いレイテンシーを備えた、暗号的に安全な乱数を必要とします。ユーザースペース CRNG はこの問題を解決できます。 ユーザー空間 CRNG は、再シードなどのモジュロを考慮して、カーネルの RNG と少なくとも同等の安全性を確保するために、カーネルの RNG からシードする必要があります。
  • 一部のアプリケーションは、ユーザー空間 CRNG を使用して暗号的に安全な乱数を生成するための十分に確立された API がすでに存在するドメインで動作します。たとえば、アプリケーションが OpenSSL を使用している場合、OpenSSL の RAND_bytes(3) を使用することが合理的である可能性があります。アプリケーションが Java で書かれている場合、java.security.SecureRandom を使用するのが合理的かもしれません。通常、これらの API の基礎となるユーザー空間 CRNG は、カーネルの RNG を使用して自動的にシードされます。
  • カーネルの RNG にまだ組み込まれていない追加のエントロピーソースを使用したい場合は、カーネルの RNG を直接使用しない方が合理的かもしれません。たとえば、Haveged は、ジッターエントロピーを使用して生成されたランダムデータを提供できます。可能であれば、追加のエントロピーソースはカーネルの RNG を置き換えるのではなく、追加のエントロピーソースとカーネルの RNG の両方からユーザー空間 CRNG をシードすることによって、カーネルの RNG と組み合わせて使用​​する必要があります。追加のエントロピーを /dev/random に書き込んでカーネルの RNG に組み込むことも可能ですが、カーネルの CRNG 再シードスケジュールにより、これが有効になるまでに最大 60 秒かかる場合があります。注: カーネルはすでに RDSEED およびその他のハードウェア乱数生成器をエントロピーソースとして使用しています。

参照