NIST SP 800-90A

NIST SP 800-90A (「SP」は「特別刊行物」の略) は、決定論的乱数ビット生成器を使用した乱数生成に関する勧告という題名の、米国国立標準技術研究所による刊行物です。この刊行物には、暗号学で安全であるとされる 3 つの疑似乱数生成器(ハッシュ関数に基づくHash DRBG、HMAC に基づく HMACに基づくCTR DRBG、およびカウンター モードのブロック暗号に基づくCTR DRBG ) の仕様が含まれています。以前のバージョンには、4 番目の生成器であるDual_EC_DRBG (楕円曲線暗号に基づく) が含まれていました。Dual_EC_DRBG には、後に米国国家安全保障局(NSA) によって挿入された盗聴バックドアが含まれている可能性があると報告されました。

NIST SP 800-90Aは、 2006年6月にアメリカ国立標準技術研究所によってNIST SP 800-90として、「決定論的乱数ビット生成器を使用した乱数生成に関する勧告」というタイトルで発行されました。^[1]この出版物には、暗号化に使用するための暗号的に安全であるとされる3つの疑似乱数生成器、Hash DRBG （ハッシュ関数に基づく）、HMAC DRBG（HMACに基づく）、およびCTR DRBG （カウンターモードのブロック暗号に基づく）の仕様が含まれています。

2015年6月24日現在、この出版物の現在のバージョンはリビジョン1です。以前のバージョンには、4番目のジェネレータであるDual_EC_DRBG （楕円曲線暗号に基づく）が含まれていました。Dual_EC_DRBGには、米国国家安全保障局（NSA）によって挿入された盗聴 バックドアが含まれている可能性があると後に報告されましたが、他の3つの乱数ジェネレータは、複数の暗号学者によって議論の余地がなく安全であると認められています。^{[2] [3]}

NIST SP 800-90A は米国連邦政府の著作物であるため、パブリック ドメインであり、無料で利用できます。

NIST は、4 つの (3 つに修正された) DBRG のそれぞれが「バックトラッキング耐性」と「予測耐性」を備えていると主張しています。前者は PRNG の「前方秘匿性」の一般的な概念です。つまり、状態が侵害された場合、攻撃者は過去の状態と出力を復元できません。後者は、状態が侵害され、その後十分なエントロピーで再シードされた場合、セキュリティが回復されることを意味します。^[4]

Dual_EC_DRBG のセキュリティ証明の試みでは、Dual_EC_DRBG が安全であるためには、決定的Diffie-Hellman 問題、x 対数問題、および切り捨て点問題という 3 つの問題が数学的に困難である必要があると述べられています。^[5]決定的 Diffie-Hellman 問題は困難であると広く認められています。^[5] x 対数問題は困難であると広く認められていません。この問題が難しいという証拠はいくつか示されていますが、その証拠は決定的ではありません。^[5]したがって、セキュリティ証明は疑わしく、x 対数問題が効率的に解決可能であることが示された場合、無効であることが証明されます。切り捨て点問題では、Dual_EC_DRBG によって選択された点から、真の乱数と区別がつかないように十分なビットを切り捨てる必要があります。^[5]しかし、Dual_EC_DRBG標準で規定されているデフォルトの16ビットの切り捨ては、出力を真の乱数ジェネレータと区別できないものにするには不十分であることが示されており^[6]、そのためデフォルトの切り捨て値を使用するとDual_EC_DRBGのセキュリティ証明が無効になります。

Bullrunプログラムの一環として、NSA は暗号化システムにバックドアを挿入しました。2013 年にそのターゲットの 1 つとして Dual_EC_DRBG が提案されました。^[7] NSA は標準化プロセスに携わり、最終的に標準の唯一の編集者になることでこれを達成しました。^[8] Dual_EC_DRBG を NIST SP 800-90A に受け入れてもらうにあたり、NSA は著名なセキュリティ企業RSA Securityが自社製品で Dual_EC_DRBG を使用していることを理由に挙げました。しかし、RSA Security は NSA から Dual_EC_DRBG をデフォルトとして使用するために 1,000 万ドルを支払われており、この契約はロイター通信が「純粋な技術者ではなくビジネス リーダーによって処理された」と表現しています。RSA Security に Dual_EC_DRBG を使用させるための 1,000 万ドルの契約はロイター通信によって秘密と表現されているため、NIST SP 800-90A に Dual_EC_DRBG を受け入れるプロセスに関わった人々は、この明らかな利益相反についておそらく知らされていなかったと思われます。^[9]これは、後に他の方法（バックドアに加えて）よりも劣っていることがわかった乱数ジェネレータが、どのようにしてNIST SP 800-90A標準に組み込まれたのかを説明するのに役立つかもしれない。

Dual_EC_DRBG のバックドアの可能性は、2007 年にDan ShumowとNiels Fergusonによってすでに文書化されていましたが^[10] 、 2013 年に暴露されるまで RSA Security などの企業によって実際に使用され続けました。^[2] Dual_EC_DRBG の既知の欠陥を考慮して、RSA Security が故意に NSA バックドアを自社製品に挿入したという非難がその後ありました。RSA は、自社製品に故意にバックドアを挿入したことを否定しています。^[11]

NSAのバックドア暴露を受けて、NISTはNIST SP 800-90A標準の公開審査プロセスを再開した。^{[7] [12]} Dual_EC_DRBGを削除したNIST SP 800-90Aの改訂版は2015年6月に公開された。^[13]

Hash_DRBGとHMAC_DRBGには、疑似乱数を生成するための単一の呼び出しに対するセキュリティ証明があります。^[14] Hash_DRBGとHMAC_DRBGのセキュリティを証明した論文では、前の段落で使用したDual_EC_DRBGのセキュリティ証明の試みをセキュリティ証明として引用し、CTR_DRBGはNIST SP 800-90Aでセキュリティ証明がない唯一のDRBGであるため、使用すべきではないと述べています。^[14]

HMAC_DRBGには機械検証されたセキュリティ証明もあります。^[15]機械検証されたセキュリティ証明を含む論文では、適切に実装されたHMAC_DRBGインスタンスの侵害が、侵害前に生成された数値のセキュリティを侵害しないことも証明されています。^[15]

WoodageとShumow (2019)はNISTスキームをより詳細に分析しています。具体的には、これまで全く分析されていなかった初期シード生成と再シードを考慮したセキュリティ証明を提供しています。ランダムオラクルモデルとオラクルに依存しないエントロピーソースを想定すると、次のようになります。^[4]

• Hash_DBRG は Dodis らの意味で堅牢であり、つまり NIST のセキュリティ要件の両方を満たしています。
• HMAC_DBRG は、2 つの条件が満たされていれば堅牢です。つまり、追加の入力エントロピーで呼び出される必要があり、そのエントロピーは追加の条件を満たす必要があります。NIST 承認のエントロピー ソースはすべて、これらの「追加の条件」を満たしています。
• HMAC_DBRG は、追加入力なしで呼び出された場合、前方安全性が確保されません。

CTR_DRBG は、特定のパラメータで使用すると理論的な欠陥があることがわかっています。これは、暗号学者がこの疑似乱数ジェネレータを設計する際に暗号のブロック サイズを考慮しなかったためです。 [ ^{16 ]} AESを基礎ブロック暗号として使用し、この疑似乱数ジェネレータから 112 ビットを取得すると、 CTR_DRBG は安全で真の乱数ソースと区別がつかないように見えます。^{[16] AES を基礎ブロック暗号として使用し、各インスタンスから 128 ビットを取得すると、必要なセキュリティ レベルが実現されますが、カウンター モードでの 128 ビット暗号の出力は真の乱数ジェネレータと区別できるという注意点があります。 [16]} AES を基礎ブロック暗号として使用し、この疑似乱数ジェネレータから 128 ビット以上を取得すると、結果として得られるセキュリティ レベルはキー サイズではなくブロック サイズによって制限されるため、実際のセキュリティ レベルはキー サイズによって示されるセキュリティ レベルよりもはるかに低くなります。^{[16] CTR_DRBGは、64ビットのブロックサイズが}トリプルDESで使用される112ビットのキーサイズよりもはるかに小さいため、トリプルDESが使用されるたびに期待されるセキュリティレベルを実現できないことも示されています。^[16]

現在、AES が使用されている場合にこの問題を悪用する方法は知られていません。

NIST CTR_DRBG 方式では、要求されたランダム性が出力された後、キーを置き換えるために追加のランダム性を生成することでキーを消去します。これはパフォーマンスの観点からは無駄ですが、前方秘匿性の問題を直ちに引き起こすことはありません。ただし、パフォーマンスへの影響を認識した NIST は、ポスト量子暗号プロジェクトへの提出物として「拡張 AES-CTR-DRBG インターフェイス」を推奨しています。このインターフェイスでは、消去を介在させることなく複数のランダム性セットを生成でき、ユーザーが明示的に要求の終了を通知したときにのみ消去されます。その結果、「拡張インターフェイス」が誤用された場合、キーが長時間メモリ内に残る可能性があります。Bernstein が提案した代替案は、 「高速キー消去」RNG で行われるように、要求されたランダム性が出力される前にキーを置き換えるためにランダム性を生成することです。^[17]

Campagna（2006）が報告したセキュリティ境界は、鍵交換手順を考慮していません。^[17]

nextWoodageとShumow（2019）は、Bernsteinが言及した状況、すなわち再キー化（）の間に生成される大量のランダム性（）を前提とした状態漏洩のドラフト分析を提供しているfinal。^[4]

• Barker, Elaine、Kelsey, John (2006 年 6 月)。「NIST 特別刊行物 800-90: 決定論的乱数ビット生成器を使用した乱数生成に関する推奨事項」(PDF)。米国国立標準技術研究所。2016年11 月 27 日に閲覧。2007年3月に撤回されました。
• Barker, Elaine、Kelsey, John (2007 年 3 月)。「NIST 特別刊行物 800-90: 決定論的乱数ビット生成器を使用した乱数生成に関する推奨事項 (改訂版)」(PDF)。米国国立標準技術研究所。2016年11 月 27 日閲覧。2012年1月に撤回されました。
• Barker, Elaine、Kelsey, John (2012 年 1 月)。「NIST 特別刊行物 800-90A: 決定論的ランダム ビット ジェネレータを使用した乱数生成に関する推奨事項」(PDF)。米国国立標準技術研究所。doi :10.6028/NIST.SP.800-90A。2016年11 月 19 日に閲覧。2015年6月に撤回されました。
• Barker, Elaine、Kelsey, John (2015 年 6 月)。「NIST が特別刊行物 (SP) 800-90A 改訂 1: 決定論的ランダム ビット ジェネレータを使用した乱数生成に関する推奨事項を発表」(PDF)。米国国立標準技術研究所。doi : 10.6028/NIST.SP.800-90Ar1。2016年11 月 19 日に閲覧。

• NIST SP 800-90B