RNG実装のテストと検証

乱数生成器のテストには、根本的な難しさがあります。真にランダムな系列と、優れたPRNGから得られる擬似ランダム系列は、統計検定では同じように見えるのです。有限長のテストで系列がランダムであることを証明することはできません。統計によって検出できるのは、ある程度の確信度での非ランダム性だけです。テストによって、RNGに明らかな偏りやパターンがないことは検証できますが、暗号学的な安全性を証明することはできません。暗号用RNGのテストには、2つの異なる目的があります。(1) 統計的品質：出力分布が一様かつ独立しているように見えることを検証します。(2) 暗号学的強度：DRBGアルゴリズムが正しく実装され、セキュリティ上の主張が成り立つことを検証します。これらには異なるテスト方法が必要です。

NIST SP 800-22は、ビット系列を評価する15種類の統計検定を提供します。検定には次のものがあります。Frequency（monobit）test：1の割合が0.5に近いことを確認します。Block frequency test：各mビットブロック内の1の頻度を調べます。Runs test：同じビットが途切れずに連続するランの数を調べます。Longest run test：1が連続する最長ランの長さを調べます。Binary matrix rank test：系列から作成した二値行列のランクを調べます。Spectral test（DFT）：周期的なパターンを検出します。Overlapping template matching：特定のパターンの出現回数を数えます。Maurer's universal statistical test：系列を圧縮し、どの程度短くなるかを測定します。各検定はp値を生成し、p < 0.01は非ランダム性を示唆します。検定には100万〜10億ビットを使用します。

TestU01（L'EcuyerとSimard、2007年）は、RNGコミュニティで広く使用されている包括的な統計検定群です。SmallCrushは10個の検定で、約35秒かかり、簡単な確認に適しています。Crushは144個の検定で、約2時間かかります。BigCrushは160個の検定で、約24時間かかります。BigCrushは、NIST SP 800-22では見逃される微妙な相関を検出します。適切に設計された暗号用DRBG（HMAC_DRBG、CTR_DRBG）は、BigCrushに問題なく合格します。これは、多項式時間アルゴリズムにとって、その出力がランダムな出力と計算量的に識別不能だからです。非暗号用PRNG（Mersenne Twister、線形合同法生成器）は、BigCrushの一部の検定に失敗します。BigCrushに失敗した場合、そのRNGを暗号用途に使用すべきではないことを強く示します。

SP 800-90Bと90Aでは、DRBGが動作中に継続的に実行しなければならないヘルステストを規定しています。Continuous RNG Test（CRNGT）：生成した各ブロックを直前のブロックと比較し、同じ場合（RNGが停止している場合）はDRBGがエラー状態に入り、生成を停止しなければなりません。Repetition Count Test：エントロピー推定値から統計的に予想される回数を超えて、連続したサンプルが同じ値を繰り返した場合に失敗とします。Adaptive Proportion Test：あるウィンドウ内で最も頻繁に現れる値が、しきい値を超える回数出現した場合に失敗とします。これらのヘルステストは、エントロピー源の障害（停止したセンサーやHWRNGのハードウェア障害）を検出し、暗号鍵の生成が気付かないうちに損なわれることを防ぎます。

PractRandは、オンライン（ストリーミング）評価用に設計された最新のRNGテストツールです。あらかじめ長さを決めておく必要はなく、系列が生成されるそばから分析します。ギャップ検定、ビット分布検定、スペクトル検定などを、精度を適応的に変化させながら適用します。PractRandは、短い系列では良好な出力を生成するものの、数十億ビットにわたるとパターンが現れるRNGの検出に特に有効です。暗号用DRBGは、系列の長さにかかわらず、PractRandによってランダムな出力と区別できない出力を生成します。これは、計算量的識別不能性の実用上の定義です。PractRandはエントロピー源の評価にも使用され、ハードウェア障害や系統的な偏りを検出するために、/dev/urandomの出力やRDRANDの出力をテストします。

Cryptographic Algorithm Validation Program（CAVP）は、SP 800-90AのDRBG向けに公式テストベクトルを提供します。CAVPテストでは、既知解テスト（KAT）ベクトルを使ってNISTの自動テストシステムに実装を提出します。特定のエントロピー入力、nonce、パーソナライゼーション文字列、additional_inputが与えられたとき、実装は期待されるビット列を正確に出力しなければなりません。CAVPは統計的特性をテストするものではなく、アルゴリズムの正しさをテストします。FIPS 140-3認証では、モジュール境界内で使用されるすべての暗号アルゴリズムについてCAVP検証が必要です。CAVPのテストベクトルはNISTのACVP（Automated Crypto Validation Protocol）サーバーから公開されており、OpenSSL、mbedTLS、BoringSSLのテストスイートにも統合されています。

DRBGを安全に初期化するには、まずエントロピー源を検証する必要があります。SP 800-90Bでは、次の項目を定義しています。(1) エントロピー推定：統計検定を使ってビット当たりの実際のエントロピーを測定します（最小エントロピーの推定）。(2) 起動時テスト：初回使用前に、エントロピー源が有効な出力を生成することを確認します。(3) オンデマンドテスト：アプリケーションによって起動される任意のテストです。(4) ノイズ源のヘルステスト：ハードウェアの劣化を検出します。一般的なエントロピー源と推定エントロピーは次のとおりです。CPUのRDRAND/RDSEED：約1ビット/ビット（ハードウェア認証済み）、/dev/urandom：複数の源を混合するため、エントロピー推定は保守的です、リングオシレーターTRNG：設計に応じて0.5〜0.9ビット/ビット、ADCノイズ：0.1〜0.5ビット/ビット。SP 800-90Bの検証には、専門設備を用いた実験室での試験が必要です。

仮想環境では、RNGのテストに特有の課題が生じます。VMでは、起動時（ハードウェアイベントがない場合）やスナップショットの復元後（状態がリセットされた場合）に、エントロピーが不足することがあります。DockerコンテナはホストカーネルのRNGを共有するため、コンテナから基盤となるエントロピーの品質を直接テストすることはできません。VMデプロイメントのテスト項目は次のとおりです。(1) /dev/random の読み取りが完了するまでの時間を測定します。待ち時間が長い場合は、エントロピーが不足していることを示します。(2) 並行して起動したVMインスタンスで生成されるUUIDまたは鍵に重複がないかテストします（これはクラウドデプロイメントで実際に記録された障害モードです）。(3) VMでVIRTIO-RNG（virtio_rng.ko）がロードされていることを確認します。これにより、ホストからゲストへのエントロピー注入が行われます。(4) アプリケーションの起動シーケンスを監査します。十分なエントロピーが利用可能になる前に鍵生成が行われていないでしょうか。

RNGのフォーク安全性をテストすると、微妙な脆弱性を防止できます。プロセスがフォークすると、親プロセスと子プロセスが同じDRBG状態を共有するため、同一のシーケンスを生成してしまう可能性があります。検出方法は、N個の子プロセスを生成し、それぞれでUUIDを生成して、すべてのUUIDが一意であることを検証することです。2つでも一致すれば、そのRNGはフォーク安全ではありません。OpenSSLでは2020年にフォーク安全性のバグが修正されました（CVE-2020-1971はDRBGに直接関係するものではありませんが、パターンは類似しています）。現在のOpenSSLではPIDベースのシード更新を使用しています。前回の呼び出し以降にPIDが変わっている場合（フォークが発生したことを示します）、DRBGは自動的に再シードされます。これをテストするには、フォークの前後でテストを実行し、異なる出力を検証して再シードが行われたことを確認します。

RNG実装の実践的な監査チェックリストは次のとおりです。(1) RNGは時刻ベースのシードではなく、OS（getrandom、BCryptGenRandom）から初期化されていますか。(2) DRBGの種類は、NIST SP 800-90Aで承認された方式（Hash、HMAC、CTR）ですか。(3) シード長は、主張する安全性強度に対して十分ですか。(4) 再シードは定期的に、またはgenerate呼び出しを一定回数行った後に実行されますか。(5) 実装はフォーク安全性（フォーク後の再シード）に対応していますか。(6) 健全性テストは有効になっており、失敗時にシステムを停止しますか。(7) シャットダウン時に状態がゼロ化されますか。(8) CAVPテストベクトルはCI/CDで実行されていますか。(9) エントロピー推定値は文書化され、検証されていますか。(10) FIPS要件について、モジュールはFIPS 140-3認証を取得していますか。

過去のRNG障害は、問題の重大さを示しています。Debian OpenSSL（2006～2008年）では、パッチによってエントロピー収集コードが誤って2行削除され、シードプールが15ビットのPID空間に縮小しました。その結果、Debianユーザーベース全体で生成可能なSSH鍵はわずか32,767種類となりました。Debianで生成されたすべてのSSHホスト鍵とユーザー鍵を交換する必要がありました。AndroidのBitcoinウォレット（2013年）では、AndroidのSecureRandomがJavaレベルのシード処理を使用していましたが、一部のデバイスでそれが失敗し、ECDSA署名でkの値が重複しました。これにより秘密鍵が直接明らかになりました。Sony PS3（2010年）では、ECDSAによるファームウェア署名に定数のnonceを使用していたため、2つの署名から秘密鍵を抽出できました（異なるメッセージで同じkを使用すると、単純な代数計算によって鍵が明らかになります）。

DRBGが同じ値を繰り返し生成する、いわゆるstuck-at出力の可能性を検出するテストは、次のうちどれですか。

統計テスト（NIST SP 800-22、TestU01 BigCrush、PractRand）は出力品質を検証しますが、暗号学的安全性を証明することはできません。CAVP既知解テストは、SP 800-90A実装のアルゴリズム上の正しさを検証します。SP 800-90Bのエントロピー源テスト（最小エントロピー推定、健全性テスト）は、シード入力を検証します。Continuous RNG Test（CRNGT）は、実行時にstuck-at出力を検出します。VMおよびコンテナのデプロイメントでは、エントロピー注入（VIRTIO-RNG）と起動時のエントロピーチェックが必要です。フォーク安全性テストでは、子プロセスが親プロセスのDRBG状態を継承していないことを検証します。現実世界の障害（Debian、Android）は、RNGのバグが暗号鍵の侵害に直接つながることを示しています。監査チェックリストによって、これらのチェックを本番デプロイメント向けに体系化できます。