暗号の危殆化と新しいアルゴリズム
先日 GnuPG 1.4.4 がリリースされました。 このバージョンではセキュリティ脆弱性の修正のほかに新しいアルゴリズムが2つ追加されています。 この記事ではこれらのアルゴリズムが追加された背景について簡単に説明したいと思います。
今回追加されたアルゴリズムは「電子署名」に関するものです。 2004年8月に発表された MD4/5 および RIPEMD 等の一方向ハッシュ関数（以降単に「ハッシュ関数」と略称します）の脆弱性に関する論文および2005年2月に発表された SHA-1 攻略の可能性に関する論文は暗号の世界に大きな波紋を呼びました。 ハッシュ関数というのは任意のデータを一定サイズのハッシュ値に「要約」するアルゴリズムで，
- ハッシュ値から元のデータを推測できない
- ひとつのハッシュ値に対し複数のデータが（実時間で）見つからない
という特徴があります。 「ひとつのハッシュ値に対し複数のデータが見つからない」といっても無限の時間をかければいつかは見つかるわけで， その見つかりやすさは（よいアルゴリズムであれば）概ねハッシュ値のサイズに依存する（ハッシュ値のサイズを n として 2 の n/2 乗分の 1 の確率）といってよいでしょう。 例えば SHA-1 のハッシュ値のサイズは160ビットなので， 確率は 2 の 80 乗分の 1， つまり 2 の 80 乗回試せばひとつは同じハッシュ値を持つデータの組を見つけることができる（これをハッシュ値の衝突（Collision）と呼びます）ということになります。 しかし件の論文によると， それよりも大きな 2 の 69 乗分の 1 の確率で衝突を起こす攻略方法があるらしいのです。 この論文の内容については現在も検証が行われていますが， 専門家の間では概ね正しいだろうと言われています。
SHA-1 は電子署名や認証アルゴリズム等に広く使われている標準アルゴリズムです。 その SHA-1 が所定の性能を発揮できないかもしれないということで， これらを使うシステムはできるだけ早く手を打たなければならなくなりました。 幸いアメリカでは2004年の時点で NIST による声明が出され， 2010年までに SHA-1 の運用を終了し SHA-2 （SHA-224, SHA-256, SHA-384, SHA-512 の総称）に移行することが決まっています。 日本でも評価機関である CRYPTREC が政府に対し SHA-256, SHA-384, SHA-512 を新たに加えるよう提言しています。 （現在の電子署名法では SHA-1 のみ規定されています。 なお SHA-1 の問題に関する詳しい経緯は「CRYPTREC Report 2005」が参考になります）
電子署名についてはもうひとつ問題があります。 署名アルゴリズムの標準のひとつである DSA の仕様により事実上 SHA-2 が使えないことです。 （NIST では DSS （電子署名標準）として RSA 署名も許容しているため，全く使えないわけではないですが）
DSA は ElGamal 署名の改良版で， 物凄く簡単に言うと以下の特徴があります。
- 512ビットから1,024ビットの鍵長
- 被署名データは160ビット固定
- 署名データ長は320ビット
しかしこれから10年後を考えると1,024ビットまでの鍵長しか扱えないのは頼りないです。 なにより被署名データが160ビット固定というのは運用上あまり便利ではありません。 DSA が SHA-2 と組み合わせて使えない理由はここにあります。 （SHA-2 のハッシュ値のサイズは224ビットから512ビット）
そこでアメリカの NIST では2006年3月の FIPS186-3 ドラフト案で DSA のアルゴリズムを変更しました。
- Draft Federal Information Processing Standard (FIPS) 186-3 - Digital Signature Standard (DSS) -- PDF
このドラフト案では DSA の鍵長を3,072ビットまで拡張しました。 各鍵長と被署名データの組み合わせは以下のとおりです。
| L | N |
|---|---|
| 1,024 | 160 |
| 2,048 | 224 |
| 2,048 | 256 |
| 3,072 | 256 |
L が鍵長で N が被署名データのサイズです。 FIPS186-3 ドラフト案ではこの組み合わせの中から選択して使うべきとしています。
ところで署名・暗号に使う鍵の長さはどの程度が適当でしょうか。 確かに長ければ長いほど安全といえますが， 長すぎる鍵はとりまわしが不便です。 この件については IPA/ISEC による 「将来の暗号技術に関する安全性要件調査」 が参考になります。 詳しい内容はそちらを読んでいただくとして， 結論としては， 今後10年のスパンで考えるなら共通鍵暗号の鍵で128ビット程度で十分なようです。 128ビットの共通鍵暗号鍵を公開鍵暗号鍵に換算するとどの程度になるかは難しいですが（先ほど紹介した調査報告書では参考値としながらもかなり大きい鍵を要求しているように読めましたが）， これについては RSA Security による 「A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths」 が参考になります。 これによると128ビットの共通鍵暗号鍵は RSA 鍵では1,620ビット（EC 鍵では256ビット）に相当するようです。 DSA も似たようなものだとすると， まぁ多めに見積もっても2,048ビットもあれば十分ということになります。 総合すると， 共通鍵暗号は AES128 以上， 公開鍵暗号は RSA/DSA なら2,048ビット以上， ハッシュ関数は SHA-2 （SHA-224, SHA-256, SHA-384, SHA-512） という標準の組み合わせでも「あと10年はもつ」ということになると思います。 もっとも暗号の危殆化は様々な条件で発生する可能性がありますので， これで安心してはダメですが。 （追記： 鍵長による安全性については「「安全な鍵長の下限」とは」も参照してください）
GnuPG 1.4.4 では FIPS186-3 ドラフト案に従って SHA-224 と新しい DSA （ここではリリースノートに従って「DSA2」と表記します）が追加されました。 また DSA 署名で SHA-2 が使えるようになりました。 早速試してみたいと思います。 まず従来の DSA 鍵を作成します（作成方法は割愛します）。 作成した公開鍵を pgpdump でダンプすると以下のような感じになります。
Old: Public Key Packet(tag 6)(418 bytes) Ver 4 - new Public key creation time - Tue Jul 04 23:10:28 東京 (標準時) 2006 Pub alg - DSA Digital Signature Algorithm(pub 17) DSA p(1024 bits) - ... DSA q(160 bits) - ... DSA g(1024 bits) - ... DSA y(1022 bits) - ... Old: User ID Packet(tag 13)(35 bytes) User ID - user1 (by DSA) <user1@exsample.com> Old: Signature Packet(tag 2)(96 bytes) Ver 4 - new Sig type - Positive certification of a User ID and Public Key packet(0x13). Pub alg - DSA Digital Signature Algorithm(pub 17) Hash alg - SHA1(hash 2) Hashed Sub: signature creation time(sub 2)(4 bytes) Time - Tue Jul 04 23:10:28 東京 (標準時) 2006 Hashed Sub: key flags(sub 27)(1 bytes) Flag - This key may be used to certify other keys Flag - This key may be used to sign data Hashed Sub: preferred symmetric algorithms(sub 11)(5 bytes) Sym alg - AES with 256-bit key(sym 9) Sym alg - AES with 192-bit key(sym 8) Sym alg - AES with 128-bit key(sym 7) Sym alg - CAST5(sym 3) Sym alg - Triple-DES(sym 2) Hashed Sub: preferred hash algorithms(sub 21)(3 bytes) Hash alg - SHA1(hash 2) Hash alg - SHA256(hash 8) Hash alg - RIPEMD160(hash 3) Hashed Sub: preferred compression algorithms(sub 22)(3 bytes) Comp alg - ZLIB <RFC1950>(comp 2) Comp alg - BZip2(comp 3) Comp alg - ZIP <RFC1951>(comp 1) Hashed Sub: features(sub 30)(1 bytes) Flag - Modification detection (packets 18 and 19) Hashed Sub: key server preferences(sub 23)(1 bytes) Flag - No-modify Sub: issuer key ID(sub 16)(8 bytes) Key ID - 0x9711CD433316266D Hash left 2 bytes - 40 d0 DSA r(158 bits) - ... DSA s(159 bits) - ... -> hash(160 bits)
「preferred hash algorithms」に SHA256 が加わっているのが分かるでしょうか。
実際に
gpg --digest-algo sha256 -sa -u user1 text.txt
などとやっても動作します。 どうやら SHA-256 で作成したハッシュ値を更に折りたたんで（？）160ビットにしているようです。
Old: Compressed Data Packet(tag 8) Comp alg - ZIP <RFC1951>(comp 1) Old: One-Pass Signature Packet(tag 4)(13 bytes) New version(3) Sig type - Signature of a binary document(0x00). Hash alg - SHA256(hash 8) Pub alg - DSA Digital Signature Algorithm(pub 17) Key ID - 0x9711CD433316266D Next packet - other than one pass signature Old: Literal Data Packet(tag 11)(2004 bytes) Format - binary Filename - text.txt File modified time - Tue Jul 04 23:12:43 東京 (標準時) 2006 Literal - ... Old: Signature Packet(tag 2)(63 bytes) Ver 3 - old Hash material(5 bytes): Sig type - Signature of a binary document(0x00). Creation time - Tue Jul 04 23:12:43 東京 (標準時) 2006 Key ID - 0x9711CD433316266D Pub alg - DSA Digital Signature Algorithm(pub 17) Hash alg - SHA256(hash 8) Hash left 2 bytes - 8d 46 DSA r(159 bits) - ... DSA s(158 bits) - ... -> hash(160 bits)
今度は DSA2 鍵を作ってみます。
DSA2 鍵を作るには --enable-dsa2 オプションをつけて起動します。
鍵長は2,048ビットにしておきましょう。
同じように pgpdump で内容をダンプしてみます。
Old: Public Key Packet(tag 6)(810 bytes) Ver 4 - new Public key creation time - Tue Jul 04 23:15:09 東京 (標準時) 2006 Pub alg - DSA Digital Signature Algorithm(pub 17) DSA p(2048 bits) - ... DSA q(224 bits) - ... DSA g(2048 bits) - ... DSA y(2047 bits) - ... Old: User ID Packet(tag 13)(36 bytes) User ID - user2 (by DSA2) <user2@exsample.com> Old: Signature Packet(tag 2)(112 bytes) Ver 4 - new Sig type - Positive certification of a User ID and Public Key packet(0x13). Pub alg - DSA Digital Signature Algorithm(pub 17) Hash alg - unknown(hash 11) Hashed Sub: signature creation time(sub 2)(4 bytes) Time - Tue Jul 04 23:15:09 東京 (標準時) 2006 Hashed Sub: key flags(sub 27)(1 bytes) Flag - This key may be used to certify other keys Flag - This key may be used to sign data Hashed Sub: preferred symmetric algorithms(sub 11)(5 bytes) Sym alg - AES with 256-bit key(sym 9) Sym alg - AES with 192-bit key(sym 8) Sym alg - AES with 128-bit key(sym 7) Sym alg - CAST5(sym 3) Sym alg - Triple-DES(sym 2) Hashed Sub: preferred hash algorithms(sub 21)(3 bytes) Hash alg - SHA1(hash 2) Hash alg - SHA256(hash 8) Hash alg - RIPEMD160(hash 3) Hashed Sub: preferred compression algorithms(sub 22)(3 bytes) Comp alg - ZLIB <RFC1950>(comp 2) Comp alg - BZip2(comp 3) Comp alg - ZIP <RFC1951>(comp 1) Hashed Sub: features(sub 30)(1 bytes) Flag - Modification detection (packets 18 and 19) Hashed Sub: key server preferences(sub 23)(1 bytes) Flag - No-modify Sub: issuer key ID(sub 16)(8 bytes) Key ID - 0x31B8A040D442790A Hash left 2 bytes - 3d 84 DSA r(222 bits) - ... DSA s(219 bits) - ... -> hash(160 bits)
鍵への自己署名のハッシュ関数が「unknown(hash 11)」となっているのは pgpdump が SHA-224 に対応していないためです。
最新の OpenPGP ドラフト案では「hash 11」は SHA-224 が割り当てられているので，
この鍵の自己署名には SHA-224 が使われていると言えます。
注意していただきたいのは DSA でも DSA2 でも情報としては同じ「pub 17」として格納されているということです。 DSA と DSA2 は内部的には別のアルゴリズムですが， データ上は区別できません（パラメータから判断することもできなくはないですが）。 おそらく FIPS186-3 ドラフト案がこれまでの DSA と新しい DSA を区別する記述になっていないからでしょうが， このまま行くと深刻な互換性の問題を抱えてしまうように思います。 新しい DSA アルゴリズムはまだドラフト段階であり， また対応するアプリケーションも他になさそうなので実装が固まるまでは業務用としては手を出さないほうがいいように思います。
参考：