Dual EC DRBGバックドア事件

Dual Elliptic Curve Deterministic Random Bit Generator（Dual EC DRBG）は、NISTがSP 800-90A（2006年）で標準化した4つのDRBGの1つでした。2つの楕円曲線上の点PとQを使用して疑似乱数ビットを生成します。各ステップでr_i = x(s_i * P)（点の乗算のx座標）を計算し、続いてs_{i+1} = x(r_i * P)で状態を更新し、output = x(r_i * Q)でビットを生成します。この生成器は、学術的な表記法では正当なものに見えました。NIST SP 800-90Aに収録され、その後RSA Securityが自社のBSAFE暗号ライブラリのデフォルトとして推奨したことで、企業や政府のソフトウェアに広まりました。

Dual EC DRBGのバックドアは、PとQの関係を悪用します。攻撃者が、Q = e * Pを満たす秘密のスカラーeを知っている場合、任意の出力ブロックから次を計算できます。output = x(r * Q)からr*Qのy座標を総当たりで求め、次にr*P = (1/e) * (r*Q) mod nを計算します。r*Pから、すべての将来の出力を予測し、内部状態を復元できます。eを知っていることがバックドアです。これはPに関するQの離散対数と等価です。NIST標準は、PとQの値がどのように選ばれたかを説明しなかったため、トラップドアなしにランダム生成されたことを検証できませんでした。

2007年8月、Dan Shumow と Niels Ferguson は、CRYPTOのRump Sessionで「On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng」と題した画期的な論文を発表しました。2人は、誰かが e（Pに関するQのECDLP）を知っていれば、約32バイトの出力からDual EC DRBGのすべての出力を予測できることを形式的に示しました。これを簡単な例で実証しています。この発表は暗号学コミュニティで広く注目されました。Bruce Schneierは、「NSAがDual_EC_DRBGの出力を読み取れるかどうかを知る術はない」と書いています。この警告にもかかわらず、Dual EC DRBGはその後6年間、標準に残り続けました。

2013年9月、The New York Times、The Guardian、ProPublicaは、Edward Snowdenが漏洩させた文書に基づく報道を発表し、NSAが暗号標準に秘密裏に脆弱性を仕込んでいたことを明らかにしました。「Sigint Enabling Project」と題された文書の1つには、暗号標準や製品に「covertly influence（秘密裏に影響を与える）」ための年間2億5,000万ドル規模のプログラムが記載されていました。この文書はDual EC DRBGを明示的には名指ししていませんでしたが、ShumowとFergusonによる数学的な実証と合わせて、暗号学コミュニティでは、NSAが既知の関係 e を持つようにPとQを選び、eを秘密にしたままその定数をNISTに提出することでバックドアを仕込んだと広く結論づけられました。

Reutersは2013年12月、NSAがRSA Securityに1,000万ドルを支払い、RSAのBSAFE暗号ツールキットでDual EC DRBGをデフォルトにさせたと報じました。当時EMCの一部門だったRSA Securityは、金融機関、医療企業、政府請負業者が使用するエンタープライズソフトウェアにBSAFEを組み込んで提供していました。RSAの声明は、バックドアを認識したうえで実装したことを否定しましたが、契約を受け入れたことは認めました。この暴露は特に大きな打撃となりました。BSAFEはセキュリティ製品として販売され、顧客は暗号による保証を求めて明確な意図を持って選択していたためです。この事件によりRSA Securityの評判は大きく損なわれ、2014年にはRSA Conferenceのボイコットにつながりました。

スノーデンによる暴露を受けて、NISTはいくつかの措置を講じました。2013年9月、NISTはSP 800-90Aを再び公開コメントの対象とし、審査が続いている間はDual EC DRBGを使用しないよう推奨しました。2014年4月、NISTはSP 800-90A Revision 1を公開し、Dual EC DRBGを完全に削除しました。残ったのはHash_DRBG、HMAC_DRBG、CTR_DRBGだけです。NISTはまた、すべての暗号標準とガイドラインの見直しを開始し、NSAの影響によって他の標準も損なわれていないかを具体的に検証しました。今後の標準化の取り組みにおける透明性と一般からの参加を高めるため、NIST Cryptographic Standards and Guidelines Processのワーキンググループも設置されました。

Dual EC DRBGのバックドアは、標準化団体に対する暗号学コミュニティの信頼に深刻な影響を与えました。この事件は、国家情報機関が世界中で使われる暗号標準を意図的に弱体化させる意思を持ち得ることを示しました。その影響を受けるのは敵対国だけでなく、同盟国、企業、一般市民でもあります。この事件をきっかけに、出所に不自然な作為がないことを示す数値を用いた、オープンで監査可能なアルゴリズムの採用が加速しました。SHA-3のKeccakは定数に使用したアルゴリズムを文書化し、BLAKE2とBLAKE3は数学定数の小数部分から定数を導出し、Curve25519は監査可能であることを意図して素数（2^255 - 19）を選んでいます。楕円曲線パラメータを「検証可能なランダム性」に基づいて生成することが標準的な実践になりました。

Dual EC DRBGのスキャンダルによって、「nothing-up-my-sleeve（NUMS）」定数という概念が広く知られるようになりました。これは、隠れたトラップドアを含められない、公開かつ検証可能な情報源から生成された暗号パラメータです。例として、SHA-2は最初の8個の素数の平方根から導出した初期ハッシュ値を使用し、ラウンド定数には最初の64個の素数の立方根を使用します。BLAKE2は、円周率やその他の数学定数の小数展開から定数を導出します。Ed25519は素数2^255 - 19と、他の任意の点に対する離散対数が証明可能な形で未知となる基点（文字列のハッシュとして選ばれています）を使用します。これらの方法により、定数が秘密の知識に基づいて選ばれたものではないことを誰でも検証できます。

2015年12月、Juniper Networksは、ScreenOS（同社のファイアウォールOS）に不正なコードが2012年から存在していたことを公表しました。調査により、2つのバックドアが明らかになりました。1つはDual EC DRBGのQ定数を攻撃者が制御する値に置き換えるもので、対応する e を知る攻撃者がVPNトラフィックを復号できるようにしていました。もう1つはSSH管理者パスワードに仕込まれたバックドアでした。Dual ECのQの置き換えは特に巧妙でした。Juniperはすでに標準とは異なるQの値を使用していたため、攻撃者はそれを自分のQに置き換え、Dual ECのトラップドア構造を二重に悪用したのです。この事件は、NISTのP/Qの値から逸脱した実装であっても、独自のQを配置した者なら誰でも攻撃できることを示しました。

Dual EC DRBGの事件からは、いくつかの教訓が得られます。(1) 透明性：暗号パラメータには検証可能な出所が必要であり、導出方法が文書化されていない定数は疑うべきです。(2) アルゴリズム設計：トラップドアを隠せる構造をアルゴリズムに持たせるべきではありません（Dual ECのQ/P関係には、より単純なDRBG設計を上回るセキュリティ上の利点がありません）。(3) 利益相反：標準化団体は、情報機関との利益相反を厳格に管理する必要があります。(4) コミュニティによるレビュー：学術暗号研究者が、標準の公開後ではなく公開前に懸念を提起できるようにすべきです。(5) 導入後の警戒：組織は、暗号ライブラリが使用するDRBGを監査し、推奨されない選択肢を事前に削除すべきです。

Dual ECが削除された後、推奨されるDRBGはHash_DRBG、HMAC_DRBG、CTR_DRBGを中心に整理されました。オープンソースコミュニティでは、NIST標準が信頼されていない状況に備えて、NIST以外のDRBGも採用されています。ChaCha20ベースのRNG（5.17以降のLinuxカーネル、OpenBSD、libsodiumで使用）は、ChaCha20がトラップドア構造を持たない単純なストリーム暗号であるため、バックドア耐性があると広く考えられています。Fortuna（FreeBSDおよび古いmacOSで使用）はSP 800-90Aより前に開発されたもので、現在も信頼されています。Dual ECの事件は、エントロピー源としてのハードウェアRNG（RDRAND）への関心も再び高めました。ただしRDRANDについても、バックドアが仕込まれている可能性を指摘する声があり、単独で使用するのではなく、RDRANDをソフトウェアのエントロピーと混合することが推奨されるようになりました。

Dual EC DRBGのバックドアを可能にする数学的関係は何ですか。

Dual EC DRBGは、2006年にNIST SP 800-90Aで標準化されました。ShumowとFergusonは2007年、e（Q=e*P）が分かれば32バイトの出力からすべての出力を予測できることを示しました。2013年のスノーデンのリークにより、NSAが暗号標準に影響を与えていたことが確認されました。RSA Securityは、BSAFEでDual ECをデフォルトにするために、1,000万ドルを受け取ったと報じられています。NISTはSP 800-90A Revision 1（2014年）でDual ECを削除しました。2015年のJuniper事件は、実際の製品でトラップドアが悪用されたことを示しました。教訓は、NUMS定数、透明性のある導出、利益相反の管理、標準化後の監査プロセスの重要性です。ChaCha20ベースのRNGは、信頼できる代替手段として登場しました。