神奈川大学理学部情報科学科 2014 年度学士論文要旨 指導教員：松尾和人 Dual EC DRBG の安全性検証 鈴木 涼平 1 はじめに 使用する必要があるが、本研究ではその中で “Curve P- 安全な暗号技術において、乱数は必要不可欠である。乱 数を生成する方法の一つに DRBG（Deterministic Ran- dom Bit Generator）が存在する。DRBG とは、ランダ ムビットを出力する生成器である。一般にこのようなメ カニズムは、「疑似乱数生成器 (Pseudo-Random Num- ber Generator)」と呼ばれている。この DRBG の中で、 本研究では NIST SP800-90 [2] で規定された Dual EC DRBG を取り上げる。Dual EC DRBG は、 「位数 n の楕 円曲線上の点 P , 点 Q を考えると、Q = d ∗ P のような式 から d を求めるのは難しい」という、よく知られる「楕 円曲線上の離散対数問題」に基づいている。ここで d ∗ P は点 P を d 倍することを意味する。Dual EC DRBG は、 楕円曲線 E 上の２つの有理点と初期シードと呼ばれる初 期値を用いて疑似乱数を導出する。この Dual EC DRBG において、設計者が d を知っている場合、乱数列を推定 する攻撃が可能であることが Shumow と Ferguson [1] に よって指摘されている。Shumow と Ferguson によって 指摘されている攻撃は、Dual EC DRBG により生成さ 256”を利用する。以下では Dual EC DRBG の動作を説 明する。 初期シードを t とする。まず有理点 P を t 倍し、その 乗算の結果から x 座標を取り出す（(x(t∗P ))）。次にこの 有限体の元である x 座標を整数に直す（(φ(x(t ∗ P )))）。 そして整数に直した値を別の変数 s とする。次に有理 点 Q を s 倍する。先ほどと同様に、x 座標を取り出し （(x(s ∗ Q))）、整数に直す（(φ(x(s ∗ Q)))）。この値を変 数 r とする。また、有理点 P を s 倍した結果から、x 座 標を取り出し整数に直した値（(φ(x(s ∗ P )))）を t とす る。この t は次の疑似乱数を生成するための新たなシー ドとなる。先ほど求めた r の一番右から outlen ビット 個を取り出す処理をする。outlen とは、ビットをいくつ か削り最終的に出力される疑似乱数のビット数である。 この outlen の最大値は、パフォーマンス上の理由により 240 となっている。つまり削るビット数は最低 16 ビット となる。取り出した値を疑似乱数として出力する。この 一連の流れを図 1 に記す。 れた疑似乱数の１つを使い、この疑似乱数を導出するの に使用したシードの次のシードを求める。これにより使 用した疑似乱数以降の疑似乱数が一致することを示す。 そこで本研究では２つの有理点の間の離散対数問題が分 かっている場合、安全性を検証するために実際に攻撃実 験をおこなう。本研究では、この Dual EC DRBG を用 い実際に疑似乱数を生成する。その疑似乱数を使い実際 図 1: Dual EC DRBG [2] に Shumow と Ferguson が指摘した攻撃方法による実験 をおこない、Dual EC DRBG を用いた暗号技術の安全 性を検証する。 2 3 Dual EC DRBG 本節では、Shumow と Ferguson [1] の攻撃方法を説明 まず Dual EC DRBG で利用する有限体 Fp 上の楕円 曲線 E を定義する。 3 する。Shumow と Ferguson の攻撃は導出した疑似乱数 のうち１つを使用して攻撃を行なう。その際 P = e ∗ Q を満足する e をあらかじめ知っているものとする。 E : y = x + ax + b (a, b ∈ Fp , 4a + 27b ̸= 0) 2 Shomow と Ferguson の攻撃方法 3 2 有理点とは楕円曲線 E 上の点のうち、x, y 座標が有限体 Fp の要素であるような点 (x, y) である。また、無限遠点 と呼ばれる点 Ｏ も有理点として扱う。この無限遠点は (x, y) と表記することが出来ない唯一の点である。 Dual EC DRBG で使用する楕円曲線 E, 点 P, Q はあ らかじめ NIST SP800-90 [2] により定められたものを Dual EC DRBG により導出した複数の疑似乱数のう ち１つを選び攻撃を実行する。まず、使用する疑似乱数 のビットを削る前の値すなわち r を求める必要がある。 しかし、削った部分は攻撃者にはわからない。そこで 0 から 2256−outlen − 1 の全パターンを疑似乱数と結びつけ る。結びつけた値はそのまま x = (x(s ∗ Q)) となるため、 この値を楕円曲線の定義式（z ≡ x3 + ax + b (mod p)） へ代入する。代入した結果の平方根、すなわち楕円曲線 神奈川大学理学部情報科学科 2014 年度学士論文要旨 指導教員：松尾和人 の定義式における y が存在すれば、点 A = (x, y) は曲線 上の点ということになる。存在するかは、z p−1 2 == 1 の 256−outlen 真偽のよって判別する。点 A の候補は約 2 −1 個存在する。この x は図 1 における r となる。ここで、 x = r より、A = s ∗ Q であり、φ(x(e ∗ A)) は P = e ∗ Q から次のように変形が出来る。 outlen 攻撃 探索 合計 240 4328.87 1586.25 5915.12 239 8682.26 3206.82 11889.08 238 17583.97 6778.26 24362.23 237 36672.01 13828.50 50500.51 236 71387.03 27314.89 98701.92 φ(x(e ∗ A)) = φ(x(e ∗ s ∗ Q)) = φ(x(s ∗ P )) = t 表 1: 攻撃・探索の実行時間（秒） つまり、点 A を e 倍し、その x 座標を取り出した値が そのまま t、すなわち新たなシードとなる。この新たな シードは点 A の候補の数だけ存在する。 次に導出した複数の新たなシードを使用して Dual EC DRBG を再び動作させ、導出した疑似乱数が、攻撃に使 用した疑似乱数の次の疑似乱数と一致するものを探す。 一致した場合、そのシードを出力する。この動作は、す べてのシードに対しておこない複数の候補を 1 通りに絞 る。ただし 1 度で候補を 1 通りに絞ることができるとは 限らない。その場合は、出力された値を新たなシードと してもう一度 Dual EC DRBG を動作させる必要がある。 この時、比較する対象は、攻撃に使用した疑似乱数の次々 の疑似乱数となる。最終的に 1 通りになった時点で攻撃 は終了となる。 時間は 1 ビットにつき 2 倍になる。時間が 2 倍かかる理 由は、攻撃アルゴリズムにおいて、0 から 2256−outlen − 1 を総当たりさせているため、総当たりさせる数が 2 倍に なるからである。outlen が 240 である場合から推測する と、outlen が 128 の場合、動作を終了する時間は 1030 年 となる。安全性を確保するには、攻撃終了時間が最低で も約 50 年にする必要がある。攻撃時間が約 50 年かかる ようにするには outlen を 222 にする必要がある。 5 まとめ 本稿では、疑似乱数生成器の一つである Dual EC DRBG の安全性の検証をおこなった。この Dual EC DRBG は 楕円曲線上の有理点のうち２点と初期シードを使用して 攻撃実験 4 Shomow と Ferguson の攻撃の実験を行なった。本実 験では、Dual EC DRBG によって出力する疑似乱数の 数は 10 個としている。また初期シードは 2250 とする。 攻撃で使用する疑似乱数は、出力した疑似乱数のうち一 番最初に出力されたものを使用する。使用する楕円曲線 E 、定数、点 P は、NIST SP800-90 により定められた ものを利用する。点 Q は自分で選択する必要がある。こ こでは Q = d ∗ P 、d = 6 とした。本研究では outlen を 240 から 236 の５通りで実験を行なった。 使用マシンは Core i7-4820K 3.7GHz、使用 OS は Linux 2.6、使用ソフトは Sage Version 5.6 である。 4.1 実行結果 攻撃から探索までの動作を行なった時間を表 1 に示す。 outlen は出力ビット数であり、時間は秒単位である。 探索により出力された値は、outlen が 240 から 236 全て の場合において一致した。 4.2 結果からわかること 探索をした結果を Dual EC DRBG の初期シードとし て動かすと出力結果は、攻撃するために使用した疑似乱 数以降と一致する。outlen が 240 では、Dual EC DRBG はこの攻撃方法によってわずか約 6000 秒で解けてしまう ことがわかった。しかし outlen の値を減らすことで実行 疑似乱数を生成するものである。この疑似乱数のうち 1 つを使用して Shumow と Ferguson [1] の攻撃方法を基に し攻撃実験をおこなった。outlen が 240 の場合では、わ ずか約 6000 秒で攻撃されてしまうことがわかった。従 来の形では安全性はないと考える。解決策として outlen を 1 ビットを減らすと、1 ビットあたり攻撃時間は約 2 倍ずつ増えていく。安全性を確保するには攻撃時間が最 低約 50 年かかる必要があるため、この Dual EC DRBG を使う場合、outlen を 222 にすることで安全性が確保で きると考える。 参考文献 [1] Dan Shumow, Niels Ferguson ,“On the Possibilirity of a Back Door in the NIST SP800-90 Dual EC Prng,”, Crypto 2007 rump session Slide15-shumow [2] Elaine Barker and John Kelsey,“NIST Special Publication 800-90A”, PP.60∼71, P.77 [3] Daniel J. Bernstein, Tanja Lange, Niederhagen ,“Dual EC DRBG”, Rubenhttps: //projectbullrun.org/dual-ec/ [4] 伊豆哲也 ,“楕円曲線暗号入門”, 立教大学理学部数学 科講「計算機緒論２」講義補助資料, 2006.8
© Copyright 2024 ExpyDoc
