「安全な鍵長の下限」とは
先日書いた 「暗号の危殆化と新しいアルゴリズム」 で署名・暗号に使う鍵の長さについて少しだけ言及しましたが， （私が断定的に書いてしまったのが悪いのかもしれませんが）その部分だけ注目している方もいるようです。 そこで今回は暗号鍵のサイズについてもう少し細かく見ていくことにしましょう。
暗号アルゴリズムの危殆化（compromise）要因には色々あるのですが， 大まかに以下の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 | 97 | 100 | 101 |
| 対大規模予算攻撃 | 103 | 105 | 107 | 110 | 111 |
| 対超大規模予算攻撃 | 108 | 110 | 113 | 116 | 117 |
| 対限界規模予算攻撃 | 114 | 116 | 119 | 122 | 123 |
この予測によれは， 今後10年に限れば128ビット程度の鍵長で十分ということになります。
ところで， 日本国外ではどのような評価をしているでしょうか。 軽く調べてみましたが， これが結構あります。 代表的なものを以下にいくつか挙げてみます。
- ECC, Future Resiliency and High Security Systems （PDF）
- A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths
- RFC3766: Determining Strengths For Public Keys Used For Exchanging Symmetric Keys
- ECRYPT Yearly Report on Algorithms and Keysizes (2005) （PDF）
- NIST Special Publication 800-57: Recommendation for Key Management - Part 1: General (Revised) （PDF）
特に欧州の 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 | 3TDEA | AES-128 | AES-192 | AES-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) f | 160-233 | 224-225 | 256-383 | 384-511 | 512+ |
TDEA というのは TripleDES のことです。 DES はかつて共通鍵暗号の標準（FIPS PUB 46-3）でしたが， 標準の座を AES に明け渡して2005年に完全に廃止になりました。 ただし TripleDES については新たに SP800-67 を発行しその中で TDEA （Triple Data Encryption Algorithm）として規格化されています。
同じようにハッシュ関数についても一覧があります。
| Bits of security | 80 | 112 | 128 | 192 | 256 |
|---|---|---|---|---|---|
| Digital Signatures and hash-only applications | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-224, SHA-256, SHA-384, SHA-512 | SHA-256, SHA-384, SHA-512 | SHA-384, SHA-512 | SHA-512 |
| HMAC | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-224, SHA-256, SHA-384, SHA-512 | SHA-256, SHA-384, SHA-512 |
| Key Derivation Functions | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-224, SHA-256, SHA-384, SHA-512 | SHA-256, SHA-384, SHA-512 |
| Random Number Generation | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 | SHA-224, SHA-256, SHA-384, SHA-512 | SHA-256, SHA-384, SHA-512 |
ハッシュ関数の場合， 目的によって要求される強度（ここではハッシュ値のビットサイズ）が異なるためこのような表になっています。 また前回述べたように， SHA-1 は予定の性能を下回ることが指摘されていて， 2010年までに SHA-2 （SHA-224, SHA-256, SHA-384, SHA-512）に移行するようにとの声明が出されました。
これらを踏まえて実際に安全な鍵長の下限がどの程度か挙げててみます。
| Algorithm security lifetime | Through 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) L | min.: 1024 | min.: 2048 | min.: 3072 |
| FFC (e.g. DSA) N | min.: 160 | min.: 224 | min.: 256 |
| IFC (e.g. RSA) k | min.: 1024 | min.: 2048 | min.: 3072 |
| ECC (e.g. ECDSA) f | min.: 160 | min.: 224 | min.: 256 |
先の IPA/ISEC の評価（こちらは2018年までしかないので簡単に比べられませんが）より若干緩い感じですね。 現状では AES-128 よりも強い暗号は必要なさそうです。 共通鍵暗号に関しては他も大体同じような結果になっていますが（ECRYPT の報告は少し厳しいですが）， 公開鍵暗号に関しては報告書によってばらつきが大きいため参考程度に留めておくのがいいかもしれません。 パッと見の印象では今回紹介した NIST の報告がバランスが取れていて妥当なところではないでしょうか。
以上で署名・暗号に使う鍵の長さについて大体イメージできたのではないでしょうか。 最初に述べたように暗号の危殆化には様々な要因があり， 「鍵長を大きくしたから安心」というようなものでもありません。 暗号技術を含むシステムを開発・運用している方々は常に技術の最新動向に注意しておく必要があります。 この記事が何らかの手助けになれば幸いです。
参考：