鍵長をどのように選択していくか　～等価安全性と鍵長の関係：デファクトスタンダード暗号技術の大移行（5）（3/3 ページ）

» 2006年08月24日 00時00分公開

[神田雅透，NTT情報流通プラットフォーム研究所]

等価安全性とは何か

　「等価安全性（equivalent security）」とは、公開鍵暗号と共通鍵暗号といった異なる種類の暗号に対しても同一の評価尺度で安全性を表すようにした基準のことであり、米国商務省国立標準技術研究所（NIST）によって提唱されている［参考文献11］。

　具体的には、評価対象とする暗号に対して最も効率的な攻撃方法を用いたときにどの程度の計算量が解読のために必要となるか（解読計算量）で評価され、解読計算量が2^xである場合に「xビット安全性（x-bit security）」と表記される。例えば、暗号化処理2³²回相当の処理を繰り返し行えば解読できるような暗号の場合、解読計算量は2³²となり、32ビット安全性であるという。

　こうすることによって、暗号の種類に依存せずに、等価安全性が大きければ安全性が高く、逆に小さければ安全性は低いと判断される。また、等価安全性が実現可能と考えられる計算量を大幅に上回っていれば、少なくとも現在知られているような攻撃方法ではその暗号を破ることは現実的に不可能であると期待できる。

　SP 800-57「Recommendation on Key Management」では、最良の攻撃方法を想定したときの等価安全性とその安全性を実現する鍵長との対応関係を表3のように示している。これからも分かるように、鍵長は、等価安全性に影響を与えるセキュリティパラメータではあるが、等価安全性そのものを表すパラメータではないことに注意されたい。

　なお、ハッシュ関数については、どの程度の計算量で衝突を見つけることができるかで評価している。

		等価安全性に相当する鍵長
		80ビット安全性	112ビット安全性	128ビット安全性	192ビット安全性	256ビット安全性
共通鍵暗号		80	112	128	192	256
公開鍵暗号デジタル署名	素因数分解問題	1024	2048	3072	7680	15360
	離散対数問題	1024	2048	3072	7680	15360
	楕円曲線上の離散対数問題	160	224	256	384	512
ハッシュ関数		160	224	256	384	512

表3　等価安全性と鍵長の関係

　上述した共通鍵暗号の解読コンテストや素因数分解実験などで実際に解読された結果と表3に示す等価安全性の関係を照らし合わせると、現時点ではおおむね65〜70ビット安全性程度の強度のものであれば数年以内の単位で解読できると予想される。

　ちなみに、現在の世界最高速のスーパーコンピュータであるIBM「Blue Gene/L」（280TFLOPSの演算能力がある）が100万台集まり、かつ1命令で1回の解読処理（つまり1秒間に約2⁶⁸回相当の解読処理）が実行できると仮定したとしても、128ビット安全性の暗号を解読するのに約2⁶⁰秒、つまり約350億年もかかることになり、事実上解読不可能といえる程度の暗号強度があることになる。

　なお、等価安全性について注意すべき点がいくつかある。特に、以下の1点目と2点目には注意しておく必要がある。

　1点目は、アルゴリズムによっては固有的に持つ脆弱性があり、最良の攻撃方法よりも効率的な攻撃方法が新たに発見されることがある。その際の攻撃方法としては、攻撃者が平文・暗号文対を多数入手できる状況という攻撃者に有利な環境も想定するのが一般的であり、必ずしも実用上安全性の脅威が生じるというわけではない。しかし、効率的な攻撃方法が発見された暗号技術は設計時に期待された安全性が担保されていないと判断され、等価安全性が必ず下方修正されることになる。

　例えば、3-key Triple DESは鍵長が168ビットの共通鍵暗号であるが、最も効率的な攻撃法が鍵全数探索攻撃ではなく中間値一致攻撃であるため、等価安全性としては112ビット安全性相当とされている。つまり、鍵長128ビットのAESやCamelliaなどが128ビット安全性であるのに対し、3-key Triple DESは鍵長が長いにもかかわらず、それらより安全性は低いと判断される。また、SHA-1の等価安全性は、従来は80ビット安全性相当であったものが、WangらのSHA-1への攻撃成功によって69ビット安全性（いまでは61ビット安全性）へ引き下げられたことになる。

　2点目は、異なる暗号技術を組み合わせて作られたシステムの場合、システム全体としての安全性が最も弱い暗号技術の等価安全性によって決まることである。従って、利用する暗号技術の等価安全性が著しく不均衡であることは望ましいことではなく、同程度の等価安全性となるような暗号技術や鍵長を選択してシステムを構築した方がよい。

　この観点でみると、共通鍵暗号がTriple DESからAESへ切り替えるのに伴って128ビット安全性以上に安全性が強化された一方で、公開鍵暗号はおおむね80ビット安全性のものが利用され続けており、またハッシュ関数は61ビット安全性にまで引き下げられた。つまり、ここ数年で利用する暗号技術が共通鍵暗号か公開鍵暗号かハッシュ関数かによって、等価安全性が著しく不均衡になってしまったことを意味する。

　単にSHA-1をSHA-2に移行するだけでなく、80ビット安全性の公開鍵暗号も含めてデファクトスタンダード暗号技術の大移行を行うとNISTが決断した理由の1つに、この等価安全性の不均衡是正があったと推測できよう。

　3点目は、短中期的に発生する可能性としては非常に少なくほとんど無視できると考えられるものの、最良の攻撃方法として新しい攻撃方法が見つかったケース（例えば数体ふるい法よりも非常に高速な素因数分解アルゴリズムが発見された場合）や計算機能力の環境が激変したケース（例えば量子コンピュータの実用化）など、等価安全性評価の前提条件を覆すような研究成果が出た場合には、表3に示した等価安全性と鍵長の関係が大きく見直される可能性がある。

　次回は、システムの利用期間に見合ったアルゴリズムと鍵長の選択に関連し、NISTのSP800-57における話題を解説する。

【参考文献】

［1］ Biham and Shamir「Differential Cryptanalysis of DES-like Cryptosystems」 Journal of Cryptology, Vol. 4 No. 1, pp. 3-72, 1991

［2］ Matsui「Linear Cryptanalysis Method for DES Cipher」Advances in Cryptology - EUROCRYPT'93, LNCS 765, Springer, 1994

［3］ RSA Laboratories「DES Challenge III」http://www.rsasecurity.com/rsalabs/node.asp?id=2108

［4］ RSA Laboratories「The RSA Laboratories Secret-Key Challenge」 http://www.rsasecurity.com/rsalabs/node.asp?id=2103

［5］ Distrituted.net「RC5-72 / Overall Project Stats」http://stats.distributed.net/projects.php?project_id=8

［6］ RSA Laboratories「The New RSA Factoring Challenge」http://www.rsasecurity.com/rsalabs/node.asp?id=2092

［7］ Wagstaff「The Cunningham Project」http://homes.cerias.purdue.edu/~ssw/cun/

［8］ Certicom「The Certicom ECC Challenge」http://www.certicom.com/index.php?action=ecc,ecc_challenge

［9］ Lenstra and Verhaul「Selecting cryptographic key sizes: Extended Abstract」Public Key Cryptography: Third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, LNCS 1751, Springer, 2004

［10］ Brent「Recent progress and prospects for integer factorization algorithm」Computing and Combinatorics: 6th Annual International Conference, COCOON 2000, LNCS 1858, Springer, 2000

［11］ NIST「Recommendation on Key Management」NIST Special Publications 800 Series, SP 800-57, 2005http://csrc.nist.gov/publications/nistpubs/index.html