Develop with pleasure!

福岡でCloudとかBlockchainとか。

Dual_EC_DRBGのバックドアの仕組み

Cryptography

japan.zdnet.com

こんなニュースもあり、バックドアと言えばエドワード・スノーデンの告発でも話題になったNSA（米国家安全保障局）のバックドアを思い出した。当時は仕組みについて調べてなかったけど、どんな仕組みのバックドアだったのか今になって気になったので調べてみた。

Dual_EC_DRBG

バックドアが仕込まれていたのは、NSAの推奨により一度は標準として採用された擬似乱数生成器のアルゴリズムDual Elliptic Curve Deterministic Random Bit Generator（Dual_EC_DRBG）。で、2006年にNIST SP800-90Aに組み込まれ、2013年に利用すべきではないと勧告されている。

Dual_EC_DRBGの仕様

Dual_EC_DRBGは、生成したシード値から、2つの楕円曲線上の点を使って、多数の乱数を生成する擬似乱数生成器で、楕円曲線上の離散対数問題の困難性がベースになっている。アルゴリズム自体はそんなに複雑ではない。

Dual_EC_DRBGでサポートされている楕円曲線は、NIST-p256およびNIST-p384とNIST-p521で、曲線の式はy² = x³ - 3x + b (mod p)。

Dual_EC_DRBGでは、楕円曲線上の２つの点PとQを使用する。この内Pは楕円曲線のジェネレーターGと同じ点で、例えばNIST-p256であればそれぞれ以下のように定義されている。

P.x = 6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
P.y = 4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5

Q.x = c97445f4 5cdef9f0 d3e05e1e 585fc297 235b82b5 be8ff3ef ca67c598 52018192
Q.y = b28ef557 ba31dfcb dd21ac46 e2a91e3c 304f44cb 87058ada 2cb81515 1e610046

そして、Dual_EC_DRBGは初期シードを使って、PとQの点を使ってスカラー倍算を実行して乱数を生成する。

エントロピーソースから初期シード ${s_0}$ を生成する。
${s_0}$ をスカラー値として ${s_0P}$ を計算し、そのx座標を ${s_1}$ とする（つまり ${s_1 = (s_0P).x}$ ）。
${s_1}$ をスカラー値として ${s_1Q}$ を計算し、そのx座標を ${r_1}$ とする（つまり ${r_0 = (s_1Q).x}$ ）。
（NIST-p256の場合） ${r_1}$ は32バイトであり、その内の上位16bitを削除した30バイトのデータが出力される。

データがさらに必要な場合、↑の計算値を使って次の乱数が生成される。次の乱数は、

${s_1}$ をスカラー値として ${s_1P}$ を計算し、そのx座標を ${s_2}$ とする（つまり ${s_2 = (s_1P).x}$ ）。
${s_2}$ をスカラー値として ${s_2Q}$ を計算し、そのx座標を ${r_2}$ とする（つまり ${r_1 = (s_2Q).x}$ ）。
${r_2}$ の下位30バイトが次の出力値。

これを要求されたビット数まで繰り返し、出力値を連結して返す（余ったバイトは破棄される）。つまり内部状態 ${s_{i-1}}$ を使って次の内部状態を ${s_i}$ を更新し、出力を生成している。

${s_i = (s_{i-1}P).x}$
${r_i = (s_iQ).x}$

このPRNGが安全であるためには、内部状態 ${s_i}$ を誰も知り得ないことが重要で、 ${s_i}$ が分かると、それ以降の全ての内部状態および出力を計算することができる。

バックドアの内容

Dual_EC_DRBGは上記のように２つの楕円曲線上の点を使って、決定論的に乱数を生成する仕組みだが、問題となるのはPとQの点の算出根拠が無い点にある。つまりNSAはPやQの離散対数を知っているのではないかということ。

攻撃者がP = dQとなるようなスカラー値を知っていて、（Public Nonceなどで）上記の ${r_1}$ を知っていると仮定した場合、攻撃者は以下の計算が行える。

${r_1}$ は楕円曲線上の点のx座標なので、楕円曲線の式を使えばy座標が計算でき点 ${R = (r_1, y)}$ を復元できる。
Rが復元できると、 ${R = s_1Q}$ である。
両辺にdをスカラー倍算すると、 ${dR = d s_1 Q = s_1P}$ が成立する。
${s_1P}$ のx座標は次の内部状態 ${s_2}$ を計算する入力値であるため、攻撃者これ以降の内部状態および出力値を知ることができる。

つまり、P = dQのスカラー値dの知識は攻撃者にとってバックドアになる。

※ ${r_1}$ は上位16 bitが削除されているので、厳密には欠落しているbitを復元するのに攻撃者は最大 ${2^{16}}$ 回の計算が必要。

↑のように、たった32バイト（正確には30バイト）の出力を入手すれば、NSAは完全な内部状態を学習できるというのがこのバックドアの怖いところ（実際に攻撃が適用できるかどうか、その難易度はこれが組み込まれているプロトコルや実装に依存する）。

参考