暗号的に安全な疑似乱数生成器

暗号的に安全な疑似乱数生成器( CSPRNG )または暗号疑似乱数生成器( CPRNG ) は、暗号化での使用に適した特性を持つ疑似乱数生成器(PRNG) です。暗号乱数生成器( CRNG )とも呼ばれます。

ほとんどの暗号化アプリケーションでは乱数が必要です。次に例を示します。

• 鍵生成
• 初期化ベクトル
• ノンス
• ECDSAやRSASSA-PSSなどの特定の署名方式のソルト
• トークン生成

これらのアプリケーションに必要なランダム性の「品質」はさまざまです。たとえば、一部のプロトコルでnonceを作成する場合、一意性のみが必要です。一方、マスターキーの生成には、より高いエントロピーなどのより高い品質が必要です。また、ワンタイム パッドの場合、情報理論による完全な秘密の保証は、キー マテリアルが高エントロピーの真のランダム ソースから取得される場合にのみ有効であり、したがって、どのような種類の疑似乱数ジェネレータでも不十分です。

理想的には、CSPRNG での乱数生成では、高品質のソース (通常はオペレーティング システムの乱数API)から取得したエントロピーを使用します。ただし、このような一見独立したプロセスのいくつかで、予期しない相関関係が見つかりました。情報理論の観点からは、生成できる乱数の量、つまりエントロピーは、システムが提供するエントロピーに等しくなります。ただし、実際の状況では、利用可能なエントロピーが提供できる以上の乱数が必要な場合もあります。また、実行中のシステムから乱数を抽出するプロセスは、実際には時間がかかります。このような場合、CSPRNG が使用されることがあります。CSPRNG は、利用可能なエントロピーをより多くのビットに「拡張」できます。

通常の PRNG の要件は暗号的に安全な PRNG でも満たされますが、その逆は当てはまりません。CSPRNG の要件は 2 つのグループに分類されます。

1. 統計的ランダム性テストに合格しました:
   • すべてのCSPRNGは、次のビットテストを満たす必要があります。つまり、ランダムシーケンスの最初のkビットが与えられた場合、成功確率が50％より無視できないほど高い確率で（k +1）番目のビットを予測できる多項式時間アルゴリズムは存在しません。 ^[1] Andrew Yaoは1982年に、次のビットテストに合格したジェネレーターは、他のすべての多項式時間の統計的ランダム性テストに合格することを証明しました。^[2]
2. 初期状態や実行状態の一部が攻撃者に利用可能になった場合でも、深刻な攻撃に対して十分に耐えることができます。^[3]
   • すべてのCSPRNGは「状態侵害拡張攻撃」に耐えられる必要があります。^{[3] : 4}状態の一部またはすべてが明らかにされた（または正しく推測された）場合、明らかにされる前の乱数ストリームを再構築することは不可能である必要があります。さらに、実行中にエントロピー入力がある場合、入力の状態に関する知識を使用してCSPRNG状態の将来の状態を予測することは不可能である必要があります。

たとえば、検討中の PRNG が、バイナリ展開内の未知のポイントから始めて、πのビットを順番に計算して出力を生成する場合、π は正規数であると推測されるため、次のビット テストを満たし、統計的にランダムである可能性があります。ただし、このアルゴリズムは暗号的に安全ではありません。π のどのビットが現在使用されているか (つまり、アルゴリズムの状態) を判断できる攻撃者は、それ以前のすべてのビットも計算できます。

ほとんどの PRNG は CSPRNG として使用するには適しておらず、どちらの点でも不合格になります。まず、ほとんどの PRNG の出力はさまざまな統計テストではランダムに見えますが、リバース エンジニアリングには耐えられません。このような PRNG に合わせて調整された特殊な統計テストでは、乱数が実際にはランダムではないことが示される場合があります。次に、ほとんどの PRNG では、状態が明らかになると、過去の乱数をすべて遡及的に推測できるため、攻撃者は過去のメッセージだけでなく将来のメッセージもすべて読み取ることができます。

CSPRNG は、このタイプの暗号解読に抵抗するように明示的に設計されています。

漸近設定において、ある多項式pに対する決定論的多項式時間計算可能関数の族は、入力の長さ（任意のkに対して）を延長し、その出力が真のランダム性と計算上区別がつかない場合、すなわち、任意の確率的多項式時間アルゴリズムAに対して、識別子として 1 または 0 を出力する場合、 擬似乱数生成器（PRNG 、または一部の文献ではPRG）である。${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$${\displaystyle p(k)>k}$

${\displaystyle \left|\Pr _{x\gets \{0,1\}^{k}}[A(G(x))=1]-\Pr _{r\gets \{0,1\}^{p(k)}}[A(r)=1]\right|\leq \mu (k)}$

ある無視できる関数 に対して。^[4]（この表記は、xが集合Xから一様にランダムに選択されることを意味する。） ${\displaystyle \mu}$${\displaystyle x\gets X}$

同等の特徴付けがある：任意の関数族に対して、GがPRNGである場合、かつその場合のみ、Gの次の出力ビットは多項式時間アルゴリズムによって予測できない。^[5]${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$

ブロック長 の前方セキュア PRNGはPRNGであり、長さkの入力文字列は期間iの現在の状態であり、出力 ( 、) は次の状態と期間iの疑似ランダム出力ブロックで構成され、次の意味で状態侵害拡張に耐えます。初期状態がから一様ランダムに選択される場合、任意のiに対して、シーケンスはと計算上区別がつかず、 は から一様ランダムに選択されます。^[6]${\displaystyle t(k)}$${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}}$${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle y_{i}}$${\displaystyle s_{i+1}}$${\displaystyle y_{i}}$${\displaystyle s_{1}}$${\displaystyle \{0,1\}^{k}}$${\displaystyle (y_{1},y_{2},\dots ,y_{i},s_{i+1})}$${\displaystyle (r_{1},r_{2},\dots ,r_{i},s_{i+1})}$${\displaystyle r_{i}}$${\displaystyle \{0,1\}^{t(k)}}$

どの PRNG も、出力を次の状態と実際の出力に分割することで、ブロック長 を持つ前方セキュア PRNG に変換できます。これは、、 を設定することで行われます。この場合、G は、 が次の状態、 が現在の期間の疑似ランダム出力ブロックで ある前方セキュア PRNG になります。${\displaystyle G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$${\displaystyle p(k)-k}$${\displaystyle G(s)=G_{0}(s)\Vert G_{1}(s)}$${\displaystyle |G_{0}(s)|=|s|=k}$${\displaystyle |G_{1}(s)|=p(k)-k}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$

SanthaとVaziraniは、弱いランダム性を持つ複数のビットストリームを組み合わせることで、高品質の準ランダムビットストリームを生成できることを証明しました。^[7] さらに以前に、John von Neumannは、単純なアルゴリズムで任意のビットストリームのバイアスをかなり除去できることを証明しました。 ^[8]このアルゴリズムは、Santha-Vazirani設計のバリエーションを使用する前に、各ビットストリームに適用する必要があります。

CSPRNG 設計は 2 つのクラスに分けられます。

1. 暗号や暗号ハッシュなどの暗号プリミティブに基づく設計
2. 難しいとされる数学の問題に基づいたデザイン

• 安全なブロック暗号は、たとえばSP 800-90A のNISTがCTR_DRBGと呼ぶ特別な構造を使用してカウンター モードで実行することにより、CSPRNG に変換できます。CTR_DBRGは通常、Advanced Encryption Standard (AES) を使用します。
  • AES -CTR_DRBGは、AES暗号化を使用するシステムで乱数ジェネレーターとしてよく使用されます。^{[9] [10]}
  • NIST CTR_DRBG 方式では、要求されたランダム性が出力された後、追加のサイクルを実行してキーを消去します。これはパフォーマンスの観点からは無駄ですが、前方秘匿性の問題を直ちに引き起こすわけではありません。ただし、パフォーマンスへの影響を認識した NIST は、ポスト量子暗号プロジェクトへの提出に「拡張 AES-CTR-DRBG インターフェイス」を推奨しています。このインターフェイスでは、消去を介さずに複数のランダム性セットを生成でき、ユーザーが明示的に要求の終了を通知したときにのみ消去されます。その結果、「拡張インターフェイス」が誤用されると、キーが長時間メモリ内に残る可能性があります。新しい「高速キー消去」RNG は、ランダム性が要求されるとすぐにランダム性を持つキーを消去します。^[11]
• ストリーム暗号は CSPRNG に変換できます。これは、RC4、ISAAC、ChaCha20などで行われています。
• 暗号的に安全なハッシュは、たとえば NIST がHash_DRBGと呼ぶ構造を使用して、優れた CSPRNG のベースになる可能性もあります。
• HMACプリミティブは、たとえば NIST がHMAC_DRBGと呼ぶ構造の一部として、CSPRNG のベースとして使用できます。

• Blum Blum Shubアルゴリズムには、 2 次剰余問題の難しさに基づくセキュリティ証明があります。この問題を解決する唯一の既知の方法は係数を因数分解することであるため、整数因数分解の難しさは Blum Blum Shub アルゴリズムの条件付きセキュリティ証明を提供すると一般に考えられています。ただし、このアルゴリズムは非常に非効率的であるため、極度のセキュリティが必要な場合を除き、実用的ではありません。
• Blum -Micali アルゴリズムは、離散対数問題の難しさに基づいてセキュリティが証明されていますが、非常に非効率的です。
• Certicomの Daniel Brown は、決定 Diffie-Hellman 仮定、x 対数問題、および切り捨て点問題の困難性に基づいて、 2006 年にDual EC DRBGのセキュリティ証明を作成しました。2006年の証明では、Dual_EC_DRBG 標準よりも低いoutlen (反復ごとに提供されるビット数) を明示的に想定し、 Dual_EC_DRBG 標準のPとQ (2013 年に NSA によってバックドアが仕掛けられている可能性があることが明らかになりました) がバックドアのない値に置き換えられています。

「実用的な」CSPRNG スキームには、CSPRNG アルゴリズムだけでなく、シードを秘密にしたままそれを初期化 (「シード」)する方法も含まれます。次のような多数のスキームが定義されています。

• Unix ライクなシステムでの /dev/randomの実装。
  • Yarrow は、シード入力のエントロピー品質を評価しようとし、内部で SHA-1 と 3DES を使用します。Yarrow は、 2019 年 12 月頃までmacOSやその他の Apple OS で使用されていましたが、その後 Fortuna に切り替わりました。
  • Fortunaは Yarrow の後継であり、入力のエントロピー品質を評価しようとしません。SHA-256 と「任意の適切なブロック暗号」を使用します。Fortuna は FreeBSD で使用されます。Apple は 2019 年 12 月頃から、ほとんどまたはすべての Apple OS を Fortuna に変更しました。
  • LinuxカーネルCSPRNGは、ChaCha20を使用してデータを生成し、^[12] BLAKE2を使用してエントロピーを取り込みます。^[13]
• arc4random は、 /dev/randomからシードする Unix 系システムの CSPRNG です。元々はRC4に基づいていますが、現在ではすべての主要な実装でChaCha20 が使用されています。 ^{[14] [15] [16]}
• CryptGenRandom は、 Windows で提供されるMicrosoftのCryptoAPIの一部です
• ANSI X9.17標準（金融機関の鍵管理（卸売） ）は、 FIPS標準としても採用されています。入力として、 TDEA（鍵オプション2）鍵バンドルkと64ビットの乱数シード s （の初期値）を受け取ります。^[17]乱数が必要になるたびに、次の手順が実行されます。
  1. 現在の日付/時刻D を可能な限り最大の解像度で取得します。
  2. 一時値t = TDEA _k ( D )を計算します。
  3. ランダム値x = TDEA _k ( s ⊕ t )を計算します。ここで、 ⊕ はビットごとの排他的論理和を表します。
  4. シードs = TDEA _k ( x ⊕ t )を更新します。

明らかに、この技術はどんなブロック暗号にも簡単に一般化できます。AESが提案されています。^[18]キーkが漏洩した場合、X9.17ストリーム全体を予測することができます。この弱点がYarrow作成の理由として挙げられています。^[19]

X9.17 を除く上記のすべてのスキームは、CSPRNG の状態と追加のエントロピー ソースを混合します。したがって、出力が初期状態によって完全に決定されないという意味で、これらは「純粋な」疑似乱数ジェネレータではありません。この追加は、初期状態が侵害された場合でも攻撃を防ぐことを目的としています。^[a]

いくつかの CSPRNG が標準化されています。例:

• FIPS 186-4 ^[21]
• NIST SP 800-90A

• NIST SP 800-90A 改訂1

• ANSI X9.17-1985 付録 C
• ANSI X9.31-1998 付録A.2.4
• ANSI X9.62-1998 付録 A.4、ANSI X9.62-2005 付録 D (HMAC_DRBG) により廃止

優れた参考資料はNISTによって維持されている。^[26]

新しい CSPRNG 設計の統計テストのための標準もあります。

• 乱数および疑似乱数ジェネレータの統計テストスイート、NIST特別出版物800-22。^[27]

ガーディアン紙とニューヨークタイムズ紙は2013年、国家安全保障局（NSA）がNIST SP 800-90Aの疑似乱数生成器（PRNG）にバックドアを挿入し、NSAがDual EC DRBGで暗号化された資料を容易に復号化できるようになったと報じた。両紙は^{[28] [29]}、独立系セキュリティ専門家が長らく疑っていたように^{[30]、 NSAがCSPRNG標準800-90に脆弱性を持ち込んでいたと報じた。これは}エドワード・スノーデン氏がガーディアン紙に漏洩した極秘文書の1つによって初めて確認された。NSAは2006年にNISTのセキュリティ標準草案の独自バージョンを世界中で承認してもらうために秘密裏に活動していた。漏洩した文書には「最終的にNSAが唯一の編集者になった」と記されている。 Dual_EC_DRBGには盗み見的なバックドアが存在する可能性があり、その他の重大な欠陥があることが知られているにもかかわらず、 RSA Securityなどのいくつかの企業は、2013年にバックドアが確認されるまでDual_EC_DRBGを使い続けました^{。 [31]} RSA Securityは、そのためにNSAから1000万ドルの支払いを受けました。 ^[32]

2017年10月23日、ペンシルベニア大学とジョンズホプキンス大学の暗号学者であるシャナン・コーニー、マシュー・グリーン、ナディア・ヘニンガーは、ハードウェアベンダーがANSI X9.31 RNGアルゴリズムにハードコードされたシードキーを使用するWPA2に対するDUHK（ハードコードされたキーを使用しないでください）攻撃の詳細を発表し、「攻撃者は暗号化されたデータをブルートフォース攻撃して残りの暗号化パラメータを発見し、Webセッションまたは仮想プライベートネットワーク（VPN）接続の暗号化に使用されるマスター暗号化キーを推測できる」と述べています。^{[33] [34]}

第二次世界大戦中、日本は外交通信に暗号機を使用していましたが、使用された「鍵値」が十分にランダムではなかったため、米国はそれを解読してメッセージを読むことができました。

ウィキブックの暗号化には、乱数生成に関するページがあります。

• RFC  4086、セキュリティのためのランダム性要件
• 暗号的に安全な予測不可能な乱数のための Java「エントロピー プール」。2008 年 12 月 2 日にWayback Machineにアーカイブされました。
• 暗号的に強力な疑似乱数ジェネレーター (PRNG) を提供する Java 標準クラス。
• CryptoAPI を使用せずに Windows 上で暗号的に安全な乱数を生成する
• ANSI-NIST 楕円曲線 RNG の推測セキュリティ、Daniel RL Brown、IACR ePrint 2006/117。
• NIST SP 800-90 楕円曲線乱数ジェネレータのセキュリティ分析、Daniel RL Brown および Kristian Gjosteen、IACR ePrint 2007/048。CRYPTO 2007 に掲載予定。
• 二重楕円曲線疑似乱数生成器の暗号解析、Berry Schoenmakers および Andrey Sidorenko、IACR ePrint 2006/190。
• DDH 仮定に基づく効率的な疑似乱数生成器、Reza Rezaeian Farashahi、Berry Schoenmakers、Andrey Sidorenko、IACR ePrint 2006/321。
• Linux 乱数ジェネレーターの分析、Zvi Gutterman、Benny Pinkas、Tzachy Reinman。
• NIST 統計テスト スイートのドキュメントとソフトウェアのダウンロード。