Internet Draft Paul Hoffman draft-hoffman-des40-03.txt Internet Mail Consortium Russ Housley SPYRUS April 30, 1999 Expires in six months DESにおける40ビット鍵の生成 このメモの位置付け このドキュメントはインターネットドラフトであり、RFC2026の第10章に記載 されているすべての条項に従う。 インターネットドラフトは、Internet Engineering Task Force(IETF)とその エリア、そしてそのワーキンググループにおいて作成中のドキュメントのこと である。その他のグループが、作成中のドキュメントをインターネットドラフト として配布することも認められている。 インターネットドラフトは最大6ヶ月間有効で、その後アップデートや置き換え をすることができる。もしくは、他のドキュメントによりいつでも無効にする ことができる。インターネットドラフトを参考文献として引用すること、もし くは "work in progress" 以上の扱いで引用するのは適切ではない。 現在のインターネットドラフトは、次のところからアクセスすることができる。 http://www.ietf.org/ietf/1id-abstracts.txt インターネットドラフトのミラーサイトのリストは、次のところからアクセス することができる。 http://www.ietf.org/shadow.html 1. はじめに このドキュメントでは、DESの鍵を56ビットから40ビットへ短くするための方法 を示す。短くされた鍵は、一般に"DES-40"として知られている。鍵を短くする 目的は、アプリケーションがより弱い暗号化アルゴリズム使用することで、いく つかの地域への輸出許可を得ることである。いくつかの企業では、すでにDESを 実装したコードを製品の中で使用しているために、他のアルゴリズムを40ビット で使用するのではなく、DESを40ビットで使用したいと考えている。このときには、 完全な強度の鍵を使用するものとして実装したDESと同一の暗号化アルゴリズム を使用して、短い鍵を使用することになる。 56ビットの鍵を40ビットに短くするための、さまざまな方法が考えられる。この ドラフトにおいて1つの方法を選択したのは、相互運用のためにはある1つの 方法を選択する必要があるためである。さらに、この方法を使用することで、 合衆国から輸出許可を得られることがすでに知られている。 2. DESにおける40ビット鍵の作成 DES [DES]では、56ビットの鍵を使用する。鍵は、8ビットを1バイトとした ときの8バイトで構成される。しかし、それぞれのバイトにおける最後（8番目） のビットはパリティ用に使用されており、残りの56ビットが鍵とされる。 8バイト、56ビットの鍵を弱めて40ビットの鍵にするには、最初のバイトから 始まる、1つおきのバイトにおいて、最初の4ビットを0にセットする。 言いかえると、次のバイナリ値と鍵との、ビットごとの論理AND演算を行う。 0000111111111111000011111111111100001111111111110000111111111111 別の見方をすると、 ビット位置 0000000000111111111122222222223333333333444444444455555555556666 0123456789012345678901234567890123456789012345678901234567890123 のとき、以下のようになる。 zzzzKKKpKKKKKKKpzzzzKKKpKKKKKKKpzzzzKKKpKKKKKKKpzzzzKKKpKKKKKKKp ここで、 z = zero ビット K = 鍵ビット p = パリティビット である。 いくつかのDESの実装では、それぞれのバイトにおけるパリティビットが正確に 設定されていることが必要とされる。これは、鍵が受理できることを確認する ためである。DESでは、それぞれのバイトの最後のビットがパリティビットであ る必要がある。DESでは、奇数パリティを使用する。すなわち、それぞれのバイ トにおける1のビットの数が奇数でなければならない。それゆえ40ビットへの変 換処理を正確に行うために、ソフトウエアでは、それぞれのバイトにおけるパ リティが奇数パリティとなるよう、必要であれば最後のビットを変更する必要が ある。 3. セキュリティに関する考察 現在のコンピュータ技術では、40ビットの鍵で暗号化された暗号文に対する ブルートフォース攻撃を、非常に高速に実行することができる。これはDESに限 らず、すべての暗号化アルゴリズムにおいて同様である。それゆえ、40ビットの 鍵へ短くするということは、復号に対するセキュリティが弱められることになる。 コンピュータがさらに高速になれば、この弱いセキュリティはさらに弱くなる。 それゆえ、もし敵が復号に成功したときに高い価値を持つようなデータに対しては、 40ビット鍵を使用してはならない。しかし、40ビットの鍵でデータを暗号化する ことにより、受動的なスヌーパーが、重要であるが煩わしい復号の努力をせずに、 すぐにメッセージを読んでしまうことを防ぐことができる。 40ビット鍵に対するブルートフォース攻撃の容易さゆえ、40ビット鍵を生成した 56ビット鍵は、56ビット鍵として使用してはならない。これは最初に40ビット鍵 を導き、そして残りの16ビットをブルートフォース攻撃により埋めるという単純 な攻撃が可能となるためである。56ビット鍵から40ビット鍵を生成するシステム では、関連する56ビット鍵は、40ビット鍵よりもほんの少ししか強度が高くない と仮定しなければならない。 短い鍵（40ビットは一般的に短いと考えられる）では、長い鍵においては不可能 な、さまざまなブルートフォース攻撃を受けることがある。それゆえ、短い鍵は さらに危険になる。例えば、40ビットアルゴリズムを使用し、攻撃者がすでに 知っているバイトブロックが含まれている文書を暗号化した場合、攻撃者は、 そのブロックに対して可能な限りの暗号化をあらかじめ行っておくことにより、 それらと暗号文との比較を高速に実行することが出来る。さらに、将来短い鍵へ の更なる攻撃法が出現すれば、短い鍵はデータを保護するのにはさらに適さない ものとなる。 このドラフトにおいて鍵を短くする方法を示したことで、作成された鍵の中での ゼロビットのパターンが明白となった。現在のところ、このゼロパターンを持つ 鍵を使用して暗号化した暗号文が、ゼロパターンの決まっていない鍵を使用して 暗号化した暗号文よりも解読が容易であるか否かを示した文献はない。しかし、 40ビット鍵はすでにそれ自体弱いため、パターン化したことによるセキュリティ の弱体化は、鍵長が短いことに基づく弱さに比べると、それほど重要ではないと 考えられる。 長い鍵を短くするための方法は他にも存在する。例えばIBMは、"Commercial Data Masking Facility" すなわちCDMF [CDMF]と呼ばれる（非常に複雑な） 方法で、特許を取得している。他にも方法は存在するであろう。これらの方法 を使用することで、ブルートフォース攻撃がより困難な（もしくはよりやさ しい）暗号文を作成する鍵を生成することができる。CDMFとDES-40との簡単な 比較によると、CDMFに対するブルートフォース攻撃では、1回分のDES処理が 余計に必要となる。しかし1回分のDES処理が必要であっても、それがさらなる 複雑さを持っているということを保証しているわけではないようである。 A. 参考文献 [CDMF] "Design of the Commercial Data Masking Facility Data Privacy Algorithm", 1st ACM Conference on Computer and Communications Security, ACM Press, 1993. [DES] ANSI X3.106, "American National Standard for Information Systems-Data Link Encryption," American National Standards Institute, 1983. B. オブジェクト識別子 一般にDES-40では、DESに関するアルゴリズム識別子が使用される。これは鍵 ビットのうち、16のビットがすでにわかっている値を持つこと以外は、全く同一 のアルゴリズムであるからである。しかし、DES-40に対して割り当てが必要な いくつかの例（例えばアルゴリズムネゴシエーションなど）が存在する。その ような場合に対し、次のアルゴリズム識別子が割り当てられている。このアルゴ リズム識別子は、処理モードには無関係であることに注意。 id-alg-des40 OBJECT IDENTIFIER ::= { iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) alg(6) 1 } C. 著者のアドレス Paul Hoffman Internet Mail Consortium 127 Segre Place Santa Cruz, CA 95060 USA phoffman@imc.org Russ Housley SPYRUS 381 Elden Street, Suite 1120 Herndon, VA 20170 USA housley@spyrus.com 日本語訳 西原 啓輔 2001年5月 訳者は、訳出した文書を利用することにより発生したいかなる損害に対しても 責任を負いません。 本文書には、技術的あるいは翻訳上の誤りがある可能性があります。技術的に 正しい知識を獲得しなければならない場合は、InterNIC/IETFから発行されて いる原文を参照してください。