« MinGW/MSYS をインストールする | メイン | Trackback Auto Discovery を外しました »

「安全な鍵長の下限」とは

先日書いた 「暗号の危殆化と新しいアルゴリズム」 で署名・暗号に使う鍵の長さについて少しだけ言及しましたが, (私が断定的に書いてしまったのが悪いのかもしれませんが)その部分だけ注目している方もいるようです。 そこで今回は暗号鍵のサイズについてもう少し細かく見ていくことにしましょう。

暗号アルゴリズムの危殆化(compromise)要因には色々あるのですが, 大まかに以下の3つに集約できると思います。 (「将来の暗号技術に関する安全性要件調査」より引用)

  1. 暗号アルゴリズムの脆弱性(設計上の瑕疵など)
  2. 攻撃法の進歩(既存攻撃法の改良、新たな攻撃法の開発)
  3. 計算機性能の向上(解読計算能力の増大)

例えば前回紹介した SHA-1 への攻略法は上記の1番目の要因に相当します。 もし1番目および2番目の要因がないとするなら, 3番目の要因を取り除くためには鍵のビット長を大きくすればいいことに気がつきます。 鍵のビット長を大きくすればそれだけ試行回数が増えるため解読に時間がかかることになるからです。

さて, ここからは IPA/ISEC の 「将来の暗号技術に関する安全性要件調査」 を見ながら説明していきましょう。

解読に時間がかかるといっても無限の時間をかければいつかは解読できるわけで, そうなるとどれだけの時間をかければ安全といえるのかということになります。 「将来の暗号技術に関する安全性要件調査」 では「1年間の解読計算によって解読される確率が0.1%未満である」ことを以って安全としているようです。 これは言い換えると「解読計算を1000年間行っても,鍵空間が探索し尽くせない」ことを意味します。

また解読計算を行うには膨大な計算リソースが必要になります。 今後ともムーアの法則(「計算機性能は同一コストで18ヶ月で2倍になる」という法則)が成り立つとしても予算は有限ですので, 調達コストやランニングコストを考えれば計算速度にも上限が存在することになります。 この場合, 予算をどのように見積もるかが鍵になりますが, 「将来の暗号技術に関する安全性要件調査」 では以下の4つのケースを想定しています。

中規模予算:1000万ドル(約10億円)
大規模予算:100億ドル(約1兆円)
超大規模予算:経済規模最大国の GDP の4% (国防予算にほぼ匹敵)
限界規模予算:世界の年間 GDP

なお, 計算機性能の向上には物理的な限界があると考えられていますが(つまりいつかはムーアの法則は破られる), その限界点についての議論も行われているようです。 それによると, クロック速度の相対論的限界はあと10の9乗(ビット換算で30ビット)程度, 集積度の量子論的限界もあと10の9乗(ビット換算で30ビット)程度, エネルギー面からも1年間の太陽エネルギーを用いて187ビットの鍵空間を探索するのが限界だそうです。 もちろんこれは現在のコンピュータの延長として考えた場合の話で, 例えば量子コンピュータが実用化されるなど画期的な技術革新があれば崩れてしまいます。 まぁその場合にはそもそも鍵長による安全性云々という話も成り立たなくなる可能性もありますが。

このように様々な条件を考慮した上で安全な鍵長の下限はどのくらいになるのか調べていきます。 ここでは調べる対象となる暗号アルゴリズムが以下の条件を満たしていると仮定します。

  • 共通鍵暗号
  • 全数探索(総当り法)よりも効率的な解読法が存在しない
  • 有意性検定のコストは無視できることとする

これら条件を満たした上で予測される安全な鍵長の下限を以下に挙げます。 (全部は多いので一部だけ)

  2003年 2006年 2010年 2016年 2018年
対中規模予算攻撃 93 95 97100101
対大規模予算攻撃 103105107110111
対超大規模予算攻撃108110113116117
対限界規模予算攻撃114116119122123

この予測によれは, 今後10年に限れば128ビット程度の鍵長で十分ということになります。

ところで, 日本国外ではどのような評価をしているでしょうか。 軽く調べてみましたが, これが結構あります。 代表的なものを以下にいくつか挙げてみます。

特に欧州の ECRYPT (Network of Excellence in Cryptology)による年次報告は各方面の調査結果が並べられていてとても参考になります。 ここではひとつだけ NIST (National Institute of Standards and Technology) SP800-57 における評価結果を紹介したいと思います。

まず鍵の強度について共通鍵暗号と公開鍵暗号とを比較した一覧があります。

Bits of security 80 112 128 192 256
Symmetric key algorithm 2TDEA 3TDEAAES-128AES-192AES-256
FFC (e.g. DSA) L 1024 2048 3072 7680 15360
FFC (e.g. DSA) N 160 224 256 384 512
IFC (e.g. RSA) k 1024 2048 3072 7680 15360
ECC (e.g. ECDSA) f160-233224-225256-383384-511 512+

TDEA というのは TripleDES のことです。 DES はかつて共通鍵暗号の標準(FIPS PUB 46-3)でしたが, 標準の座を AES に明け渡して2005年に完全に廃止になりました。 ただし TripleDES については新たに SP800-67 を発行しその中で TDEA (Triple Data Encryption Algorithm)として規格化されています。

同じようにハッシュ関数についても一覧があります。

Bits of security80 112 128 192 256
Digital Signatures and hash-only applicationsSHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-224, SHA-256, SHA-384, SHA-512 SHA-256, SHA-384, SHA-512 SHA-384, SHA-512 SHA-512
HMACSHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-224, SHA-256, SHA-384, SHA-512SHA-256, SHA-384, SHA-512
Key Derivation FunctionsSHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-224, SHA-256, SHA-384, SHA-512SHA-256, SHA-384, SHA-512
Random Number GenerationSHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-1, SHA-224, SHA-256, SHA-384, SHA-512SHA-224, SHA-256, SHA-384, SHA-512SHA-256, SHA-384, SHA-512

ハッシュ関数の場合, 目的によって要求される強度(ここではハッシュ値のビットサイズ)が異なるためこのような表になっています。 また前回述べたように, SHA-1 は予定の性能を下回ることが指摘されていて, 2010年までに SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)に移行するようにとの声明が出されました。

これらを踏まえて実際に安全な鍵長の下限がどの程度か挙げててみます。

Algorithm security lifetimeThrough 2010
(min. of 80 bits of strength)
Through 2030
(min. of 112 bits of strength)
Beyond 2030
(min. of 128 bits of strength)
Symmetric key algorithm
(Encryption and MAC)
2TDEA, 3TDEA, AES-128, AES-192, AES-256 3TDEA, AES-128, AES-192, AES-256 AES-128, AES-192, AES-256
FFC (e.g. DSA) Lmin.: 1024 min.: 2048 min.: 3072
FFC (e.g. DSA) Nmin.: 160 min.: 224 min.: 256
IFC (e.g. RSA) kmin.: 1024 min.: 2048 min.: 3072
ECC (e.g. ECDSA) fmin.: 160 min.: 224 min.: 256

先の IPA/ISEC の評価(こちらは2018年までしかないので簡単に比べられませんが)より若干緩い感じですね。 現状では AES-128 よりも強い暗号は必要なさそうです。 共通鍵暗号に関しては他も大体同じような結果になっていますが(ECRYPT の報告は少し厳しいですが), 公開鍵暗号に関しては報告書によってばらつきが大きいため参考程度に留めておくのがいいかもしれません。 パッと見の印象では今回紹介した NIST の報告がバランスが取れていて妥当なところではないでしょうか。

以上で署名・暗号に使う鍵の長さについて大体イメージできたのではないでしょうか。 最初に述べたように暗号の危殆化には様々な要因があり, 「鍵長を大きくしたから安心」というようなものでもありません。 暗号技術を含むシステムを開発・運用している方々は常に技術の最新動向に注意しておく必要があります。 この記事が何らかの手助けになれば幸いです。

参考:

Tags: [security] [cryptgraphy] [RSA] [DSA] [ECDSA] [SHA] [TDEA]
2006-07-15T16:13:23+09:00 Spiegel (licensed) [暗号・セキュリティ] このエントリーを含むはてなブックマーク

トラックバック

現在 spam 対策のため Trackback Auto Discovery を無効にしています。 あしからずご了承ください。

トラックバック URL:

» RSA768 合成数を素因数分解 from Baldanders.info
RSA768 合成数の素因数分解に成功したらしい。 [続きを読む]

トラックバック時刻: 2010年1月 9日 13:23