このプロジェクトの背景については以下をみること。 http://www.eff.org/descracker/. この仕事についてはEFFに感謝する。また、スキャンした原文はhttp://cryptome.org/cracking-des.htmを参照のこと。翻訳にあたっては、このスキャン版をもとにしているけれど、おかしな部分については紙版も適時参照している。

プロジェクト杉田玄白　正式参加作品。詳細は https://genpaku.org/ を参照のこと。このworkは、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。

DESのクラック：暗号研究と盗聴政策、チップ設計の秘密

Electronic Frontier Foundation
翻訳：山形浩生

明記してある例外的な部分をのぞき、この本とその内容はパブリック・ドメインにある。原著は1998年に Electronic Frontier Foundationによって刊行された。一切の権利を留保しない。以下に記した例外を除いて、この本のあらゆる部分は、いかなる形態または手段によっても、発行者および訳者のいずれの許可も得ることなく複製が認められる。この文書の原著はパブリックドメインにあり、さらに訳者は一切の権利を放棄しているため、本文書の複製、使用、複写、変更、配布は、いかなる目的のためであれ、一切の許可を得ることなく、また料金などの支払いをすることなく認められる。

第四章のテストファイル、ブートストラップ、ブートストラップ2の掲載物の著作権保有者は、©1997 by Network Associates, Inc. である。この掲載物は、全体、部分を問わず、使用料の支払いなしに複製が認められる。第10章「暗号分析ハードウェアのアーキテクチャ上の考察」は、著者Ian GoldbergとDavid Wagnerが著作権 © 1996 を保有する。著者たちとは iang@cs.berkeley.edu と daw@cs.berkeley.eduで連絡がとれる。第11章「効率のよいDES鍵の探索：アップデート」の著作権保有者は、Entrust Technologies © 1997 である。これは、全体、部分を問わず、使用料の支払いなしに複製が認められる。第 9 章「100 万のDES 鍵を破る」は© 1986 である。作業はベルギー王国の University of Leuven でおこなわれ、ベルギー王国の NFWO の支援の元で実施された。この部分は著者の許可なく複製を行ってはならない。著者とはdesmedt@cs.uwm.eduで連絡がとれる。

原著発売は、O'Reilly & Associates, Inc., 101 Morris Street, Sebastopol, CA 95472 USA である。

日本語版の著作権保持者は ©1999 山形浩生<hiyori13@alum.mit.edu>である。この翻訳は、全体、部分を問わず、使用料の支払いなしに複製が認められる。

Printing History:

May 1998: 初版

製造業者や販売業者が自分の製品を区別するために使っている名称・呼称の多くは、商標として登録されている。こうした商標が本書に登場し、それが商標であると出版者が認識していた場合には、その名称はすべて大文字か、あるいは頭文字を大文字化して表記してある。

本書の制作にあたっては多大な注意がはらわれてはいるものの、出版者も配布者も、まちがいや欠落については責任をいっさいおわず、さらにここに含まれた情報の利用から生じた損害についてもいっさい責任をおわない。

v

目次

序文 ........................................ix

はじめに .......................................xiii

1: 概論.....................................1-1

解読の政治性.................................1-1
ねらい ......................................1-7
DES クラッキングの歴史 ......................1-8
EFF の DES クラッカープロジェクト ...........1-8
アーキテクチャ ..............................1-9
ほかにはだれが DES をクラックしているだろう? ..1-16
DES を使っていたらどうすればいいの？ .........1-17
結論 ........................................1-18

2: DES 鍵探索アレイのデザイン ..................2-1

チップのレジスタ ............................2-1
コマンド ....................................2-4
探索ユニットのはたらき ......................2-4
見本プログラムの説明 ........................2-5
スケーラビリティと性能 ......................2-9
ホストコンピュータのソフト ..................2-9
用語集 .....................................2-10

vi

3. DES 鍵探索アレイの設計：チップレベルの仕様 ..3-1

ASIC の説明 ..............................................3-1
基板の説明 ...............................................3-3
リード／ライトのタイミング ...............................3-5
アドレス指定用レジスタ ...................................3-7
All-active 信号 ..........................................3-7
ASIC レジスタ割り当て ....................................3-8

4: ソースコードのスキャン ..................................4-1

暗号ソースコードの政治性 ..................................4-1
紙の出版物は例外 ..........................................4-2
スキャン ..................................................4-4
ブートストラップ ..........................................4-5

[以下の5, 6, 7 章のソースコードそのものは以下にある： ftp://ftp.nic.surfnet.nl/surfnet/net-security/encryption/cracking_DES/]

5: ソフトウェアのソースコード ......................................5-1

6: チップのソースコード ..........................................6-1

7: チップシミュレータのソースコード ................................7-1

8: ハードウェア：基板の回路 ....................................8-1

基板回路 ......................................................8-1
Sun-4/470 バックプレーンの改造................................8-10
PC インターフェース .......................................................8-12
正誤表 ...............................................8-13

9: 百万DES鍵を破る：Yvo Desmedt著 .........9-1

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

vii

10: 暗号解析ハードウェアのアーキテクチャ考察 .. 10-1

Abstract ............................10-1
Introduction ........................10-1
Motivation ..........................10-2
Related work ........................10-4
Technical Approach ..................10-6
Design and Analysis .................10-8
Future work .........................10-23
Conclusions .........................10-23
Acknowledgements ....................10-24
Availability ........................10-24
References ..........................10-24

11: 効率のよいDES鍵の探索：アップデート：Michael J. Wiener 著 11-1

技術の進歩 ..........................11-2
プログラマブル・ハードウェア ........11-3
結論 ............................................................................11-4

12: 著者紹介 ......................................................................12-1

The Electronic Frontier Foundation ....................12-1
John Gilmore ..........................................12-2
Cryptography Research .................................12-2
Paul Kocher ...........................................12-3
Advanced Wireless Technologies ........................12-3

pp. ix-xii

序文
Whitfield Diffie

　1974 年にスタンフォードの計算機科学の連中は、Loui's で食事をした。 [1] 秋のある晩にわたしが食事をしていると、Butler Lampson がやってきて、最近なにをやっているときく中で、IBM の Lucifer システムが全国標準規格になるよ、と話してくれた。わたしはそれを知らなかったので、思案をはじめた。

考えはこんな具合にすすんだ。

NSA は、メッセージが読めなくなるといやだから、強い暗号システムを全国標準規格にしたくないんだな。

一方で、もし NSA が弱い暗号システムを推薦して、それがばれたら、ぼこぼこにされることになる。

Butler が正しいらしいということで、わたしはこの問題についてその後数ヶ月にわたっていろいろ考えることになった。そこから落とし穴式の暗号システムについて考えて、そして最終的には公開鍵暗号方式のことを考えるようになった。

データ暗号化規格（DES）の案が 1975 年 3 月 17 日にリリースされて[2],、わたしはかれらのやったことが見えたと思った。基本的なシステムはOKだったけれど、でもキー空間は小さめだ。キーをさがすのはむずかしいけれど、不可能ではない。最初の見積もりでは、6.5 億ドルあれば、DES を一週間で破る機械をつくれると思った。この考えをMarty Hellmanと話し合うと、かれは夢中になってこの計算にとりくんだ。話が終わるまでに、見積もりは 2,000 万ドル、時間は一日まで下がった。 [3]

われわれの論文を発端にして、暗号コミュニティではゲームがはじまって、それ以来、DES 鍵を探す論文がたくさん書かれるようになった。われわれの論文発表から 3 年くらいして、Robert Jueneman（当時はバージニア州マクリーンの Satellite Business Systems に所属）が「The Data Encryption Standard vs. Exhaustive Search」という論文を書いた。 [4] この力作は、DES を破る見通しについて、われわれよりもずっと楽観的だった。この論文の予言では、1985 年までに 50 万ドルの投資で、一時間で DES 鍵を見つけられるようになるし、1995 年までには 1,000 万ドルの投資で、それが 2 秒にまで短縮されるとなっているが、これは 15 年後に実際にできたものを、実に見事に予言している。

10年たって、Yvo DesmedtとJean-Jaques Quisquaterが貢献を 2 つ行ってくれた。一つは冗談交じりで、ひとつは真剣だ。これは関連した「誕生日問題」みたいなアプローチを使ったもので、多数の暗号問題を同時にとけるようなマシンが提案されている。[5] 冗談交じりの提案のほうは、中国の人口が DES 鍵空間の平方根と同じくらいだ、という事実を利用したものだ。

1993年は、注目すべき年だった。Michael Wiener （Bell-Northern Research）が、最高にしっかりした紙上のマシンを設計したのである。[6] ノーザンテレコムの　DMS100　電話交換機を　DES　攻撃用に特化したもの、といえばあたらずといえども遠からずだろう。この論文が特筆すべきなのは、これがチップから基板からキャビネットまで、すべてノーザンテレコムの標準設計技法を使ったということだ。3 時間で鍵を発見するマシンが、100　万ドル以下でできると予想している。非常に挑発的な付記として、この程度の予算なら　Bell-Northern Research 社の部長決裁に入れてしまえる、という点があげられている。

最後に 1996 年になると、暗号学者一人や二人ではなく、暗号学者グループによって推定が発表されている。かれらは後に（多少の嫌みもこめて）the magnificent seven [7] と呼ばれている。この推定は、必要となるリソース 3 段階とゆるく関連した、3 つのアプローチの概略を述べている。いちばん安いものとしては、必ずしも自分が所有しているとは限らないコンピュータ時間をかき集めるやりかた。真ん中は、プログラマブルな論理アレイを使うことだ。たとえば、チップシミュレーションなどほかの目的につくられた PLA マシンを使うことだ。ハイエンドでは、カスタムチップ方式に最新の改良を加えたものがあがっている。

しらみつぶし式の鍵探索は、こんなに人気がでるとは意外な問題だ。だれでもこの問題を考えてみれば、2⁵⁶の可能性を探索するのは、めんどうくさいけれど、できなくはないというのは自明だろう。わたしを含む多くの人たちが、なぜこの推定を精緻にして厳密にしようとがんばったのかもなぞだけれど、それよりさらに大きな謎は、1990年代後半になって、ほんとうにその鍵探索をやりだした人たちがいる、ということだ。

1997 年にサンフランシスコで開かれた、年次 RSA 暗号業界ショーで、DES暗号文をクラックした者に賞金を出すというアナウンスがされた[8]。5ヶ月後にその賞金を獲得したのは、インターネット中にちらばったコンピュータを使ったゆるい連合体だった。このアプローチは、これまで 40 ビットの鍵をもった暗号文や因数分解には適用されていたものだが、その劇的な成功だった。

1998年の RSA ショーで、また賞金がだされた。今回、賞金は39日で獲得された [9]。この結果は、実は見た目よりも大きな改善を示している。最初の鍵がみつかったのは、鍵空間を 25% しかつぶしていない時点でだった。二番目の鍵は、85% をさがし終えてやっと見つかった。つまり二番目のチームが最初のキーを見つけようとしたら、たぶん一月でそれが達成できたことになる。

こうした試みは the magnificent seven の最初のアプローチを使っている。二番目のアプローチを使ったものは、いまのところ公表されていない。本書はすぐに三番目のアプローチに飛んで、カスタムチップを使ったコンピュータについて述べている。「だれでも」つくれるマシンだ。本書にでてくる図面をつかえば、そこそこの値段で DES 鍵をものの数日で見つけられる。金さえかければ、ほんの数時間で。本書と、本書に書かれたマシンの登場で、事態は完全にかわってしまった。もはや、しらみつぶし探索で DES 鍵が見つかるか、という話ではない。それがどういう目的で、どれだけ安上がりに見つけられるか、という問題になってきている。

自分の持っていない、あるいはコントロールできない汎用マシンをネットワーク化する、というのは暗号解析コンテストに勝つには、とてもよい方法ではあるけれど、業務レベルの暗号解析には役にたたない。これをやるには、自分の活動を自分だけにとどめておく必要がある。無用な注意をひかないように保護できるハードでそれを動かせなくてはならない。本書に書かれているのは、まさにそういうマシンだ。DES は過去 20 年以上、標準となっていたわけだけれど、それでどれだけのメッセージが暗号化されたかは見当もつかない。もっと見当がつかないのは、そのなかにいまだに重要性をもつものがどれだけあって、さらにそのどれだけがディスクやテープ上に落とされて、アクセス可能となっているか、ということだ。でもその数は、この質問をどれだけ限定的に考えたにしても、かなり大きいにちがいない。こうしたメッセージのすべてが、いまや弱点にさらされていると考えるべきである。

しかしながら、弱点はこれで絶えたわけではない。というのも、暗号システムというのは殺しても死なないくらいしぶといものだからだ。DES が安全ではないとどんなに強力に論じたとしても、世界中でDES機器に大量の投資が行われてしまっているために、それをひっくり返すわけにはいかない。人々はどんなに短所があっても DES を使い続け、自分のニーズにはこれでじゅうぶんだと考え続けるわけだ。そして DES は、これだけはっきりと弱点を抱えているのに、今後何十年も情報を守っているかのようなふりを続けるだろう。

脚注

[1]パロアルトのTown and Country Villageにある、Louis Kaoの Hsi-Nan レストラン
[2] 40 Federal Register 12067
[3] Whitfield Diffie and Martin E. Hellman. "Exhaustive cryptanalysis of the NBS data encryption standard". Computer, 10(6):74-84, June 1977.
[4] R. R. Jueneman, The Data Encryption Standard vs. Exhaustive Search: Practicalities and Politics. 5 Feb 1981.
[5] Yvo Desmedt, "An Exhaustive Key Search Machine Breaking One Million DES Keys",Eurocrypt 1987で発表。 本書(Cracking DES)の第9章。 Jean-Jacques Quisquater and Yvo G. Desmedt, "Chinese Lotto as an Exhaustive Code-Breaking Machine", Computer, 24(11):14-22, November 1991.
[6] Michael Wiener, "Efficient DES Key Search", Crypto '93 のrump sessionで発表。 Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp. 31-79 (1996)　に再録。現在は以下で入手可能：
http://www.eff.org/pub/Crypto/Crypto_misc/Technical/des_key_search.ps.gz
[7] Matt Blaze, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, and Michael Wiener. "Minimal key lengths for symmetric ciphers to provide adequate commercial security: A report by an ad hoc group of cryptographers and computer scientists", January 1996. http://www.bsa.org/policy/encryption/cryptographers_c.htmlにて入手可能。
[8] http://www.rsa.com/rsalabs/97challenge/
[9] June 17, 1997, http://www.rsa.com/des/、 http://www.frii.com/~rcv/deschall.htm (February 24, 1998)、 http://www.wired.com/news/news/technology/story/10544.html、 http://www.distributed.netでの発表を参照。

xiii

はじめに

プライバシーとコンピュータ・セキュリティの分野では、まともな情報を見つけるのは実にむずかしい。ほとんどの人は本当に何が起こっているか知らないし、知っている人たちはかたろうとしない。

この本は、隠された真実を暴露するために書かれた。アメリカ政府が、情報を安全かつプライベートにするために使いなさいと推奨している標準的な手段「Data Encryption Standard」またはDESは、実は情報を安全にもプライベートにもしてくれないのである。政府は、隠したはずの情報を復号するそこそこ簡単な方法をちゃんと知っているのだ（これはDESのクラッキングとか解読とか呼ばれる）。

多くの科学者やエンジニアは、この事実を知っていたか、あるいはうすうす感じてはいた。政府が何をしているかはっきり知っていた人たちは、「機密」情報漏洩で処罰されるのがこわくて、知っていることをみんなに話すことができなかった。うすうす感づいただけの人たちは、その推測がまちがっているのではないかと思って、その推測を公表してこなかった。

この本では、われわれがDESクラック用に実際に作ったマシンを説明している。このマシンは実在するし、その存在も簡単に確認できる。アメリカではすぐに買えるし、なんなら自分で作ることもできる。このマシンは民間で設計製造されたものなので、機密にはなっていない。われわれはこのマシンをパブリックドメインに寄付したので、もはや独占権が主張されることもない。このマシンが作れるものであり、実際に作られたということも、もはや疑問の余地はない。細部まで公開してあるので、ほかの科学者やエンジニアたちもわれわれの作業をレビューし、再現し、さらに発展させることもできる。もう疑問の余地はない。DESは安全ではない。

xiv

各章の概要

本書の最初の部分は、DESクラック用マシンをつくろうというElectronic Frontier Foundationの研究プロジェクトについての説明である。次の部分では、われわれのデザインしたマシンの技術的な詳細がすべて記述してある。これは暗号研究コミュニティによるレビュー、批判、検討、そしてさらなる発展のためにやったことだ。最後の部分では、DESを解読するための総当たり方式について、見つけにくい技術報告をいくつか含んでいる。

技術的な説明

第一章 概論ではプロジェクトを紹介して、EFFのDESクラック用マシンの基本的なアーキテクチャを説明している。

第二章 設計仕様（Paul Kocher著、Cryptography Research）は、ソフト作者の観点からマシンの仕様を述べている。

第三章ハード仕様（Advanced Wireless Technologies著）は、ゲートアレイのカスタムチップと、それをのせるボードについて、ハード設計者の観点から説明している。

技術的な設計詳細

第４章 ソースコードのスキャン では、この本を光学式のスキャナに通して、われわれの設計したソフトと、専用ゲートアレイチップをつくるためのソースコードを正確に再現する方法を説明している。

第5章ソフトのソースコードには、PC上で走ってDESクラッカーの制御をするC言語のソフトのソースの完全なリストがある。

第6章チップソースコードには、ゲートアレイのカスタムチップを設計したときのチップデザイン言語（VHDL）コードの完全なリストがある。

第7章チップシミュレータのソースコードには、チップの働きをシミュレートするC言語のソフトの完全なリストがおかれている。これはチップの機能を理解して、チップがきちんとつくられたかどうか確認するためのテストベクトルを生成するのに使う。

第8章ハード基板の構成では、カスタムチップに電力とコンピュータ用インターフェースを提供する基板の回路図と、基板レイアウトやそれをつなぐバックプレーンの配置などがかかれている。

xv

関連研究論文

第9章百万DESキーを破るには（Yvo Desmedt著）は1987年の論文で、多くのDESキーを同時に探索できるマシンについて、おもしろいデザインを提案している。

第10章暗号分析ハードのアーキテクチャに関する検討（Ian Goldberg and David Wagner）は1996年の研究で、DESなどの暗号をプログラマブル・ゲートアレイチップを使ってクラックする方法を検討している。

第11章効率のよいDESキー探索：追補（Michael J. Wiener）は、1993年にかれが発表した重要な論文に含まれた技術的な推定を、1998年のものにアップデートしたものである。この論文は、DESクラック用のカスタムチップについて、完全な回路図を載せた初のものである。

第12章著者たちについてはこのプロジェクトの構築で協力した組織や企業について説明している。

1

概論

本章の内容:

• 解読の政治性
• ねらい
• DES クラッキングの歴史
• EFFのDESクラッカープロジェクト
• アーキテクチャ
• ほかにはだれがDESをクラックしているだろう？
• DESを使っていたらどうすればいいの？
• 結論
  

解読の政治性

Electronic Frontier FoundationのDESクラッカープロジェクトを開始したのは、解読の政治性に興味があったからだ（脚注）。DESのように広く使われている暗号規格がどれだけ弱いものかということを社会が理解するのは重要なことである。

「DESクラッカー」というのは、データ暗号化規格（DES）で暗号化された情報を、暗号化の際に使われた鍵を発見することで読める機械である。「DESクラッキング」はこの探索プロセスの名前だ。これをいちばん簡単に行うには、正しいものがみつかるまで、可能な鍵を片っぱしから試していくことだ。手間のかかるやり方で「ばか力探索（brute-force search）」と呼ばれる。

　もしDESで暗号化された情報が、それを見ていいことになっていない人物によって、簡単に解読できてしまうなら、DESを使うインフラのプライバシーとセキュリティはリスクにさらされることになる。多くの政治的、社会的、技術的な意志決定は、DESを解読するのがとてもむずかしいという前提で行われている。

われわれは、いろいろな状況で、アメリカ政府のとても有能で尊敬も受けている人々が、DESをクラックするのにどれだけかかるか、という発言を行う事例が増えているのに気がついた。いずれの場合にも、こうした発言はわれわれの推定や、暗号研究者たちの見解とはかなりちがっていた。もっとひらたく言ってしまうと、こうした政府の役人は、うそをついているか、無能か、あるいはその両方なわけだ。かれらは、DESのクラックがわれわれの考えるよりもずっとずっと高価で時間がかかる、と発言していた。非常に信頼性の高い研究論文の予言では、DESを3-1/2時間でクラックするマシンは、開発コストまでいれても150万ドルでつくれる、と推計している。それなのに政府からでてくる推定では、メッセージ一つを解読するのにコンピュータ何千台も使って、数週間から数年はかかる、ということになっていた。

_______________

* DES （データ暗号化規格）は秘密鍵を使って機密メッセージを暗号化し、スクランブルされた出力に変える。この入力メッセージは「平文」とも呼ばれ、結果的な出力を「暗号文」とも言う。考え方としては、その秘密鍵を知っている受け手だけが暗号文を復号し、もとのメッセージを入手できる、というものだ。DESは56ビットの鍵を使っているので、鍵の可能性は 2⁵⁶ 通りある。

1-1

1-2

1997年6月26日木曜日、アメリカ議会下院の国際関係委員会が、非公開の機密証言を受けている。この委員会は、暗号についての輸出規制を廃止する法案を検討していた。この証言のあとで委員会は法案は書き換え、正反対の内容の代替案をかわりに入れた。一ヶ月後に、公聴会の検閲を受けた議事録が提供された。全文は http://jya.com/hir-hear.htmを見てほしい。ここに抜粋を載せる。

FBI Director、Louis J. Freehの発言：

. . . それにそういう情報に対してリアルタイムのアクセスどころか、まともに使える速度でのアクセスすら、できるようなコンピュータもテクノロジーもないんです。

何千ものコンピュータをつないで、それを4ヶ月まわし続けたら、最近実証されたみたいにメッセージ一つ解読できるかもしれません。そんな時間がかかったら、誘拐事件では意味がありませんし、国家安保にかかわる事態でも無意味です。そういう情報を得るだけの技術もないし、ばか力式の能力もないのです。

国家安全保障機関（National Security Agency）Deputy Director、William P. Crowell, Deputy Directorの発言

...さらに言わせてもらえればLouis Freehの組織が単に技術的にもっとレベルをあげればいいのだ、なんていう人がいます。もうちょっと技術に明るくなったら、こんなものはすぐに破れる、とね。これについては、統計を一つだけあげます。そうしたら法案そのものについてちょっと申し上げておしまいにしましょう。

法執行機関には、ばか力式の解決はできないのです。 [墨ぬり-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --] 学生のグループが -- いや、学生ではありません -- インターネットの連中が先週、56ビットDESを使ったメッセージ一つを破りました。一つ解読するのに、78,000台のコンピュータで96日かかっているのに、新聞の見出しは「DESの暗号は弱い」ですからね。

かれはこれがそんなに弱いとは思いません。これが64ビットの暗号なら、そしてそれはいまも輸出できて、さらに国内では自由に使えるわけですが、同じことをやれば7000年かかることになります。そしてこれが128ビット暗号なら、PGP, pretty good privacyがそうですが、宇宙の年齢の8.6兆倍かかったでしょう。

1-3

公聴会で後出のコメント

Gilman議長：暗号解読の必要があったら、追加のマンパワーと機器が必要になりますか？そしてそれは、いまでもめんどうな盗聴での言語の翻訳の問題を増やすものになりますか？

Director Freeh：まちがいなくそういう追加のリソースは必要になりますが、それよりもさっきここで述べた論点のほうがだいじだと思います。National Research Council はFBI にもっとコンピュータを買えとすすめますし、ビル・ゲイツはわたしに、FBIの研究開発をアップグレードしろといいますが、[墨ぬり------------------------------] アメリカの産業界にもできないことで、それは最低限の堅牢さをもって、リアルタイムの暗号を解読することです。[墨ぬり---------] もし300万ドルもらえて、それでCrayコンピュータを買えたら、それでメッセージ一つ解読するのに何年かかります？

Mr. Crowell：64ビットなら7,000年。

Director Freeh：誘拐事件では、そんな悠長はことはしてられないのです。こっちがつぶれてしまいます。

1998年3月17日、On March 17, 1998, Principal Associate Deputy Attorney GeneralのRobert S. Littは、アメリカ議会上院司法委員会の憲法・連邦主義・所有権小委員会で証言した。公聴会のテーマは「デジタル時代のプライバシー：暗号と義務的アクセス」である。リット氏証言の全文は、以下にある： http://www.computerprivacy.org/archive/03171998-4.shtml DESクラッキングと関係ある部分は以下のとおり：

なかにはこれが、法執行機関のリソース問題にすぎない、という人もいます。この人たちは、犯罪の証拠となっている通信やデータの平文に、法的なアクセスが必要となったら、法執行機関が単に資源を強力暗号コードの解読に集中させて、鍵を全部試してみればいいのだと思っているのです。でも、このアイデアはまったく使い物になりません。こういうばか力式の解読は、公安保全に使うには時間がかかりすぎるからです。たとえば56ビット鍵のメッセージ一つを解読するだけで、ペンティアム級コンピュータ14,000台で4ヶ月かかりました。これだけのリソースは明らかにFBIにはありませんし、ましてジェファソン市警なんかにあるわけがない。

こうした証言のどこがまちがっているのか？

ここで引用した証言の一部は、文字通りの意味では正しいものもある。でも、ここにはごまかしが入っている。政府監督官僚たちが挙げた解読時間推定はすべて、汎用コンピュータを使った数字に基づいている。でもこれはやりかたとしては根本的にまちがっているし、この役人たちはそれを知っているはずなのだ。

普通のコンピュータは、DESクラッカーとして使うにはむいていない。そもそもDESのデザインからして、ソフトでやるには性質上とても遅いけれど、ハードでやるととてもはやいのである。さらに、いまのコンピュータは並列処理をほとんどしない。チップ設計者たちは、どんな命令が実行されるかわからないので、あらゆる組み合わせに対処できるようにしなくてはならないからだ。

1-4

DESをまともにクラックしようと思ったら、専用ハードを使うことだ。カスタムチップは、クロックが遅くても最高速の汎用コンピュータに楽々勝てる。さらには、ボード一枚にチップをたくさんのせることも可能だ。ふつうのコンピュータは、マザーボード上にチップ一つしかない。

ばか力探索方式でクラックできる鍵のサイズには、現実的に考えれば限界はあるけれど、DESが設計された1970年代に、NSAは意図的にDESの鍵のサイズを56ビットに制限したので、DESはばか力方式でクラックできる。今日のテクノロジーでは、64ビットや128ビットの鍵をもった暗号方式は、解読できないかもしれない---が、できるかもしれない。だれかが試して、その結果を公開し、科学的な検討をうけるまでは、だれにもわからない。こうした暗号方式は、DESとは内部構造もかなりちがっているので、その方式の構造を利用することでかなりの数の鍵を除外できてしまうかもしれない。高名な暗号学者たちが、安全のために必要な鍵のサイズについて1996年の論文で推定を発表している*。それによると、ばか力クラッキングに対抗するためには最低でも75ビット、そして20年にわたって情報を保護するには、最低でも90ビットの鍵がいる、とされている。

またばか力方式の探索コストの推定も、現実世界で暗号化テキストを復元するコストを過大に見積もっている。法執行に対して暗号が及ぼす現実的なインパクトについての、重要な報告⁺によると、警察が暗号化ファイルにアクセスできなかったために、容疑者が釈放される結果となった事例は、実は一つもない。多くの場合、平文はほかの手段で復元されている。たとえば容疑者に鍵を出すよう要求したり、ディスク上でその情報の別のコピーを見つける、などの方式である。ばか力方式を使わなければならなかったときにさえ、キーが本当にランダムだったことはほとんどなく、ありそうな順に探すことができた。

輸出規制と DES

いまのアメリカ政府は、企業や個人が機密保持のためにDESを使うハードやソフトを輸出することを制限している。こうした「輸出制限（export controls）」は、ネットワーク化されたコンピュータや携帯電話など、一般用の通信装置のセキュリティとプライバシー開発にとって、強烈な阻害要因となってきた。DESより強い暗号化アルゴリズムの使用も規制されている。

1996年12月、政府は正式に輸出業者に対し、DESを製品に含めていいという許可を与えた。ただしそれより強いものは認められない。そしてこの許可の代償として、こうした企業は政府との同意書に署名しなくてはならず、その同意書はその企業たちに、2年以内に製品に「キーリカバリ」を含めるよう義務づけるものとなっていた。

___________________

* Minimal Key Lengths For Symmetric Ciphers To Provide Adequate Commercial Security: A Report By An Ad Hoc Group Of Cryptographers And Computer Scientists. Matt Blaze, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, Michael Wiener, January 1996. Available at http://www.bsa.org/policy/encryption/index.html.

+ Encryption and Evolving Technologies: Tools of Organized Crime and Terrorism, by Dorothy E. Denning and William E. Baugh, Jr. National Strategy Information Center, 1997. ISSN 1093-7269.

1-5

キーリカバリは、各メッセージに使った鍵のコピーを提出させて、政府が好きなだけメッセージを解読できるようにして、しかもそれを製品のユーザは防止したりコントロールしたりできないという方式である。一言で、政府が要求していたのは：おれたちと野合して顧客のプライバシーを侵害させろ、さもないと高セキュリティ製品はいっさい輸出させてやらない、ということだ。

同時に、各個別業の暗号製品輸出申請書を検討するグループにFBIも加えられた。あらゆる報告が指摘しているのは、FBIが強力なおどしをかけていて、国家の安全保障に対していっさい脅威とならないようなさまざまな製品（というのも、それらの製品はFBIが口出しするようになるまでは輸出できていたから）についても、輸出に反対しているということだ。FBIはどうやら、自分が嫌われ、おそれられるようになれば、会社たちが命令にしたがうようになる、と考えているらしい。ところが実際はかえって、企業たちはFBIが輸出規制を悪用できるようにした規制法規の撤回を求めるようになってしまった。業界は大規模なロビイング団体Americans for Computer Privacy (http://www.computerprivacy.org)を設立しているが、これは民生暗号輸出についてはいっさい規制がかからないように、法改正を求めている。

何十かの企業がキーリカバリに合意したようだが、キーリカバリを導入するという約束を本気で守るつもりの企業が、実際にはいくつあるのかははっきりしない。こうした企業のなかで、製品の広告にキーリカバリをうたったものはほとんどない。ユーザは、キーリカバリがセキュリティに制限をつけるものなのを知っているので、あまり歓迎しない。もし顧客がそういう製品を買わないのなら、開発しても意味がない。

企業としていちばんいいのは、おそらくは本当のセキュリティを提供できるような製品を、世界の中で輸出制限のかからない地域で開発することだ。すでにこれをやっている企業もある。でも政府が「妥協案」を提供しているため、足踏みしている企業はあえてここまでやろうとしない。この妥協案では、もっと穏健な折衷案を採用してもいいよ、というものだ。わざわざ外国に暗号開発力をおくだけの手間をかけた企業は、みんなDESより強い技術を使っている。これはセールスポイントでもあり、また技術の陳腐化を防ぐことにもなる。もしこういう企業がアメリカ国内にとどまり、政府のキーリカバリに参加し、DESを見放さないように説得できるなら、政府の勝利は続き、市民のプライバシーは負け続ける。

この政府のニンジンぶら下げ方式の成否は、業界と市民たちがDESのセキュリティについて誤解したままでいてくれるかどうかにかかっている。もしDESを使った製品がセキュリティが低いと思われてしまえば、会社はDESなどというろくでもない代物ごときのために、顧客の生得のプライバシー権を譲り渡すのに同意する理由はない。もしDESを使った製品が高セキュリティと思われていて、でも政府が実はそれが低セキュリティなのを知っているとしたら、政府は企業から譲歩を引き出せる一方で、自分は通信を傍受できる能力を温存できる。そして市民にそれを知られなければ、政府としてはいちばんいい思いができるわけだ。

1-6

政治的な動機とEFFの対応

われわれは、アメリカ政府官僚が意図的にDES暗号の強さについて誤解するようにしむけているのだと考える。その狙いは：

• 市民たちにDESを使い続けさせて、政府機関が市民たちを盗聴できるようにする。
• 政府が解読に苦労するような、DESよりもっと強力な暗号規格が広がるのを防ぐ。
• DESの輸出可能性を取引材料としてちらつかせる。これは政府にとってはコストがほとんどないけれど、価値があると思われている。
• 議員や大統領など、政策立案者たちに、法執行機関が暗号化データでとても困っていて、それを解読する現実的な方法がないと思わせることで、キーリカバリなどのとんでもない手法を採択させる。

暗号政策推進者として、われわれはつらい立場におかれることとなった。非常に地位の高い人たちが、自分たちの有害な狙いを推進するために、議会や市民に対して意図的にウソをついているか、あるいはそこに含まれる問題について無知なために、市民の自由を深刻なかたちで侵害しようと主張しているとしかわれわれには思えなかった。かれらがウソをついているという可能性がいちばんこわかった。こうした政府官僚は、単に価値の高い機密作業を公開しないための盾になっているつもりだったのかもしれない。よい政府を支持する者として、われわれはプログラムを機密にしたいからといって、官僚がそれについて証言するときに自らを欺くようなことは正当化されないと考える。（意見を述べるのを拒否するというならまだわかるが、真実でない発言を事実であるかのように述べるとなると、話はまったく別だ）。

National Research Councilは、暗号問題について研究して、1996年に非常に充実した報告を発表した*。この報告でいちばん興味深い結論は、「国家の暗号政策に関する議論は、機密としない状態でもじゅうぶんに実施できる」というものだった。これは、機密の影に隠れている政府機関が誠実に対応してくれるものという前提があってのことである。もしかれらの声明が、世論を操作しようとするウソであるなら、正直でまともな一般議論は絶対にかれらを不正直でまともでない参加者として排除しなくてはならない。

一方で、もし政府高官が無知または無能なために劣悪な政策決定が行われているのであれば、正直な支持者の役割は、議論に貢献することだろう。

_________________

* Cryptography's Role In Securing the Information Society, Kenneth W. Dam and Herbert S. Lin, editors. National Academy Press, Washington, DC, 1996.

1-7

こうした懸念に答えるため、EFFは研究プログラムを開始した。この研究結果で、DESが短期間で安上がりにクラックできることが証明された。これは、役人たちがうそをついていたか、無能だったということを証明している。本書はその研究を記述したもので、ほかの科学者がそれを確認できるようにするためのものだ。

ねらい

EFFのDESクラッカー研究プロジェクトのねらいは、DESをつかいものになるかたちでクラックするマシンをつくるのが、どれだけ安上がりか高価かを見極めることだ。

技術的には、平文認識装置の優れた設計を検討することにも興味があった。平文認識装置とは、復号結果が正しいものである可能性が高く、専用ソフト（または人間）が見てる価値があると認識してくれる回路だ。これについてはほとんど研究が発表されていないものの*、暗号解析の有効なシステムにおいてはかならず重要な位置を占める回路だ。

この研究をするだけでも、EFFはDESをクラックする費用についての真相を知ることができる。でも、その研究を公表して機械をデモすることでのみ、DESの強さについての真相を一般に報せることができる。プレス発表や技術論文だけでは不十分だ。もしそれでいいなら、Michael Wienerのすばらしい1993年論文に100万ドルのDESクラッカーの回路が登場しているのだから、すでに用は足りているはずだ。でも、人々はいまだにDESを導入し、議員たちはその強さについて、高官たちの保証をめくら滅法にうのみにし続けている。

自分の目で実際に見るまで、真実であっても信用しないという人は多い。DESをものの数日でクラックできる物理的なマシンを本当に見せるというのは、DESにセキュリティを託すことはできないというのを、そういう人たちに納得させる唯一の方法だ。

別の人々は、ほかのチームが何度かそのマシンを再現しない限り、われわれの主張を信用しないだろう（これは科学的手法の基本的な部分である）。それに、多くの人はこういうボックスがどういう仕組みで動くのか、そしてどうやってそれがたった20万ドルでつくれたのか、当然ながら興味を持つだろう。この本はそういう人たちのためにかかれた。ここにはDESクラッカーの完全な仕様と設計書が掲載されているし、基板の回路図も、ソフトやゲートアレイの設計についても完全なリストがあがっている。われわれの設計をすべて公開したことで、ほかのチームは短時間でこれを再現し、確認し、さらに設計を改善させることができる。

_________________

* しかしながら、 David A. Wagner and Steven M. Bellovin, "A Programmable Plaintext Recognizer," 1994 （http://www.research.att.com/~smb/papers/recog.psまたは recog.pdf）を見よ。

1-8

DES クラッキングの歴史

DESクラッカーは、1970年代から科学文献や一般文献でなんどか言及されてきた。Whitfield Diffieの序文にもそのいくつかがかかれている。近年で、いちばん詳細にそれを記述したのは、1993年にBell Northern ResearchのMichael Wienerが発表したものである。Wienerの論文は、カスタムチップで作ったDESクラッカーの詳細設計をふくんでいた。チップは基板にのり、そのボードが電話交換機みたいに機械的な「フレーム」におさまることになっている、この設計を実現しようと思ったら100万ドルほどかかり、平文と暗号文が与えられていれば、平均3-1/2時間（最悪7時間）でDES鍵を見つけられる。

Wiener氏はこの論文の結論を1998年に更新した。5年間の技術的な変化を反映させるためである。この更新した論文も本書に含まれている。この更新版をもともと刊行したRSA Data Securityには、許可を与えてくれて感謝したい。

カリフォルニア大学バークレー校のIan Goldberg と David Wagner は、別のアプローチをとっている。かれらの設計では、「現場プログラム可能ゲートアレイ（field programmable gate array, FPGA)を使っている。これは、製造したあとからプログラミングして、いろいろな回路にしたてることができるチップだ。

FPGA チップは、Wienerの設計に使ってあるカスタムチップよりもおそいけれど、少量でもすぐに買えて、設計に大きな初期投資がいらない。でっかいマシンを設計するのに、百万ドルのかなりの部分を使ってしまうよりも、この研究者たちは汎用チップをいくつか買ってきて、それをおそいDESクラッカーになるようにプログラムした。このおかげで、この遅いチップをどれだけ積み上げれば、つかいものになるDESクラッカーがつくれるかをすぐに計測できた。この論文も本書に収録されている。

EFFのDESクラッカープロジェクト

Electronic Frontier FoundationがDESクラッキングの検討をはじめたのは、1997年のことだった。最初の計画では、FPGAをたくさん使ったDESクラッカーができないかと考えていた。

FPGAでできた大規模マシンは、商業市場に存在している。これはチップ製造前に、大規模な新チップをシミュレートするために使われる。比較的能力の低いFPGAを何千も集めれば、非常に性能の高いカスタムチップをシミュレートできる。ただし速度は、実際のカスタムチップの1/10から1/100になる。この機能を使って、チップ設計者は高価で時間のかかる物理チップをつくる前に、チップの「バグ」を取り除く。

EFFは、結局そんなチップシミュレータは調達しなかった。かわりに、検討をすすめるなかで、Cryptography ResearchのPaul Kocherに出会った。ポールはこれまでに、カスタムゲートアレイチップを、何千個単位のバッチで安くつくってくれる、ハード設計者といっしょに仕事をしたことがあったのだ。

1-9

ポールとEFFは、Advanced Wireless Technologiesの技術者と会って、20万ドルくらいの予算でつかいものになるDESクラッカーがつくれると見積もった。できるマシンは、例となる8バイトの平文と暗号文が一つわかっていれば、平均で一週間以下でキーをつきとめられる。さらに平文の統計的な特徴がわかっていれば、そのキーを16ビットの暗号文から推定するのも、ほとんど同じくらいしかかからない。たとえばもし平文が電子メールのメッセージなのがわかっていれば、このマシンは文字や数字や記号しかない平文をうみだすキーをすべて発見できる。こうすればこのマシンは、現実世界の暗号解読問題を解決するのに使いでが高まる。

われわれのDESクラッカーに、革命的な部分はなにもない。DESをどうクラックすればいいかについて、暗号研究コミュニティでは何年もまえからでまわっていたふつうのアイデアを使っている。唯一のちがいは、われわれは論文を書くだけでなく、それを本当に作ってしまったということだ。ほとんど同じマシンは、去年だろうと一昨年だろうと、5年前、10年前だろうとつくれた。ただ、速度は遅くてもっと高価だったかもしれないけれど。

アーキテクチャ

EFFのDESクラッカーの設計は、考え方は簡単だ。ふつうのパソコンを、大規模なカスタムチップ・アレイにつないだだけである。パソコン側のソフトは、カスタムチップに探索をはじめろと告げて、ユーザとのやりとりも担当する。カスタムチップはその後は、おもしろそうな鍵を見つけるか、あるいは探索用に鍵空間の新しい部分を指定してもらうまで、ソフトからは指図を受けない。ソフトはたまにチップにお伺いをたてて、おもしろそうな鍵がみつかったかどうかを調べる。

ハードウェアの仕事は、答えを見つけることではない。むしろ、正しくない答えの大部分を排除することだ。そうすれば、残りのただしいかもしれない鍵を検索する仕事は、ソフトの速度でも十分に対応できる。ソフトが、「もっともらしいもの（false positives）」を本当の答えから仕分けしてくれるわけだ。このマシンの強みは、単純だが強力な探索回路が何千回も使われるため、ソフトで鍵空間のごく一部を探索するだけで答えがみつかる、という点にある。

ちょっとのソフトで協調させるだけで、DESキーの探索問題は「高度に並列処理可能（highly parallelizable)」である。つまり、たくさんのマシンを同時に動かすことで、問題を効率よく解決できるということだ。たとえば、DESクラッカーチップ一つでなら、鍵を探すのに何年もかかる。DESチップを千個使えば、同じ問題を千分の一の時間で解決できる。DESチップが100万個あれば、理論的には同じ問題が100万分の一の時間で解決できる。ただしこの場合には、各チップをスタートさせるときのオーバーヘッドが必要時間にきいてきてしまうだろう。われわれの作った実際のマシンは、チップ1536個を使っている。

1-10

ばか力式の探索を行うときには、もちろん鍵をかたっぱしから探していくことになるわけだが、多少のコツはある。キーはどんな順番で探してもいい。もしキーがランダムではないと思ったら、可能性の高そうなものから試していくといい。正しいキーがみつかれば、そこで止めればいい。残りはためさなくていい。最初の百万回で見つかるかもしれないし、最後の百万回でみつかるかもしれない。平均では、道半ばで見つかることになる（つまり可能な鍵を半分までためしたところで）。だから、バカ力方式の所要時間は、ふつうは鍵をみつける平均時間で示される。最大必要時間は、平均時間の二倍だ。

探索ユニット（search unit）

EFF DESクラッカーの核となるのは、探索ユニットだ。DESクラッカーには探索ユニットが何千も入っている。

探索ユニットは小さなハードウェアで、鍵と暗号文の64ビットブロックを2つとってくる。その暗号文を鍵で復号してみて、でてきた結果が「おもしろい」かどうかを調べる。おもしろくなければ、鍵に1を足して同じことを繰り返し、鍵空間をずっと探していく。

もしこの最初の復号が「おもしろい」結果をうみだせば、同じ鍵で暗号文の次のブロックを復号してみる。もしどっちの結果もおもしろければ、探索ユニットは止まって、ソフトに対しておもしろい鍵を見つけたよ、と連絡する。二番目のブロックの復号結果がおもしろくなければ、探索ユニットはまた鍵に1を足して、鍵空間の探索を続ける。

おもしろい結果をみつけて探索ユニットが止まったら、ホストのコンピュータは結果を検討して、それが本物の答えか、それともただの「もっともらしいもの」かどうかを検討しなくてはならない。もっともらしいものというのは、ハードが見たらおもしろそうに見えたけれど、実際には問題の答えではない平文のことだ。ハードウェアは、本物の答えとならんで、ある程度はもっともらしいだけの結果を出してくるように設計されている。（ハードウェアの仕事は、答えを見つけることではなくて、絶対に答えではない大半のものを排除することだ）。もっともらしいものがたくさん出てきすぎて、ソフトがそれをチェックしてはねられなくなると困るけれど、そうでなければもっともらしいものがあっても別にかまわないし、それを許せばハードも簡単になって、汎用性が高くなる。われわれが解こうとしているような問題では、ハードがもっともらしいもので無駄にする時間は、探索時間の1％以下になるよう設計されている。

1-11

おもしろい平文の識別

おもしろい結果って、どういうことだろう。もし平文があらかじめわかっていれば、おもしろい結果というのは、その鍵で得られた平文が、わかっている平文とマッチする、ということだ。もしもとの平文がわからなければ、それが全部、文字や数字や記号だけでできていれば「おもしろい」といえるかもしれない。この検討は、簡単にして柔軟でなくてはならない。結局われわれが使ったのは、ハードにとっては単純だけれど、ソフトのほうにはちょっと負担がかかるものだ。

それぞれの結果は、8ビット長バイトを8個ふくむ。それぞれのバイトがとれる値は、256とおりある。探索ユニットは、この256個のうちでどの値が「おもしろい」もので、どれがつまらないかを定義した表をもっている。たとえば平文が全部数字だというのがわかっていれば、ソフトはこの表で、数字10個（0から9まで）がおもしろくて、それ以外の値はぜんぶつまらない、と定義する。

まちがった鍵で復号してやると、結果はほとんどランダムといっていいものになる。だから一つのバイトが「おもしろい」ものとなる確率は、256通りの可能性のうち、「おもしろい」と定義された部分がどれだけあるかによって変わってくる。たとえば、69文字がおもしろいとされていたら（A-Z, a-z, 0-9, 空白, その他句読点など）、ランダムなバイトがおもしろいものになる確率は、69/256 で、つまり約1/4ということになる。これだとあまり分がいいようには見えないでしょう。チップは鍵の4つに一つで止まって、ソフトに「おもしろい」けれどまちがった鍵を見せることになる。

でも「おもしろい」判定は、結果のすべてのバイトに適用される。もしまちがった鍵のバイトがおもしろい確率が1/4なら、2バイトがおもしろい可能性は1/4のそのまた1/4, つまり1/16になる。3バイトなら、1/4の1/4の1/4、つまり1/64だ。この調子で、チップが結果の8バイトを検討し終わると、まちがった鍵は全体の1/65536(l/4⁸)に限られてくる。

これはかなり小さい数に思えるけれど、なにせ今は 2,057,594,037,927,936個の鍵 (2⁵⁶の鍵、または7.2京の鍵）を探しているので、もっともっと手助けが要る。ソフトに可能な鍵の1/65536をチェックさせるだけでも、1,099,511,627,776個の鍵（2⁴⁰ または1兆個の鍵）を調べなくてはならないことになる。そこでチップが、もうすこし手助けをするようになっている。

この助けを提供してくれるのが、暗号文の2つめのブロックだ。もし暗号文の最初のブロックで、結果のバイトがすべておもしろかったら、チップは今度は、同じ鍵で二番目の暗号文を復号してみる。これで「まちがい率」はさらに65536分の一になって、ソフトはたった16,777,216 (2²⁴または1600万くらい）の鍵を見るだけですむ。いまのコンピュータのソフトは、このくらいならそこそこの時間で見てしまえる。

(もし暗号文が1ブロックしかわかっていなければ、同じ暗号文を両方に入れるだけだ。チップは同じものをテストして、いずれおもしろいブロックを教えてくれる。同じことを二回やるわけだけれど、これで無駄にする時間というのは、探索の総時間のなかでほんのわずかだ。）

1-12

また平文認識の部分には、平文のどのバイトを調べるとおもしろいかを指定できる8ビットがある。たとえば、平文の値の最初の6バイトの中身は知っているか見当がついて、残りの2バイトについてはなにも知らないなら、その6バイトのところだけマッチする鍵を探すことができる。

平文がわかっているとき

もし、平文についておおまかな性質だけでなく、それ自体がわかっていたら、チップから出てくる「もっともらしいもの」はぐっと減ってくる。この場合、「おもしろい」ものとなるバイト値はごく少数しか出てこない。もし平文に繰り返されるバイト値がなければ、おもしろいバイト値は、上の69個ではなく、8個にしぼられる。

たとえば、もし平文のブロックが「hello th」だったとしよう。するとおもしろいのは「h」「e」「l」「o」「t」空白だけがおもしろい。もし平文がこういうバイトだけを含んでいたら、それはおもしろいことになる。もっともらしいものはいくつか出てくるだろう。「theolo tt」などというのも、正解ではなくても「おもしろい」と見られるからだ。

この「おもしろい」の定義を使うと、まちがった鍵で出てくるバイトがおもしろくなる可能性は、8/256または1/32だけになる。8バイトすべてがおもしろくなる可能性は、1/32の8乗(1/32の1/32の1/32の1/32の1/32の1/32の1/32の1/32)、つまりは1/1,099,511,627,776(1/2⁴⁰)しかなくなる。つまり、探索ユニットは、おもしろそうな鍵を報告するまでに、平均で1兆個くらいの鍵を試せるわけだ。だから、止まったり、ソフトにかまったりして速度を落とさずに、かなり長時間探索を続けられることになる。

Speed

いったん動き始めたら、探索ユニットは16クロックサイクルで復号を一つできる。われわれの作ったチップは40MHz（1秒に4000万ヘルツ）で動ける。16を4000万で割ると、各探索ユニットは毎秒だいたい250万鍵くらいを試せるのがわかる。

探索ユニットをつくるにあたり、鍵に1を足すときの回路を簡単にすればスピードをあげられることを発見した。全ビットゼロの鍵から、全ビット1の鍵までずっと数えられるようなしかけにせずに、鍵の下32ビットだけ数えるような加算回路を採用してある。てっぺんの24ビットはずっと同じままだ。毎秒250万鍵という速度だと、てっぺん24ビットが同じ鍵をすべて探索しつくすのには1717秒（約30分）かかる。その30分が終わったら、ソフトがチップを止めて、24ビットに新しい値を入れ直して、またチップを走らせる。

1-13

フィードバックモード

チップはまた、「暗号ブロック連鎖モード（Cipher Block Chaining）」モードで暗号化された暗号も復号できる設計となっている。このモードでは、各ブロックの暗号文は、暗号化される前に次のブロックの平文にXORされる（平文の最初のブロックには「初期化ベクトル」がXORされる）。探索ユニットは、最初の暗号文を復号してから、初期化ベクトル（IV）をXORしてはずすやりかたを知っているし、さらに二番目の暗号文を復号してから最初の暗号文をXORしてはずす方法も知っている。IVの指定は、暗号文の値を指定するときと同時にソフトが指定する。

Blaze 式チャレンジ

1997年6月には、AT&Tの暗号研究者のMatt Blazeが、別の種類の暗号問題を提案した。かれが考えていたのは、提案者ですら解決方法を知らず、鍵空間を大量に探索したり、DESの構造を暗号解析しないでもいいような問題だった。

かれの問題というのは、 XXXXXXXX という形式の鍵が復号されるとYYYYYYYYのようなかたちになる鍵をみつける、というだけのものだ。このとき、XとYはそれぞれ任意の固定8ビット値で、それがブロックの8バイトすべてで繰り返されているわけだ。

探索ユニットにちょっとハードを追加して、この問題の解決も手伝うことにした。ユニットには、復号した平文がおもしろいかどうかを調べる前に、平文の右半分を左半分にXORするオプションがつけてある。YYYYYYYYという形式の平文では、これは平文の左半分がすべてゼロになるということだ。こうすれば平文認識を設定するときに、左半分だけを見て、おもしろいのはゼロだけ、ということにしておく。これは大量の「もっともらしい」結果を作り出す（右半分と左半分が同じになっている平文、たとえばABCDABCDなどはすべてあてはまる）ことになるけれど、でもそれは、パフォーマンスを1%くらい下げるだけで、ソフトによってスクリーニングできる。

マシンの構成

これで探索ユニット一つの仕組みはわかってもらえたので、これを組み立ててマシン全体を作ってみよう。

各探索ユニットは、カスタムチップの中におさまっている。チップ一つには、探索ユニットが24個入っている。一つのチップ内部の探索ユニットは、すべて同じ暗号文ブロックと、初期化ベクトルと、同じ「おもしろい」結果値の表を共有している。各検索ユニットは独立した鍵をもって、独立にとめたり走らせたりできる。

チップのピンは簡単なインターフェースだけを提供する。探索ユニットのどれかが止まったかを告げる信号がいくつか、ソフトが探索ユニットに読み書きできるような、アドレスとデータ用のピンがいくつか、そして電源と設置用のピンがある。

1-14

各探索ユニットは毎秒250万鍵を探索するので、24の探索ユニットを持ったチップは毎秒6000万鍵をためせる。でも、相手にしている鍵もたくさんある。チップ一個なら、平均で鍵を見つけるのに6,950日かかる（約19年だ）。鍵空間全体を探すには38年かかる。そんなに待つのはいやだったから、チップはもっとたくさん使うことにした。

各チップは、大きな回路基板にマウントされている。基板一枚に64チップがのり、さらにインターフェース用の回路も少々のっている。基板は、ソフトがその基板とやりとりしているときにはLEDが光るようになっている。ほかにランプが64個あって、各チップの探索ユニットが止まったときには光ってわかるようになっている。ふつうの使用だと、ソフトは数秒ごとに基板とやりとりをして、チップを調べてまわる。チップはほんのたまにしか止まらず、さらにすぐにソフトで再起動がかけられなくてはならない。

基板は、「9U」VMEバスの基板の仕様にあわせて設計されている（約38センチx38センチ）。VMEバスはコンピュータ基板用の工業規格で、1980年代にはよく使われた。VMEバスのサイズを使ったのは、そういう基板を差し込める装置が簡単に手に入るからだ。VMEバス自体の電気仕様は使っていない。

9U VMEバス基板は、汎用PCにささるふつうのインターフェースカードよりずっと大きいので、一枚にのるチップの数もずっと多くなる。さらに9U VMEバス基板は大量の電源が供給できる設計になっていて、DESクラッカーチップにはこれが必要だ。

各チップは毎秒6000万鍵を探索するので、チップ64個のった基板は、毎秒38億鍵を探索してくれる。鍵空間を半分探索しつくすには、この基板一枚で109日かかる。これでもまだ、そんなには待ちたくなかったから、基板ももっとたくさん使うことにした。

基板はラック、またの名を「カードケージ」にさした。現在の設計では、このラックは1990年頃のSunワークステーションパッケージをリサイクルしたものを使っている。Sun Microsystemsは、大型の9U VMEバス基板を使うシステムをたくさんつくっており、こういうシステムは基板の電源と冷却の点でもきわめて優れている。Sun-4/470 のシャーシはVMEバス基板のスロットを12個分持っていて、こちらの要件にあうようにすぐに改造できた。今後のモデルは、物理的なパッケージはちがったものになるだろう。

各ラックにはコネクタがついていて、そこにはリボンケーブルが2本ついて、となりのラックや、ソフトを動かす汎用PCと接続するようになっている。最後のラックは、次のラックがないので、「ターミネータ」（末端抵抗）がついている。信号がリボンケーブルの終端にきたとき、そこではねかえって信号をゆがませないようにするために、そういう抵抗をつけておくわけだ。

各基板は一秒で38億鍵を探索するので、基板12枚をさしたラックは、毎秒460億鍵を探索することになる。このスピードだと、鍵空間の半分を探索しつくすのには9日くらいかかることになる。このラック一つに基板をいっぱいにさせば、1998年2月にRSAの「DES-II」チャレンジを解決した全世界のコンピュータを上回る速度となる。このコンテストに参加した全世界のコンピュータ群は、ピーク時に秒速340億鍵をためしていた。

1-15

最初のDESクラッカーの非公式な目標としては、平均的なDES鍵を1週間以下でクラックすることだったので、基板は12枚以上必要ということになる。じゅうぶんに余裕をみて、基板を24枚使って、それをラック2つにおさめた。これで毎秒920億の鍵を探索してくれるので、鍵空間の半分を4.5日でカバーする。チップがラック一つに入れるには消費電力が大きすぎたり、発熱が大きすぎたりしたら*、基板24枚をラック3つにわければいい。

まず、探索ユニットを一回設計した。そしてそれを各チップごとに24回コピーして、さらにはそのチップを1,500個作っただけで、処理能力は36,000倍になった。これが「高度に並列処理可能（highly parallelizable)」ということだ。

予算

プロジェクト全体で予算は21万ドルほどだった。このうち8万ドルはDESクラッカーの設計、組み立て、テストにかかった労働コストである。残り13万はチップ、基板、その他基板のコンポーネント、基板のラック、電源、冷却装置、そしてPCなどの直接コストである。

DESクラッカーの制御用ソフトは別個にボランティアプロジェクトとしてかかれた。作業としては二三週間ほどかかっている。

プロジェクト全体は、全部で18ヶ月ほどで完成した。その時間の大半は、初期のリサーチに費やされたもので、カスタムチップではなくFPGAを使おうとしていた時間が多い。カスタムチップをつくるための契約は1997年8月にかわされた。プロジェクトがはじまって8ヶ月くらいたってからだ。チームは全部で10人以下、しかもフルタイムでこのプロジェクトに取り組んだ者は一人もいない。チームメンバーは、プロジェクトマネージャ、ソフトデザイナー、プログラマ、チップ設計者、基板設計者、ハード技術者、ハードマネージャから構成される。

_________________

* 刊行時点では、ここのチップはテストが終わっていたけれど、マシン全体はまだ作り終えていなかった。もしチップの消費電力か発熱が大きすぎて、チップ1500個を使ったマシンが無理なら、チップのクロックを40 MHz から、たとえば 30 MHz まで下げるという手もある。こうすれば熱と消費電力の問題は相当へる。ただしこの場合、探索時間は33%よけいにかかることになる（つまり平均で6日よけいにかかることになる）。

1-16

もし設計にもっとお金をかける気があれば、チップあたりのコストを下げたり、チップ密度を上げたり、探索速度を向上させることもできたはずだ。もっと複雑な設計にすれば、ほかの暗号アルゴリズムをクラックできるだけの柔軟性ももてただろう。ここでほんとうに大事な点というのは、どんな政府でも、ほとんどの企業でも、そして何万人もの個人ですら手が届くような予算で、使い物になるDESクラック用マシンがつくれた、ということだ。この設計を公開したことで、将来のマシンの設計コストはもっと下がるだろうし、半導体技術の進歩も、コスト低下に貢献するはずだ。5年もすれば、10代の子でも、高校の科学博覧会で自前のDESクラッカーがつくれるようになることは、じゅうぶんに考えられる。

ほかにはだれがDESをクラックしているだろう?

もし市民自由団体がDESクラッカーを20万ドルでつくれるなら、おそらく政府機関でも100万ドル以下で同じものをつくれるはずだ（いまのは冗談）。US National Security Agency の予算と使命を考えると、おそらくかれらは何年も前にDESクラッカーをつくりはじめているはずだ。われわれの見当では、おそらくそういうマシンの4世代目か5世代目にかかっているだろう。われわれのものよりかなり高速なチップも使っているはずだ。現在のプロセッサは300MHz以上で走る。われわれの40MHzチップの8倍以上のはやさだ。おそらくはスーツケースにおさまるような「野戦用」ユニットもあって、それでもDESを一日でクラックできるだろう。フォート・ミードの地下にはすさまじい中央ユニットがあって、ふつうのDES鍵をものの数秒でやぶり、しかも同時に独立に傍受したメッセージを何千も解読しているだろう。

もし基板5200枚上にチップ33.3万個を載せて使えば、DES鍵は30分くらいでみつかる。基板はおそらく、通信用にパラレルポート200くらいが必要だろう。IBM互換パソコンがそういう基板4枚を同時に相手にできるので、これはパソコン50台ということだ。必要なソフトはごく簡単になる。いちばん難しいのは、物理的な配置と修理の物資移動に関わる部分だ。これはわれわれがつくったものの200倍のハードとなる。そういうシステムの値段として、とんでもない上限値をあげるとすれば、われわれのプロジェクトコストを単純に200倍して、4000万ドルとなる。

もちろん、もしチップ30万個を使ってDESを30分でクラックするシステムを作る気なら、設計を白紙に戻して一からやりなおしたほうがいいだろう。もっと先進的なチップ製造プロセスを使うだろう。大量に発注すればこれは要求できる。初期デザインとソフトにももっとお金をかけて、全体システムをもっと安く単純にして、おそらくはもっと高密・高速・低消費電力チップを使って、それをボードにもっと高密に実装し、さらにプロセッサもオンボードにして、直接イーサネットにつながるようにするだろう。各チップのコストをがんばってもっと下げるだろう。これだけ数があるとそれが大きい。さらには複数のDES鍵を同時にクラックすることも考えるだろう。

1-17

大国ならどこでもDESクラック用マシンをすでに持っていると考えていいはずだ。本書の刊行で目をさました小国も、さらに一部の犯罪組織もDESクラッカーをつくるか買うかするはずだ。それは別に本書の目的ではない。われわれの意図としては、この諜報監視の標的や、機器のメーカ、さらには政策立案者など、暗号問題と取り組んでいる人々に情報と警告を与えることだ。

DESを使っていたらどうすればいいの？

シングルDESを使うような設計は、これからいっさいしないこと。

完全に固定されたシングルDES鍵を使うシステムは、すべて廃棄すること。あるいはそのトラヒックをさらにもう一段暗号化すること。もう一段の暗号化には、特別な配慮が必要となる。外のDES暗号をクラックするのに使われそうな、わかりやすいヘッダをさけなくてはならない。

ソフトとハードを換えて、だんだんDESより強い暗号アルゴリズムを使っていくようにしよう。

鍵3つのトリプルDESが無難な線だろう。同じブロックサイズを使うし、ハードも同じものが使えるかもしれない。単に、鍵を3つ使ってDESを3回かけるというだけだ（つまり各ブロックをまず最初の鍵で暗号化し、それをさらに2番目の鍵で暗号化し、そしてそれを3番目の鍵で暗号化する）。トリプルDESの強さについては、確実なことはなにもわかっていないけれど、シングルDESより弱くはないのは確実だし、おそらくかなり強いはずではある。ただしトリプルDESでも、「ごたまぜ」変種やモードには要注意。Eli Biham* とDavid Wagner⁺の研究によれば、これはふつうのトリプルDESにくらべてずっと弱いことがわかっていて、下手をするとシングルDESにすら劣るかもしれない。基本的なプリミティブとして、DESを3つ、 Electronic Code Book (ECB) モードで使うこと。そこからECB 3DESプリミティブを使うことで、Cipher Feedbackモードのようなモードを構築できる。

アメリカ政府は、DESを新方式と置き換えるための公式なプロセスを、遅々としつつも実施しているところだ。この試みは高度暗号規格（Advanced Encryption Standard, AEC）と呼ばれているが、最終的なアルゴリズムが決まるまでにはあと数年かかるし、それが実際の現場で、使い物になると証明され、世の暗号解析者たちの慎重な検討をうけて隠れた弱点がないか確認されるまでにはさらに何年もかかるだろう。もし、5年後か10年後に世に出る製品を設計しているなら、暗号化アルゴリズムとしてAESを考えてみてもいいかもしれない。

AESが遅々としている理由というのは、NSAが過去10年に、このプロセスを始めようとしたときにかならずそれをつぶしてきたからだ、と言われている。最近ではNSAは、SkipjackのようなNSA設計の機密になった暗号化アルゴリズムを技術コミュニティに使わせようとしたが、ユーザにそのアルゴリズムを公開検討する機会を与えなかったので失敗している。これが失敗したので、やっとNSAもNational Institute of Standards and TechnologyがAES標準化プロセスを開始するのを認めた。

_______________

* "Cryptanalysis of Triple-Modes of Operation", Eli Biham, Technion Computer Science Department Technical Report CS0885, 1996.

+"Cryptanalysis of some Recently Proposed Multiple Modes of Operation", David Wagner, University of California at Berkeley, http://www.cs.berkeley.edu/~daw/multmode-fse98.ps. 1998 Fast Software Encryption ワークショップで発表。

1-18

結論

データ暗号化規格（Data Encryption Standard, DES）は1975年以来、なかなか公共の役にたってきたことは事実だ。だがこれが設計されたのは、計算コストがすさまじく高くて、巨大コンピュータが専用の二重床の上に鎮座して、専用空調つきの屋内聖域にすえられていた時代である。いまやスーパーコンピュータがバックパックにおさまり、インターネットで何百万というマシンにアクセスできる時代だ。DESはもはや時代遅れなのだ。

Electronic Frontier Foundationは、本書が暗号に関わる政策論争にとって、真実の新しい水準をもたらしてくれることを期待している。われわれの社会にとって賢い選択をするためには、きちんとした情報に基づく選択をしなくてはならない。こうした論争においては、National Security Agency （NSA）と Federal Bureau of Investigation（FBI）の見解と経験がきわめて重視されてきた。政策立案者や市民が、かれらの発言の多くがどのくらい正確かをチェックしていないということを考えると、きわめて驚くべきことである* (市民はかれらの発言のほとんどについては、きくことさえできない。国家機密とされているからである）。暗号政策論争が、もっと成功した、一般に指示される政策に向かって移行することを期待したい。こうした機関がもっと正直になろうかと検討してくれたり、政策立案者たちが、かれらの裏付けのない発言を信じるのをやめたりしてくれれば、このプロセスはすぐにもそうした方向に向かえるのである。

_________________

* 政府機関の信頼性が疑問視されているのは、なにもDES クラッキングだけではない。たとえば、暗号によって政府機関が直面している問題が実際にはどのていどのものかという問題は、これまた公式にはとんでもない推定が出されているのに、もっと慎重でバイアスのない調査ではほとんど影響がないとされている。こうした政府機関の行いに関する合憲性についての見解がどこまで有効かについても、疑わしい面がある。これは司法省によって20年前にその見解が却下されているし、1997年には連邦地方裁判所で違憲判決がおりている。政府職員による非合法の盗聴と通信傍受の多発も、問題となっている。たとえばLos Angeles Timesの1998年4月26日記事 "Can the L.A. Criminal-Justice System Work Without Trust?" を見よ。

 レジスタ　      説明とコメント
 0x00-0x1F        PlaintextVector
 0x20-0x27        PlaintextXorMask
 0x28-0x2F        Ciphertext0
 0x30-0x37        Ciphertext1
 0x38             PlaintextByteMask
 0x39-0x3E        未使用 (reserved)
 0x3F             SearchInfo
 0x40-0x47        探索ユニット  0 キーカウンタ (0x40-0x46) とSearchStatus (0x47)
 0x48-0x4F        探索ユニット  1 キーカウンタ (0x48-0x4E) とSearchStatus (0x4F)
 0x50-0x57        探索ユニット  2 キーカウンタ (0x50-0x56) とSearchStatus (0x57)
 0x58-0x5F        探索ユニット  3 キーカウンタ (0x58-0x5E) とSearchStatus (0x5F)
 0x60-0x67        探索ユニット  4 キーカウンタ (0x60 0x66) とSearchStatus (0x67)
 0x68-0x6F        探索ユニット  5 キーカウンタ (0x68 0x6E) とSearchStatus (0x6F)
 0x70-0x77        探索ユニット  6 キーカウンタ (0x70-0x76) とSearchStatus (0x77)
 0x78-0x7F        探索ユニット  7 キーカウンタ (0x78-0x7E) とSearchStatus (0x7F)
 0x80-0x87        探索ユニット  8 キーカウンタ (0x80-0x86) とSearchStatus (0x87)
 0x88-0x8F        探索ユニット  9 キーカウンタ (0x88 0x8E) とSearchStatus (0x8F)
 0x90-0x97        探索ユニット 10 キーカウンタ (0x90-0x96) とSearchStatus (0x97)
 0x98-0x9F        探索ユニット 11 キーカウンタ (0x98-0x9E) とSearchStatus (0x9F)
 0xA0-0xA7        探索ユニット 12 キーカウンタ (0xA0-0xA6) とSearchStatus(0xA7)
 0xA8-0xAF        探索ユニット 13 キーカウンタ (0xA8-0xAE) とSearchStatus (0xAF)
 0xB0-0xB7        探索ユニット 14 キーカウンタ (0xB0 0xB6) とSearchStatus (0xB7)
 0xB8-0xBF        探索ユニット 15 キーカウンタ (0xB8-0xBE) とSearchStatus (0xBF)
 0xC0-0xC7        探索ユニット 16 キーカウンタ (0xC0-0xC6) とSearchStatus (0xC7)
 0xC8-0xCF        探索ユニット 17 キーカウンタ (0xC8-0xCE) とSearchStatus (0xCF)
 0xD0-0xD7        探索ユニット 18 キーカウンタ (0xD0-0xD6) とSearchStatus (0xD7)
 0xD8-0xDF        探索ユニット 19 キーカウンタ (0xD8-0xDE) とSearchStatus (0xDF)
 0xE0-0xE7        探索ユニット 20 キーカウンタ (0xE0-0xE6) とSearchStatus (0xE7)
 0xE8 0xEF        探索ユニット 21 キーカウンタ (0xE8-0xEE) とSearchStatus (0xEF)
 0xF0-0xF7        探索ユニット 22 キーカウンタ (0xF0-0xF6) とSearchStatus (0xF7)
 0xF8-0xFF        探索ユニット 23 キーカウンタ (0xF8-0xFE) とSearchStatus (0xFF)

     DATA <= DATAO when (RDB = '0' and ADDSEL2 = '0') else (others => 'Z' 

     DATA <= DATAO when (RDB = '0' and ADDSEL2 = '0' and CHIP_EN = '1')
                   else (others => 'Z');