Note: Yvo Desmedt は、1999 年 10 月 31 日に、この章の日本語訳を公開する許可を与えてくれた。Desmedt 氏は、自分が責任を持てるのはこの章の原文についてのみであり、本のその他の部分や、翻訳のできについては責任は持てない、と宣言している。またかれは、現在は Florida State University, Department of Computer Science 教授である。連絡先は <desmedt@nu.cs.fsu.edu>。また「本書では、この論文が Eurocrypt '87 で発表されたとなっているが、これはまちがいであり、もっと一般的な論文が別タイトルで Eurocrypt '86 で発表されている。この章はrump session で発表したかもしれないが、はっきりおぼえていない」とのこと。

9

百万 DES 鍵を破る：Yvo Desmedt 著

本章の内容：

概要
はじめに
基本的な考え方
マシンの詳細
得られた結果と考察
結論
謝辞

この論文は、Eurocrypt 1987においてYvo Desmedt と Jean-Jacques Quisquater により「An Exhaustive Key Search Machine Breaking One Million DES Keys」という題名で発表された。この会議では論文集がつくられなかったため、ここが初めての刊行となる。並行ばか力式の暗号破りにおける研究の方向性をいくつか指摘していて、いまでも有用。

概要

DES は、商用と産業用ではいちばん多く使われている暗号アルゴリズムだ。本論では、現実性のあるしらみつぶし式の鍵探索マシンを提案している。これはDESが標準の8バイトモードでプライバシー保護に使われたときに、毎時間何千もの鍵を見つけ出すものである。またDESを使った真正性保護も、セキュリティが破られることがある。

はじめに

DES は暗号の NBS* と ANSI⁺ 規格である。また、DEA1の名のもとで、ISO^#規格とする提案も行われている。最初からDiffie と Hellman は、平文がわかっていたらDES鍵はしらみつぶし鍵探索マシンによる攻撃で破れると述べていた。^§ しかしながら、その設計は、サイズや消費電力といった現実的な問題が考慮されていないために、批判を受けていた。

___________________

* "Data Encryption Standard", FIPS (National Bureau of Standards Federal Information Processing Standards Publ.), no. 46, Washington D.C., January 1977.

+ "Data Encryption Algorithm", ANSI X3.92-1981, (American National Standards Institute), New York, December 31, 1980.

# "Data Encipherment, Specification of Algorithm DEA1", ISO/DP 8227 (Draft Proposal), 1983.

§ Diffie, W., and Hellman, M.E.: "Exhaustive cryptanalysis of the NBS Data Encryption Standard", Computer, vol. 10, no. 6, pp. 74 -84, June 1977.

9-1

9-2

Hoornaert* は昨年、現実性のあるしらみつぶし式鍵探索マシンを提案し、これは現実的な問題をすべて解決している。DESを半日で破るかわりに (これはDiffie-Hellmanのマシンの案)、値段の安いバージョン（100万ドル）は鍵を見つけるのに最大4週間かかる。しかし実際には、企業や秘密機関は、複数の鍵を一度に破りたいと思うだろう。産業スパイ目的では、企業は主要な競合相手の通信を、なるべくたくさん解読したいはずだ。秘密機関は、あらゆる通信を傍受して、軍事目的に使えるような他国での産業上の発展を追いかけたいと思うだろう。上記のマシンは、この目的には非実用的か、高価すぎる。でも何千ものマシンを使って何千もの鍵を解読するかわりに、改造したマシンが一つあれば十分だ。

基本的な考え方

単純に考えると、しらみつぶし方式のマシンで100万鍵を解読したければ、平文と暗号文のペア (plaintext,ciphertext)=(Mi,Ci) が100万対必要となって、そのそれぞれのついについて一つずつ作業しなくてはならないように思える。でも、このペアのすべてが同じ平文をもっていたら、しらみつぶしマシンは、1ペアだけを解読するのと同じ労力で、その100万対すべての暗号文を解読できる。これは非常に現実的な想定である。たとえば、手紙の末尾などですべて同じパターン（例："Yours Sincerely"）が使われるのはよくあることだからだ。すべての標準⁺ 8 バイトモードでは、部分的にわかっている平文を使った攻撃だけで十分である。ECB の場合は、暗号文のみの攻撃で十分となる。いちばんよく出てくる8バイトの組み合わせは簡単に検知できて利用できる。もちろんながら、マシンを増やせばちがう平文パターンもあつかえるようになる。パターンがちがっても平文を選んで攻撃すれば数が減らせてしまう！

マシンの詳細

実際には作っていないものの、ここではそうしたマシンが実際に可能だということを示すだけの詳細が十分に記述されている。マシンは、Hoornaertのマシンで使われたDESチップにちょっと拡張をほどこしたものをもとにする。鍵を見つけたい暗号文を「望まれた」暗号文と呼ぶことにする。一台のマシンで、たとえば25000のDESチップがあるとすると、それが同じ8バイトの「平文」パターンからはじめて、ちがった鍵を使って暗号文を計算してゆく。マシンは、結果として出てきた暗号文が「望まれた」暗号文と同じかどうか確認する。もし同じなら、対応する鍵とその「望まれた」暗号文の「番号」を鍵処理マシン（Key Handling Machine, KHM) に伝える。

___________________

* Hoornaert, F., Goubert, J., and Desmedt, Y.: "Efficient hardware implementations of the DES", Advances in Cryptology, Proceedings of Crypto 84, Santa Barbara, August 1984 (Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1985), pp. 147-173.

+ DES modes of operation", FIPS (NBS Federal Information Processing Standards Publ.), no. 81, Washington D.C., December 2, 1980.

9-3

でも、使っているDESチップはそれぞれ毎秒訳100万対（暗号文と鍵）をつくりだす。これはかなり通信上の問題を引き起こす。これだけの情報すべて (約 110Mbit/秒= (56 鍵ビット + 64 暗号文ビット) x 1M DES/秒) を、すべてチップ外に伝えることはできない。この通信上の問題を避けるために、チップは内部で、「望まれた」暗号文に等しくないとはっきりわかるものを排除する。したがってチップの外界に伝えられるのは、ごく一部となる。ここでは、「望まれた」暗号分はまずあらかじめ、そのさいしょの20ビットだけに基づいてソートされる。そしてこの20ビットは、望まれた暗号文へのアドレスとして使われる。もし「望まれた」暗号文のうち、最初の20ビットが同一のものがあったら、そのうち一つだけがしらみつぶしマシンに送られて、残りは待ち行列に入れられる。しらみつぶしマシンでは、そのさいしょの20ビットを使って、望まれた暗号文のビットが後述の方法でRAMに展開される。

各拡張DESチップは、1MビットRAM4つと、リフレッシュコントローラといっしょにハイブリッド基板に載せられる（fig. 1 も見よ [提供されていない]）。番号をふられた鍵のそれぞれについて、DESチップはそれに対応して生成された暗号文のさいしょの20ビットをRAMにアドレスとして送る。RAMに保存された4ビットの情報は、望まれた暗号文のつぎの4ビットに対応している。このRAMは、改造DESチップにこの4ビットを伝える。この4ビットが、生成された暗号テキストの対応ビットに一致した場合にかぎり、生成ペア（暗号文と鍵）はDESチップの外へ出て、ローカルバスにのる（fig. 1を見よ）。したがって、平均での通信量は、まちがいなく望まれたものではない暗号文を排除することで、減る。

こうしたハイブリッドが10個ほど、小さなプリント基板に載せられる。カスタムデザインのチップが、さっきの4ビットをチェックしたのと同じ考え方で、暗号文のつぎの10ビット（25-34ビット）をチェックする。ここでは、1 MビットのRAM10個が使われて、そのアドレスはさっきと同じく、生成された暗号テキストのさいしょの20ビットだ。このチェックがうまくいった場合にかぎり、その対（暗号文と鍵）はグローバルバス経由で外界に送られる。これによって、ローカルバスとグローバルバスとの通信量は、約1000分の位1くらいにまで減る。

同じようなプリント基板が2500枚、このマシンには使われる。暗号文のさいごの30ビットが、さらにチェックされる。同じようなハードが、複数のプリント基板を制御することになる。さいごに、小さなマシンが最終チェックを行う。KHMマシンが、ほかの（平文・暗号文）ペアで鍵の正しさをチェックするか、あるいは言語の冗長性によってチェックする。たとえば一時間に一度くらい、KHMマシンは解読された鍵をアップデートして、待ち行列で待っているものをしらみつぶしマシンに送り込む（空きがあれば）。仮にハイブリッド一つが$80とすると、このマシンは$300万 (25,000 x ハイブリッド + カスタムチップ + プリント基板 + その他)くらいが現実的で妥当だろう。

9-4

得られた結果と考察

ここに記述したマシンは、4週間で約100万鍵を破る。平均では、一時間に3000鍵となる。検討ずみの鍵をアップデートすることで、もっといい結果を出すこともできる。* バッファリング、同期、MTBF、消費電力、サイズ、RAMのリロードなど現実的な問題は、著者が解決した。いくつかの状況では、最適化を行ったり、このマシンの変種をつくったりすることもできる。DESには裏口が仕掛けられているという、既存の噂があるが、このマシンが現実性を持つと言うことは、DESを破るには裏口は必要ないということを実証したことになる。むかしのRAM技術でも、同じような（あるいはもっと大規模な）マシンを設計できた。この場合は、速度は遅くなる（3.2万鍵）。この攻撃を避けるには、DESユーザはCFBの1バイトモードをきちんと使うか、新しいモードを使うか、三重DES暗号化を、ちがう鍵2つを使って利用するべきである。ここに記した攻撃に対し、もっとセキュリティが高く、使う鍵も48ビットで、DESと同じ暗号化・復号速度を持つ（固定鍵を使う場合）、DESと似たアルゴリズムも設計できる。^# DESを使って（たとえばみじかい）メッセージの認証を保護するのは、セキュリティがひくいことがある。^§ この結果と、その前の結果とを組み合わせたとき、DESで標準化されたメッセージの認証をしても、まったく無価値かもしれないということを示す。またさいごに、このマシンで使われているDESチップは、最先端VLSIを使っていないということに注意。いまではメガビット級のRAMはかんたんに手に入る。

結論

世界中の重要な企業や秘密機関なら、どこでも簡単にこのようなマシンをつくれる。そうしたマシンをこれらの組織がすでにつかっているという可能性が否定できない以上、著者は、ユーザたちに、DESの利用にあたっては慎重を期すよう忠告するものである。いちばんよく使われているモードは突破可能であるため、ユーザはハードやソフトを、そうした攻撃を避けるような形に変更しなくてはならない。また、DESで送信できるのは、機密性のひくい情報だけである。もしDESの標準化された使い方でメッセージの認証が保護されている場合には、みじかいメッセージは長くする(enlarge）必要がある。

___________________

* Desmedt, Y., "Optimizations and variants of exhaustive key search machines breaking millions of DES keys and their consequences on the security of privacy and authenticity with DES", Internal Report, ESAT Laboratory, Katholieke Universiteit Leuven, 準備中。

+ Quisquater, J.-J., Philips Research Laboratory, Brussels, 論文準備中。

# Quisquater, J.-J., Desmedt, Y., and Davio, M.: "A secure DES* scheme with < 48 bit keys", Crypto '85 rump session にて発表, Santa Barbara, August, 1985

§ Desmedt, Y.: "Unconditionally secure authentication schemes and practical and theoretical consequences", presented at Crypto '85, Santa Barbara, August, 1985, 論文集「Advances in Cryptology」 (Springer-Verlag, Berlin, 1986)に採録予定。

9-5

謝辞

著者はBelgian NFWOの出資を受けている。F. Hoornaert, IMEC-ESAT, Leuven とJ.-J. Quisquater, Philips Research Laboratory, Brussels にはさまざまな示唆や完全案をもらって著者は感謝するものである。

Y.Desmedt
ESAT Laboratory
Katholieke Universiteit Leuven
Kard. Mercierlaan 94
B-3030 Heverlee, Belgium

（現所属・連絡先は以下の通り：）
Yvo Desmedt
Professor
Department of Computer Science
PO Box 4530
206 Love Building
Florida State University
Tallahassee, FL 32306-4530 USA

本文の続きへ

YAMAGATA Hiroo<hiyori13@alum.mit.edu>