乱数生成

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 つのインターフェイスを提供します:

• getrandom(2) system call
• /dev/random
• /dev/urandom

歴史的に、/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 およびその他のハードウェア乱数生成器をエントロピーソースとして使用しています。

参照

• カーネル RNG の改善:
  • random: replace non-blocking pool with a Chacha20-based CRNG - ChaCha20 CRNG 導入(2016年)
  • random: try to actively add entropy rather than passively wait for it - CPU ベースのジッターエントロピーをフォールバックとして使用できるようにしました (2019)
  • Removing the Linux /dev/random blocking pool - /dev/random に /dev/urandom と同様に CRNG を使用させ、"真" のランダム性を提供しようとしませんでした (2020)
  • Random number generator enhancements for Linux 5.17 and 5.18 (2022)
  • random: use simpler fast key erasure flow on per-cpu keys - CRNG 設計の簡素化と最適化 (2022)
  • random: do not pretend to handle premature next security model - 新しいエントロピーをより迅速に使用できるようにしました (2022)
  • random: opportunistically initialize on /dev/urandom reads - x86 では /dev/urandom を /dev/random と同じくらい安全にしました (2022)
• Randomness - さまざまな RNG について説明した人気の科学記事
• ENT - ランダムシーケンス (エントロピー、カイ二乗検定、モンテカルロ、相関など) をテストするための簡単なプログラム
• An Analysis of OpenSSL's Random Number Generator - OpenSSL 機能における RNG 再シードのリスクに関する論文