Valid HTML 4.0! Originally from http://www.genpaku.org/crackdes/cracking-desj.html.

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

プロジェクト杉田玄白 正式参加作品。詳細は http://www.genpaku.org/ を参照のこと。


      Scan This Book!      

DESをクラック

暗号研究、

連邦機関は

盗聴政策と

こうして

チップ設計の

プライバシーを

秘密

侵害する



EFF
     ELECTRONIC FRONTIER FOUNDATION      

翻訳:山形浩生



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

Electronic Frontier Foundation
翻訳:山形浩生

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

第四章のテストファイル、ブートストラップ、ブートストラップ2の掲載物の著作権保有者は、©1997 by Network Associates, Inc. である。この掲載物は、全体、部分を問わず、使用料の支払いなしに複製が認められる。第10章「暗号分析ハードウェアのアーキテクチャ上の考察」は、著者Ian GoldbergとDavid Wagnerが著作権 © 1996 を保有する。著者たちとは iang@cs.berkeley.edudaw@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 マシンを使うことだ。ハイエンドでは、カスタムチップ方式に最新の改良を加えたものがあがっている。

しらみつぶし式の鍵探索は、こんなに人気がでるとは意外な問題だ。だれでもこの問題を考えてみれば、256の可能性を探索するのは、めんどうくさいけれど、できなくはないというのは自明だろう。わたしを含む多くの人たちが、なぜこの推定を精緻にして厳密にしようとがんばったのかもなぞだけれど、それよりさらに大きな謎は、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.htmlhttp://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著)は、ゲートアレイのカスタムチップと、それをのせるボードについて、ハード設計者の観点から説明している。

技術的な設計詳細

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

第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

概論

本章の内容:

解読の政治性

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

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

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

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

_______________

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

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暗号の強さについて誤解するようにしむけているのだと考える。その狙いは:

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

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/48)に限られてくる。

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

この助けを提供してくれるのが、暗号文の2つめのブロックだ。もし暗号文の最初のブロックで、結果のバイトがすべておもしろかったら、チップは今度は、同じ鍵で二番目の暗号文を復号してみる。これで「まちがい率」はさらに65536分の一になって、ソフトはたった16,777,216 (224または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/240)しかなくなる。つまり、探索ユニットは、おもしろそうな鍵を報告するまでに、平均で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つにわければいい。

Table 1-1: DES クラッカー性能のまとめ

デバイス

その下のデバイスあたりの数

鍵/秒

探索あたり平均所要日数

探索ユニット

24

2,500,000

166,800

チップ

64

60,000,000

6,950

基板

12

3,840,000,000

109

ラック

2

46,080,000,000

9.05

EFF DES クラッカー

92,160,000,000

4.524

まず、探索ユニットを一回設計した。そしてそれを各チップごとに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?" を見よ。


2

DES 鍵探索アレイのデザイン

本章の内容:

Cryptography Research
and
Advanced Wireless Technologies, Inc.

チップのレジスタ

各チップには、以下のレジスタがある。それぞれのアドレス指定については、Figure 2-1を参照。

Ciphertext0 (64 bits = 8 bytes)

探索される最初の暗号テキスト。Ciphertext0はチップ上のすべての探索ユニット共通であり、セットされるのは一回だけ(探索システムが最初に初期化されるとき)。

Ciphertext1 (64 bits = 8 bytes)

探索される2番目の暗号テキスト。Ciphertext1はチップ上のすべての探索ユニット共通であり、セットされるのは一回だけ(探索システムが最初に初期化されるとき)。

PlaintextByteMask (8 bits)

平文バイトのセレクタ。このレジスタのビットは、あるキーをつかって復号して出てきた平文のうち、無視するべきバイトを示す。このマスクは、平文の値の一部しかわかっていないときに便利だ。たとえば、最初の5バイトがなにかのヘッダでわかっていて、残りの3バイトがわからないときには、 PlaintextByteMask に 0x07 を入れればいい。

PlaintextXorMask (64 bits = 8 bytes)

このレジスタは、ciphertext0の復号結果とXORされれる。このレジスタはふつうはCBC mode IV のときにつかわれる。

2-1


2-2

Figure 2-1: レジスタのアドレッシング

 レジスタ       説明とコメント
 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)

PlaintextVector (256 bits = 8 bytes)

許される平文バイトの値を指定(PlaintextByteMaskでマスクされたものをのぞく)。どの平文テキストのバイト P[i=0..7]についてもP[i]ビットがセットされていなければ、その復号キーははねられる。PlaintextVectorチップ上のすべての探索ユニット共通であり、セットされるのは一回だけ(探索システムが最初に初期化されるとき)。

SearchInfo (8 bits)

SearchInfoのビットは、正しい平文同定機能がどういうふうに機能するかを示す。SearchInfoのビットはそれぞれ次のように定義される:


2-3

bit 0 = UseCBC

このビットがセットされていると、平文がチェックされる前に、Ciphertext0 が Ciphertext1を復号してできた平文にXORされる。このビットは、CBCモードの暗号文をチェックするときに使う。

bit 1 = ExtraXOR

このビットがセットされていると、復号結果の平文の右半分が、左半分にXORされてから平文チェックがおこなれれる。ExtraXOR と UseCBC は同時には使用できない。

bit 2 = ChipAllActive

これがクリアされていると、チップ上の探索ユニットのどれか(複数可)が止まっている(つまり SearchActiveがゼロになっている)。このレジスタの値は、すべての探索ユニットの SearchStatus バイトをANDして得ている。この値の逆が専用ピンに出ていて、チップがとまったときにLEDが点灯できるようにしてある。

bit 3 = BoardAllActive

このピンは、このチップと基板上でそれより奥にあるチップすべてのChipAllActive信号をANDしたもの。実装方法としては、n番目のチップがn+1番目のチップのBaordAllActive線を見て、それを自分のChipAllActive線とANDして、その結果をn-1番目のチップにわたしてBoardAllActiveの計算をさせる、というかたちで実装されている。これによって、基板上のどのチップがとまっているかを調べるときに、log2N個のチップをたたけばすむ。このときNは基板上のチップの数になる。もしBoardAllActiveEnableが1になっていなければ、BoardAllActiveはチップの内部状態にかかわらずBoardAllActiveInputピンと同じになる。

bit 4 = BoardAllActiveEnable

この値がゼロなら、BoardAllActiveはその基板上の探索ユニットがすべてアクティブかどうかにかかわらず、常に BoardAllActiveInput ピンと等しくなる。もしこのビットが1にセットされていれば、BoardAllActiveレジスタ(と出力)はチップの内部状態を反映した値が入力ピンとANDされてセットされる。

bits 5-7 = 未使用

キーカウンタ (56 bits)

いまチェックされている鍵の値。キーカウンタはしょっちゅう更新される(つまりテストされる鍵が変わるごとに更新)。各探索ユニットごとに、わりあてられるキーカウンタの値はちがう。探索ユニットが、マッチするものをみつけて止まった時点で、すでにキーカウンタは次の鍵にインクリメントされている。一致した鍵は、一つ前のものとなる。

SearchCommandAndStatus (8 bits)

SearchStatusのビットは、各探索ユニットの現在の状態を指名している。各探索ユニットごとに、別々のSearchStatusレジスタが割り当てられている。SearchStatus の美とは次のようにわりあてられる:


2-4

bit 0 = SearchActive

探索が現在とまっているかどうかを示す(0=停止、1=アクティブ)。コンピュータは、探索を始めるときにこのビットをセットして、マッチする候補鍵が見つかったらこれをクリアする。ホストコンピュータは定期的にこのビットの状態をチェックして、ゼロならキーを読み出して探索を再開させる。(SearchInfoレジスタのなかのChipAllActive と BoardAllActive も参照)。

bit 1 = CiphertextSelector

探索エンジンがチェックしているのが、Ciphertext0かCiphertext1かを示す(0=Ciphertext0, 1=Ciphertext1)。このビットがゼロなら、探索エンジンはCiphertext0を復号して、CiphertextSelectorを1にする(平文がチェックにパスすれば)か、あるいはキーカウンタをインクリメントする(もし平文がチェックにパスしない場合)。このビットが1なら、探索エンジンはCiphertext1を復号して、SearchActiveを0にする(平文がチェックにパスすれば)か、あるいはキーカウンタをインクリメントする(もし平文がチェックにパスしない場合)。

bits 2-7 = 未使用

コマンド

各探索ユニットを別々に指定できるように、それぞれはチップ上の位置とそのチップの基板上の位置、そして基板のidによって識別できる。基板IDはチップ外で解釈される。各チップは基板セレクトピンを持っていて、基板がセレクトされたらチップにわかるようになっている。チップIDのマッチングは各ASIC内で行われる。ASICのIDピンはチップのIDに配線されている。

コンピュータの発したすべてのコマンドは、バス経由で運ばれる。このバスには、基板ID/チップID/レジスタ・アドレス用に8ビット、データ用に8ビット、そしてその他制御用に何ビットかが使われている。

探索をするには、ホストコンピュータは探索ユニットをFigure 2-2に示したような形でプログラムする。(Nは探索ユニット総数で、これは0からN-1まで番号がわりふられており、それぞれが固有の基板ID/チップID/レジスタ・アドレスを持っている。)

探索ユニットのはたらき

各探索ユニットはDESエンジンを持っていて、キーカウンタの値を使ってL/Rの二つの32ビットレジスタにDESを行う。各探索ユニットは、Figure 2-3にくわしく書いたプロセスを実行して、決して止まる必要はない。もしレジスタがこのプロセスの途中で更新されたら、出力は無意味になる(これは問題にはならない。まちがった結果は統計的にみて、マッチしないのがほぼ確実だからだ)。


2-5

Figure 2-2: ホストコンピュータを使って探索アレイをプログラムするアルゴリズムの見本s

これはとても単純なアルゴリズムで、見本用のものでしかない。実際のソフトは、BoardAllActiveとChipAllActiveラインをつかって、もっとかしこい探索技法を使う。

Ciphertext0, Ciphertext1, PlaintextXorMask, PlaintextByteMask, PlaintextVector, SearchInfo を各チップにロードする。

For i = 0 upto N-1

鍵をロードしながら、探索ユニットiのSearchStatusを0にする。
探索ユニットiのキーカウンタを((256)(i) / N)にセットする。
探索ユニットiのSearchStatusを1にしてSearchActiveをエネーブルする。

EndFor

While 正しいキーがみつからないうちは:

For i = 0 upto N-1:
探索ユニット i の SearchStatus を読む。
SearchActive ビットをチェック。
If SearchActive が0なら:
ユニット i の KeyCounter を読む。
鍵の下32ビットから 1 を引く。
ローカルコンピュータで DES 操作をして鍵をチェック。鍵が正しければ探索おしまい。
さもなければ、SearchStatus の SearchActive ビットをたてて探索を再開。

EndIf

EndFor

EndWhile

見本プログラムの説明

ここでは、システムが通常のオペレーションでどうプログラムされるかを説明する。

Known ciphertext/plaintext (ECB, CBC, etc.)

完全な暗号文/平文ブロックがわかっていたら、このモードが使われる。これはほとんどのDESモード(ECB、CBC、カウンタなど)で使えるけれど、いずれの場合にも暗号文と平文の完全なペアが必要となる。

PlaintextVector

この探索では、わかっている平文のなかに、固有の平文バイトが8個(またはそれ以下)ある。PlaintextVectorでわかっているそれぞれのバイトに対応したビットが立てられ、それ以外はゼロとなる。


2-6

Figure 2-3: 探索ユニットのはたらき

1. もし CiphertextSelector=0 なら、 L/R = Ciphertext0にする。
もし CiphertextSelector が 1 なら L/R = Ciphertext1にする。

2. キーカウンタの鍵を使って L/R を復号し、候補となる平文をL/Rにつくる。

3. もし ExtraXOR = 1 なら、 L = L XOR Rにする。
もし CiphertextSelector = 0 なら

L/R = L/R XOR PlaintextXorMaskにする。

もし CiphertextSelector = 1 かつ UseCBC = 1 なら:

L/R = L/R XOR Ciphertext0にする。

4. If SearchActive = 1 AND (
(PlaintextByteMask[0x80] = 0 AND PlaintextVector[byte 0 of L] is 0) OR (PlaintextByteMask[0x40] = 0 AND PlaintextVector[byte 1 of L] is 0) OR (PlaintextByteMask[0x20] = 0 AND PlaintextVector[byte 2 of L] is 0) OR (PlaintextByteMask[0x10] = 0 AND PlaintextVector[byte 3 of L] is 0) OR (PlaintextByteMask[0x08] = 0 AND PlaintextVector[byte 0 of R] is 0) OR (PlaintextByteMask[0x04] = 0 AND PlaintextVector[byte 1 of R] is 0) OR (PlaintextByteMask[0x02] = 0 AND PlaintextVector[byte 2 of R] is 0) OR (PlaintextByteMask[0x01] = 0 AND PlaintextVector[byte 3 of R] is 0)) なら:

CiphertextSelector = 0にする。
キーカウンタをインクリメント。

そうでなければ:

もし CiphertextSelector = 1 なら SearchActive = 0にする。
CiphertextSelector = 1にする。

5. Step 1にもどる。

Ciphertext0

暗号文ブロックに等しい。

Ciphertext1

暗号文ブロックに等しい。

SearchInfo

UseCBC と ExtraXOR はどちらも 0

PlaintextByteMask

0x00 に設定(全バイトを使う)


2-7

PlaintextXorMask

Set to 0x0000000000000000.

平文バイトの順序はどうでもいいので、各暗号テキストのバイトには、可能なものが8通りある。つまり探索のチェック基準を満たす暗号文は 88 = 224 = 1.67億通りある。まちがった暗号文がチェックをとおり可能性は 224 / 264 なので、255 通りの鍵を探索する間に、もっともらしい鍵は平均で (255)( 224 / 264), つまり32768通り出てくることになって、これらはコントロールしているコンピュータが排除しなくてはならない。Ciphertext0 と Ciphertext1 は同じ内容にしてあるので、最初のテストをパスするもっともらしい結果は、すべて二番目のテストもパスすることになる。(これが速度に与えるペナルティは、ほとんどない。探索システムは、32768のもっともらしい鍵についてはDES操作を二回やることになるけれど、それ以外の正しくないキーについては一通りしかやらないからだ。)

ASCII テキスト (ECB or CBC)

ASCIIのみのアタックの場合には、最低でも2つのとなりあった暗号テキスト(全部で16バイト)が必要になる。

PlaintextVector

認められるASCII文字の入ったビットだけをたてる。通常のテキストの場合、これはふつうは256通りの文字のうち、55通りを含むものとなる(10=LF、13=CR, 32=空白、65-90=大文字, 97-122=小文字)。

Ciphertext0

最初の暗号テキスト。

Ciphertext1

二番目の暗号テキスト。

SearchInfo

UseCBC は ECBなら0にセットされ、暗号文がCBCを使ってつくられたものなら1にセットされる。ExtraXOR は 0にセット。

PlaintextByteMask

0x00にセット (全バイト使用).

PlaintextXorMask

ECBなら 0x0000000000000000 にセット、CBC なら IV(初期化ベクトル) にセット。

まちがった鍵によって復号された二つの(ランダムな)候補となる平文が、上で述べたASCII文字だけになる可能性は (55/256)16 だ。したがって探索では、コンピュータがはねるべきもっともらしい結果が平均で 255 (55/256)16 = 742358 通りあることになる。22万鍵に一つは、最初のチェックをパスして、二回目のDESが必要になる(こうした追加のDESの時間は無視できる)。もっともらしい結果がはねられるのを待つ時間も無視できる。もしコンピュータが各探索ユニットのSearchActiveフラグを一秒に一回ずつチェックするとしたら、もっともらしい結果一つあたりで、0.5探索ユニット秒が無駄になるだけ。つまり探索全体では、400万探索ユニット・時間がかかることになるが、そのなかの103探索ユニット時間が無駄になるだけだ。


2-8

CBCモードのプログラミングでは、 PlaintextXorMask は初期化ベクトル(あるいは攻撃している暗号文が最初のブロックでない場合には、前の暗号文)にセットしなくてはならない。

Matt Blaze式チャレンジ

目標は、すべての平文バイトが等しくて、すべての暗号文のバイトも等しいような場合を見つけることだ。

PlaintextVector

ビット0だけをセット。

Ciphertext0

すべてのバイトを等しくした固定値に。

Ciphertext1

Ciphertext0と同じ。

SearchInfo

UseCBC は0にセット。ExtraXOR は1にセット。

PlaintextByteMask

0x0Fにセット (左半分だけがチェックされる)

PlaintextXorMask

0x0000000000000000にセット。

平文のバイトがすべて等しければ、つまり右半分と左半分は等しくなる。このとき、 ExtraXOR ビットのステータスのために L=L XOR R となったら、Lは0になる。平文マスクは左半分だけを選び、 PlaintextVector で、それが0かどうか確認できる。

もっともらしいケースは、L=Rのときに起こる。これは232に一つの鍵で起こるわけだ。この探索は256通りためして終わるという保証はないので、平均時間は256になる (255ではない)。もっともらしいケースの数は 256 / 232 = 224 = 1.68 億通りとなる。したがって各探索ユニットは、平均で 232 鍵ごとにもっともらしいものにあたる。つまりは30分に一回ずつくらい、ということだ。各探索ユニットを1秒に1回調べるとすると、アイドリング状態になるのは (0.5)(16.8 million)/3600 = 2333 探索ユニット時間(これでも全体の1%以下)。ホストコンピュータは、1.68億通り(平均)のDES操作をやらなくてはならいが、かなり下手なDES実装でも、数分あればこれは可能だ。


2-9

スケーラビリティと性能

このアーキテクチャは、DES鍵を平均で10日以下で見つけるように意図されている。Figure 2-4に最初の実装の性能を示す。ハードをふやせば、もっと高速な結果は簡単に得られる。ハードの量を増やせば結果を出すのに必要な時間は半分になる。キー探索ASICの基板は簡単に足したり減らしたりできるような設計になっていて、システムを大規模にも小規模にもできる。大規模システムはコストはかかるが、結果はもっとはやくわかる。またシステムが大きくなると、電源と冷却も強力なものが必要となる。

Figure 2-4: 推定性能

ASIC総数 1536
ASICあたりの探索ユニット 24
探索ユニット総数 36864
クロック速度 (Hz) 4.00E+07
キーあたり必要クロック(平均) 16
探索ユニットあたり毎秒処理DES鍵数 2.50E+06
システム全体での毎秒処理DES鍵 9.22E+10

探索サイズ(最悪ケース) 7.21E+16
結果が出るまでの必要秒数(最悪ケース) 7.82E+05
結果が出るまでの必要日数(最悪ケース) 9.05

探索サイズ(平均) 3.60E+16
結果が出るまでの必要秒数(平均) 3.91E+05
結果が出るまでの必要日数(平均) 4.52


ホストコンピュータのソフト

Cryptography Research が以下のソフトを書く予定。

シミュレーション

Cryptography Research は、チップデザインがファブリケーションに送られる前にチップをテストするための、テストベクトル生成ソフトを書く。このソフトはチップ上のあらゆる機能をテストし、あらゆるオペレーションのモードをチェックする。このプログラムは、簡単なコマンドライン・インターフェースを持つ。

ホストコンピュータ

ホストコンピュータ用のソフトウェアは、平文がわかっている場合の鍵派遣、暗号化されたASCII文の解読(ECBとCBCモード)、Matt Blaze式チャレンジ解決をする通常の探索タスクを実装する。このソフトはプラットホーム固有の I/O コードをのぞけば、ふつうの ANSI C でかかれる。


2-10

ホストプログラムにはまたテストモードも持つ。これは探索ユニットに、すぐ止まるのがわかっているようなタスク(たとえばほんの数百万鍵を探せばすむようなタスク)をロードしてみて、出てきた結果を確認してどこか異常はないかを検出する。(ソフトには、探索の途中で不良探索ユニットをバイパスする機能がついている)。通常以外の探索をしたいユーザは、カスタム関数を付け加えて、候補として出てきたキーが本当に正しいかがチェックできるようにしたうえで、コードをコンパイルしなおすこと。

このプログラムの最初のバージョンは、単純なコマンドライン式のインターフェースを持ち、DOS用に書かれる。Linuxへの移植もされるが、最初の目標完成日には間に合わないかもしれない。(プラットホームに依存するコードというのは、I/O部分だけなので、まともなコンパイラがあればどんなプラットホームへも簡単に移植できるはずだ)。ソフトプログラムは、プロジェクト参加者 (AWT, EFF, and Cryptography Research) を明示する。

Cryptography Research はまた、もっときれいなインターフェースを持ったバージョンをつくる。これは、デモをもっとかっこよくできるようにするためのモノだ(プラットホームは未定)。

ソフトとソースコードはすべてパブリックドメインにおかれる。

用語集

基板ID

各基板ごとに与えられる、固有の8ビットid。これは基板上のdipスイッチでセットする。ホストコンピュータはチップをアクセスするのに、チップIDと基板IDを使う。

CBC モード

DESモードの一つ。最初の平文ブロックが、初期化ベクトル(IV)とXORされ、その後の平文ブロックは、その前の暗号文とXORされる。

チップID

ホストコンピュータが、基板上のどのチップをアクセスするか指定するときに使う値。

暗号文

暗号化されたデータ。

Ciphertext0

攻撃する暗号文のうち最初のもの。

Ciphertext1

攻撃する暗号文のうち2番目のもの。

_________________

必要なら、ANSI C 以前のものもサポート可能。GUIコードはおそらくすべてC++で書かれるはず。


2-11

CiphertextSelector

現在攻撃されている暗号文を選ぶためのレジスタ。各DESエンジンは、あるキーが見込みありそうだと判断するときに、暗号文を2つテストして両方とも見込みある結果が出ていることを確認するので、このセレクタが必要になる。

DES

データ暗号化規格(The Data Encryption Standard)

ExtraXOR

復号結果の右半分と左半分をXORをする追加操作を探索ユニットにさせるためのレジスタ。Matt BlazeのDES問題の解決をサポートできるように追加された。

ホストコンピュータ

DES探索アレイをコントロールするコンピュータ。

キーカウンタ

各探索ユニットにはキーカウンタ・レジスタがあって、現在チェック中の鍵がおさめられている。このレジスタはそれぞれ7バイトあり、56ビットの鍵がおさまるようになっている。

平文(Plaintext)

暗号文に対応した、暗号化されていないデータ。

PlaintextByteMask

8ビットのレジスタで、平文のバイトにマスクをかけるために使う。平文で、値のわかっていないバイトをマスクしておいたり、わかってはいてもPlaintextVectorに記述できるほど明確ではない場合に使う。

PlaintextVector

256-bit のレジスタで、見込みある平文でどのバイト値があり得るかを指定するためのもの。ホストコンピュータは、PlaintextVectorのまともな数のビットがセットされているのを自分で確認する必要がある。セットされているビットが多すぎれば、DESの探索が止まる回数が多くなりすぎる。

PlaintextXorMask

Ciphertext0 を復号した結果にXORされる64-bit レジスタ。ふつうは、このマスクは0sw、CBCモードのときには初期化ベクトル(IV)にセットされる。

SearchActive

各探索ユニット上のビットで、現在探索を行っているか、それとも候補鍵を見つけて止まっているかを示す。止まった探索ユニットを再開するには、止まらない鍵をロードして、このビットをリセットする。

SearchInfo

DESの結果をどのように事後処理するかについて、各種の情報を入れておくレジスタ。さらに、チップ上または基板上の探索ユニットがどれか止まったかどうかも示す。


2-12

UseCBC

SearchInfo の中のビットで、探索エンジンが復号後にCBCモードの事後処理を行うように指示する(つまりciphertext1の復号結果をciphertext0とXORしてplaintext1をつくるようにする)。


3

DES 鍵探索アレイの設計:チップレベルの仕様

本章の内容:


Advanced Wireless Technologies, Inc.
and
Cryptography Research

ASIC の説明

Select1

Cipher text 1 を選ぶ

C0

Cipher text 0

C1

Cipher text 1

Search

探索がアクティブ

K

Mask

平文ビットマスクとDES出力

Match=0

「探索ユニットの仕組み」のStep 4で指定された平文ベクトルのビット位置すべてにゼロが入る(第二章参照)

CBC & Extra XOR

「探索ユニットの仕組み」のStep 3で指定された操作を行う。(第二章参照)

3-1


3-2

探索ユニットの動きのフローチャート
Figure 3-1. 探索ユニットの動きのフローチャート

鍵に必要な最大のビット数を決めるために:

K= log2(最大組み合わせ数/チップ数)

= log2(256/(24 cpc * 64 cpb * 24 基板) = log2(1. 95E12) = 42 ビット

32ビットカウンタを使う場合には、これは以下の間隔でオーバーフローすることになる:

232 * 16 cycles * 25ns = 1. 72 * 1012ns = 1720 sec = 28. 7 minutes


3-3

探索ユニットの状態ダイヤグラム
Figure 3-2 探索ユニットの状態ダイヤグラム

基板の説明

コンピュータはパラレルカード経由でASICとインターフェースする。パラレルカードにはポートが3つあり、以下のように割り当てられている:

Port A: アドレス(7:0)
Port B: データ(7:0)
Port C: 制御信号 8 本

基板とASICのルーティングリソースを減らすために、アドレス線は多重化してある。ASIC上のレジスタをアクセスするためには、ソフトはアドレスを3回ラッチする必要がある。基板-ID(7:0), チップ-ID(6:0) 最後にレジスタアドレスである。


3-4

探索ユニットのブロックダイヤグラム
Figure 3-3: 探索ユニットのブロックダイヤグラム

基板上にスイッチを持つことで、設計が柔軟で拡張しやすいものになる。各基板には、固有の基板 ID があって、これがスイッチで設定できるようになっている。たとえば16進で 5F の基板 ID を持つ基板は、基板 ID スイッチを以下のように設定することなる:


3-5

リード/ライトのタイミング

リード/ライトのタイミング

タイミング

3-6

タイミング
tas1 10 ns Min Board-ID and Chip-ID Address setup

tas2 10 ns Min Write Register-Address setup

tas3 10 ns Min Read Register-Address setup

tah1 10 ns Min Board-ID and Chip-ID Address invalid (hold)

tah2 10 ns Min Write strobe trailing edge to Address invalid (hold)

tav 10 ns Min ALE valid

tds 10 ns Min Data valid to Write strobe goes low (setup)

tch 10 ns Min Chip select hold

tdh 10 ns Min Write strobe goes high to data invalid (Data hold)

trv 10 ns Min Read strobe duration

tdv 100 ns Max Read strobe goes low to data valid

tdh 100 ns Max Read strobe goes high to data invalid (Data hold)


3-7

アドレス指定用レジスタ

アドレスバスのダイヤグラム
Figure 3-4 アドレスバスのダイヤグラム

All-active 信号

この信号がlowなら、探索ユニットのどれか(複数可)がとまったことになる。この値は、SearchActive ビットをすべてANDして得られる結果である。ASICごとにANDゲートを一つおいて、それをカスケード接続している。

All Activeのカスケード

3-8

ASIC レジスタわりあて

全探索ユニットに共通するレジスタ

0x00-0x1f PlaintextVector
0x20-0x27 PlaintextXorMask
0x28-0x2f CipherText0
0x30-0x37 CipherText1
0x38 PlaintextByteMask
0x39-0x3e 予約済み
0x3f SearchInfo

探索ユニットのその他レジスタ

0x40-0x47 探索ユニット 0: キーカウンタ (最初の 7 バイト) と Search Status
0x48-0x4f 探索ユニット 1: キーカウンタ (最初の 7 バイト) と Search Status
. . .
0xf8-0xff 探索ユニット 23: キーカウンタ (最初の 7 バイト) と Search Status

必要なレジスタ数:

共通レジスタ 58 + 8 * n レジスタ; n = ASIC内の探索ユニットの総数。この倍には n = 24 なので、 58 + 192 = 250 レジスタが必要となる。


3-9

レジスタ
Note: 指定のないピンは接続なし
CNTRL0 = ALE = ADDSEL1

CNTRL1 = CSB = ADDSEL2


4

ソースコードのスキャン

本章の内容:

この先の何章かは、DESクラッカーの設計のためにわれわれが書いたドキュメントを、特別な書式で掲載している。これらのドキュメントは、ばか力方式暗号解析研究におけるわれわれの主要なソースであり、ほかの研究者はわれわれの研究結果を再現したり追試したりするためにこれが必要となる。

暗号ソースコードの政治性

われわれは暗号の科学の急速な進歩に関心があるし、さらには市民にたいして暗号技術のメリットや危険性について啓蒙することにも関心がある。したがって、できればこうした情報をすべてWorld Wide Webに載せたいと思っていた。そうすれば、暗号の勉強をしたいと思う世界中の人が、だれでもすぐにアクセスできるようになる。

残念ながら、著者たちの住んで働いている国では、暗号に関する政策は何十年にもわたる秘密主義と隠密統制のもとで形成されてきている。強力な政府機関が業務のために盗聴を利用している――そして業務以外の、自分の権力を温存するための目的でも。こうした機関が、議会や政府の重要機関を操ってきた。かれらは議会を説得して、研究者――われわれのような――が自分の研究成果を公開する自由を制限するような、憲法違反の法律を可決させてしまった。(議会に憲法違反をするよう説得するのは、ネコにキイキイいう缶切りの音を聞いて(エサがもらえると思って)寄ってくるように説得するのとおなじくらい簡単なことが多いのだけれど、だからといってそういう機関がそういうまねをしていいということにはならない。)商務省や国務省、法務省などに圧力をかけて、こうした違憲な法律を支持するようにさせて職務上の宣誓を破らせただけでなく、その抑圧的な検閲方式の窓口にさせて、違憲な規制をつくらせ、ふつうの研究者やソフト作者を弾圧するようにさせている。

4-1


4-2

これに関与している主要政府機関は、National Security Agencyであるが、ここ数年はFBIもリクルートされたらしい。外側にいるわれわれとしては、この機関たちが、政府のほかの部分にたいしてどんな圧力をかけているのか、推測するしかない。FBIは、違法な盗聴をながいことつづけているし、盗聴のあとは、その情報を脅迫(議員や大統領に対する脅迫も含め)に使っている。FBI のスポークスマンは、それが「むかしのわるいFBI」の話であって、J. エドガー・フーヴァーが死んで、ニクソン大統領が失脚してからはもうそういうのは一掃された、と言う。でもこうした機関は、ふつうの市民がかれらの活動を調べようとすると、あらゆる手を使ってこれを妨害する。Freedom of Information 法を使って、かれらがやっていることをはっきり知ろうとすると、協力を拒否するわけだ。

とにかく、こうした機関は法や規制に影響を与えて、アメリカの暗号研究家たちがその結果をWorld Wide Web (あるいはそれ以外の電子的な形)で公開するのを非合法にしてしまった。

紙の出版物は例外

暗号学者のなかには、アメリカ政府に対する訴訟をおこした人たちもいる。暗号の輸出を禁止する法律のために、自分たちの研究成果が検閲されてしまっているからだ。 (Electronic Frontier Foundation は、こうした訴訟の一つ Bernstein v. Department of Justice, et al を資金援助している)*。 こうした慣行を、裁判で検討してもらうことの結果の一つとして、かつて存在していたきわめてあくどいやり口が使われなくなってきた、ということがある。

たとえば、1970年代から1980年代初期にかけて、ある種の科学論文を刊行したり、それを図書館においたりした研究者にたいして、NSAは刑事訴訟をちらつかせて脅しをかけている。また、協力しようという人々に対しては「自主的」検閲方式も用意していた。でも訴えられると、政府としては、こうした本や論文などを検閲し続ければ、輸出制限での法廷闘争においてとても不利になることを理解したわけだ。

判事は、本ならわかる。政府が人々にたいして、本を書いたり頒布したり販売したりするのを禁止するというのは、なにか怪しげなことが行われているのだ、というのも、判事たちは理解できる。政府は、インターネットやフロッピーディスク、ファックスや電話といった派手な現代技術についてなら、判事数人の目をくらませることはできるだろう。でも、この自由な国で、紙にインクをのせただけでだれかを牢屋にぶちこんだり、処罰したりするというのが憲法にてらして正しいかどうか、という点については、ごまかされる判事はいないだろう。

_________________

* http://www.eff.org/pub/Privacy/ITAR_export/Bernstein_case/を見よ。


4-3

したがって、暗号の輸出禁止に関する最新の重要なアップデート(1996)では、こうした輸出規制は、情報を本(あるいはそれ以外のあらゆる形式の紙)として出版することに対しては適用されないことが明記されることになった。政府機関のほうは、いずれ本も規制の対象にする「かもしれない」――おそらくは、いまの法廷闘争すべてに勝ったら、ということだろう――と煮え切らないことを言ってはいる。でもそれまではアメリカ合州国憲法の修正第一条がまだ本に対しては適用されているので、われわれは本の形でなら、どんな暗号に関する情報を出版するのも自由である。たとえば、いまごらんになっている本書のような。

したがって、暗号研究はこれまで紙ベースで発表されてきたけれど、今後も紙での発表が続くトレンドを見せている。ほかの科学研究は急速にオンライン化されつつあるのだが。

Electronic Frontier Foundation はこれまで、情報のほとんどを電子的に公開してきた。定期的な電子ニュースレターを出し、メンバーや一般市民とのやりとりもほとんどが電子メールと電話で、市民の権利と責任についての電子保存情報をの膨大な資料庫をつくりあげてきた。これは世界中から、すぐにWebやFTP経由でアクセスできるようになっている。

この本も、おなじ形式で出版したいと思ったけれど、でもまだそれは不可能だ。このためには、われわれの法廷闘争で、研究に対する検閲を認める法律が却下されなくてはならない。アメリカでは、暗号ソフトが入った本とまったくおなじ情報を電子的に公開すると、深刻な非合法行為となってしまう。それを個人的に、友だちや同僚に教えるだけでも、それが電子的に行われる場合でその相手がアメリカに住んでいない場合には、政府に非合法であるとされてしまう。

アメリカ商務省は、暗号ソフトのある外国のロケーションへのリンクを含んだWorld Wide Web ページを公開しても、それは「輸出監督規制(Export Administration Regulations, EAR)の対象となる輸出にはならない」と公式に発表している。* これはわれわれにも納得がいく――ちょっと「極論にまで誇張」reductio ad absurdum 式の思考実験をしてみれば、リンク禁止が実質的に意味を持つためには、外国の Universal Resource Locatorsを表示すること自体を禁止しなくてはならないことがわかる。URL というのはただの文字が並んでいるだけだ。たとえば http://www.eff.orgのように。アメリカの法廷が、どこか情報がみつかる場所の名前を挙げるだけの行為を禁止するようなことは、おそらくあり得ないだろう。

したがって、Electronic Frontier Foundation は自由な国でこの本の電子的なコピーが存在するところへのリンクを公開するのは自由である。もしそうした本書の電子バージョンが海外にあることがわかれば、それに対するリンクを http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/のページで公開する。

___________________

* これは、 http://samsara.law.cwru.edu/comp_law/jvd/pdj-bxa-gjs070397.htmに含まれている。これは、Peter Junger教授の暗号輸出制限規制に対する修正第一条訴訟の一部である。


スキャン

この本を印刷するときには、Pretty Good Privacy, Inc のツールを使った。(同社は後に、Network Associates, Incに統合された。) PGPは、ソースコードをスキャンし、さらにスキャン用にソースコードを印刷するための、なかなかすぐれたツール群をつくっている。本書で公開しているドキュメントを扱ういちばん簡単な方法は、かれらのツールと、スキャン上の指示を利用することだ。

PGP は、もちろんこうしたツールを本の形で公開している。 "Tools for Publishing Source Code via OCR", by Colin Plumb, Mark H. Weaver, and Philip R. Zimmermann, ISBN # 1-891064-02-9 だ。この本は1997年に発行されて、 Printers Inc. Bookstore, 301 Castro St, Mountain View, California 94041 USA; phone +1650 961 8500; http://www.pibooks.comが販売している。

OCRツール本におさめられたツールや指示は、PGPの本だけでなく、インターネット上でも入手できる。 http://www.pgpi.com/project/, で、「proof-reading utilities」(校正用ユーティリティ)を見てほしい。ページが移動したり、構成が変わったりしてこれではうまくいかない場合には、International PGP ページ http://www.pgpi.comからさがしていってほしい。

PGP のツールは、行ごととページごとにチェックサムを出してくれるし、ふつうは目に見えない、tabや複数の空白といった文字もはっきりわかるようにしてある。このツールを入手したら、その本にある説明文を読むか、あるいはオンラインで配布されているREADMEファイルを読むことを強く推奨する。本書などのようなプログラムリストをスキャンして構成するための、とても詳しい指示が書いてある。本書でこの先に書いた指示は、それをごくごく簡略化したものだ。

このプログラムリストを電子化する手順は2つある。まず最初に、ページの画像をスキャンすること、そしてその画像を、ページ上のテキストに近いものに変換することだ。さいしょの部分は機械的なスキャナで行われる。二番目の部分は、光学式文字認識(Optical Character Recognition, OCR) プログラムで行う。ちかくの「コピー屋」などで、スキャナとOCRソフトがついているコンピュータを借りられることもある。

ソースをスキャンするときには、まずOCRソフトを「訓練」してやろう。まず、以下のテストファイルのページやプログラムの一部をスキャンして、OCRがそれぞれのテキストをどう判断するかをいろいろ手直ししてやればいい。これをどうやるかは、使うOCRソフトにもよる。でも、われわれの使っているそれぞれの文字や記号の形についてきちんと識別できるように教え込んでおけば、その後のページをスキャンして修正するときの手間はずっと省けるようになる。

プログラムリストには、独特な文字がいくつか使われている。OCRソフトに、それぞれつぎのように変換しろと教えておこう。


4-5

右向き三角形(タブとして使用):通貨記号(バイト値は8進で244)

小さなまん中の三角形「ドット」(複数スペースとして使用):ナカグロ (バイト値は8進で 267)

フォームフィード:円記号(バイト値は8進で 245)

大きな黒い四角形(行が続くことを示す): pilcrow または paragraph symbol (バイト値は8進で266).

ページのスキャンとOCR処理がすんだら、それをPGPのツールにかけて、まちがいをみつけて訂正すれば、きれいなオンラインのコピーをつくれる。

ブートストラップ

Philip R. Zimmermann と Network Associates の好意により、PGP OCRツールをもっていない人たちを支援するために、ここにPGPのbootstrapとbootstrap2ページを載せておこう。(「ブートストラップ」ということばは、「自分のブーツのひもをもって自分を引っ張り上げる」という話から出ている。つまり、外からの助けを借りずに自分を起動する、という意味で使われている)まともなかたちで以下のページをスキャンしてOCRにかければ、この本とPerlさえあれば、修正済みのファイルを抽出できる。ただしこれは、PGPツールを使ったときよりも手作業が増える。

さいしょのブートストラッププログラムは、そこそこ読みやすいPerlのコードが1ページほどだ。このページをできるだけ慎重にスキャンすること。校正は手作業でやらなくてはならない。OCRから出てきた結果をファイルに保存して、手でチェックサムを取り除いてやれば、Perlスクリプトとして実行できるようになる。そうしたら、このPerlスクリプトを、OCR結果(チェックサムつきのもの)を引数にして実行しよう。もし手作業の校正がうまくいっていれば、きちんと実行されて、自分自身のきれいなコピーが「bootstrap」というファイルになってできるはずだ。(ほかにそういうファイル名のファイルがないことを事前に確認しておくこと)。もし校正がちゃんとしていなければ、Perlスクリプトは途中で死ぬので、印刷されたものと比べて、見逃したところがないか確かめることになる。

ブートストラップのスクリプトを実行すると、入力ファイルの行ごとにチェックサムを調べる。チェックサムがあわない行があるごとに、スクリプトはエディタをたちあげて停止する。(エディタは環境変数EDITORで指定しておく)。エディタで問題の行をなおそう。エディタをとじると、またスクリプトの実行が再開する。

ブートストラップのスクリプトが、自分自身をきれいに再現してくれたら、bootstrap2のページをスキャンしてOCRにかけて、それをこのbootsrtapにかけてやろう。同じように一行ずつ校正していって、bootstrapスクリプトが文句をいわないようになるまでつづける。これでbootstrap2がきれいに再現できるはずだ。

bootstrap2 スクリプトを使って、この本の残りの部分をスキャンしよう。はたらきはbootstrapスクリプトと似ているけれど、ページチェックサムも使うので、もっとまちがいをたくさん発見できる。これも、自分でまちがいをなおしてはくれないけれど、手動でまちがいをなおせるようにエディタをたちあげてくれる。(自動エラー訂正がほしければ、PGPの本やツールを入手すること。)


4-6

この本にある、スキャン可能なプログラムリストは、すべてパブリック・ドメインに属している。テストファイル、ブートストラップ、ブートストラップ2は著作権があるが、(著作権保持者の)Network Associatesはそれを自由に複製していいと認めているので、著者たちはあなたがこのプログラムリストを友だちにコピーしてあげたり、なにかに採録したり、スキャンしたり、出版したり、製品で使ったりすることについて、一切の制限をつけていない。しかしながら、もしあなたが自由でない国に住んでいる場合には、こうした情報を入手してからそれを使ってなにができるかについては、制限がかけられているかもしれない。これについては、現地の思考警察に確認すること。


pp. 4-7 to 4-14 はまだ準備中:内容は、テストファイルが6ページ、ブートストラップが1ページ、ブートストラップ2が1ページ。 [Note: ブートストラップの1と2は、OCRツールのなかにも含まれている。ツールは以下から入手可能。 http://www.pgpi.com/project/]


5

ソフトのソースコード

 この章は、DESクラッカーのハードウェアを制御するためにわれわれが書いた、C言語によるソフトのプログラムリストがすべて掲載されている。ソフトには簡単なユーザインターフェースがついていて、ハードをテストし、可能な鍵を探索して解決すべき問題を設定し、探索を実装できるようになっている。これを公開することで、人とマシンの両方に、DESクラッカーをどう制御するかを示すわけだ。

 このバージョンのソフトは、ごくごく基本的なものでしかない。グラフィカル・ユーザ・インターフェースもないし、ばか力式の探索を高速化するために、インターネット上でほかのマシンと協力する、などということもできない。本書をお読みになるころには、おそらくもっとすぐれたバージョンのソフトができているはずだ。これについてはわれわれのウェブページ、http://www.eff.org/pub/Privacy/Crypto_misc/DES_Cracking/に説明があるはずだ。

 このソフトは、Windows95の「DOS窓」で、Borland C++ V3.1を使ってビルドしてうごくことが確認されている。また、Microsoft Visual C++バージョン5でもきれいにコンパイルできる。

 ソフトについての説明は、付属のreadme.txtファイルを参照。

 この文書がなぜこういう印刷のされかたになっていて、それをどうやってコンピュータにスキャンすればいいのかについては、第4章「ソースコードのスキャン」を参照。

(ソースコードの実物はftp://ftp.nic.surfnet.nl/surfnet/net-security/encryption/cracking_DES/で入手可能。)


6

チップのソースコード

 この章には、われわれの書いたチップデザイン言語(VHLD)文書の完全なリストが掲載されている。われわれのDESクラッカー上のカスタム・ゲートアレイチップをどう設計したか、人々とマシンに知ってもらうためである。

 今日では、テキストファイルでふつうの文書を書くだけで、完全なチップが設計できる。これは、特別なハードウェアプログラミング言語VHDLで書かれている。この言語はチップシミュレーションソフトが理解できるようになっていて、このシミュレーションソフトは、ふつうのプログラミング言語のインタープリタのように機能する。設計者がその設計で満足したら、このVHDLプログラムのテキストは「チップコンパイラ」に読み込まれる。このコンパイラは、バイナリのプログラムをつくるのではなく、チップのローレベル設計情報を出力する。

 チップのコンパイルプロセスは、ふつうのバイナリソフトのコンパイルよりも、ずっと細かいところに気をつかう必要がある。たとえば、現代のコンピュータでは、バイナリプログラムがメモリ上のどこに置かれても、あまり関係はない。どこにあってもプログラムはだいたいおなじ動きを示す。チップを作る際には、チップの構成ブロックを「レイアウト」して「ルーティング」するのに、人間が手をくわえたり、工夫をしたりしなくてはならない。そうしないと結果が高性能、低消費電力、ローコストなどの望ましい性質を持たなくなってしまう。どのくらい細かく手を入れるかは、チップを作る(ファブリケートする)ときに使うテクノロジーや機材にも大きく左右されてくる。ただし、設計文書はこういうのとはまったく独立になっている。

 したがって、ここにあげた設計だけでは、話の全貌とはなっていない。これさえあれば、ボタン一押しでチップが出てきます、というようにはなっていない。でも、われわれの設計を理解するためには役にたつ。有効な入力の組み合わせでチップがなにをするか、ということを、人間に読める形で厳密に定義しているのがこのドキュメントだからだ。

 この文書がなぜこういう印刷のされかたになっていて、それをどうやってコンピュータにスキャンすればいいのかについては、第4章「ソースコードのスキャン」を参照。

(ソースコードの実物はftp://ftp.nic.surfnet.nl/surfnet/net-security/encryption/cracking_DES/で入手可能。)


7

チップシミュレータのソースコード

 この章には、カスタムDESクラッカーチップの動きをシミュレートするC言語のソフトが掲載されている。このソフトは、人にチップの働きを見せるのに便利だし、チップがきちんと製造されたかをマシンに確認してもらうためのテストベクトルの生成にも使える。

 このシミュレータは、チップの設計に先立って書いた。いろいろな設計上のアイデアを試してみるためである。このシミュレータは、実際のチップとまったくおなじ結果を出力するはずだ。速度よりは記述の明快さと、新しいアイデアを試すときの柔軟性を重視した書き方になっている。チップの働きが理解できなければ、このソフトをふつうのPCかUnixマシンでビルドしてみて、いろいろ実験してみるといい。Borland C++ 3.1 など、ふつうのCコンパイラでコンパイルできるはずだ。

 物理的なチップをつくるプロセスは、エラーがたくさん発生する可能性がある。それぞれのチップは、ほこりや、あるいはシリコン材料の欠陥のために問題が発生するかもしれない。だからあるチップが機能するかどうかは、実際に試してみる以外には確かめる方法がない。したがって、チップ製造業者は、チップを設計したらいっしょにテストベクトルも提供するように要求してくる。テストベクトルは、チップの各入力ピンに加える電圧と、チップ試験器が時間に応じてそれをどう変化させるべきかを一覧にしたものだ。ベクトルには、チップ試験器がその入力電圧ごとに、出力ピンからどんな出力を得るはずか、というのも一覧にしてある。もしチップ試験器が、すべての入力信号を順にチップにくわえて、その出力が対応するはずの出力信号と完全に一致していたら、このチップはテストに「合格」したことになる。もし出力信号のどれかが仕様とちがっていたら、チップは試験に「不合格」となって廃棄される。

 こうしたテストにパスしただけでは、そのチップがきちんと製造されたという証明にはならない。チップが、設計者の提供した少数の試験データをきちんと処理できる、ということを示すだけだ。チップのあらゆる部分をテストするようなテストベクトルを創り出すというのは、ほとんど芸術といっていい技能だ。チップのテストのコストは、テストのサイズに比例するので、テストはふつうはみじかくてとてもストレートなものになっている。したがって、チップの働きを理解しているかどうか確認するために、このテストベクトルを小さな例として使うことができる。

 この文書がなぜこういう印刷のされかたになっていて、それをどうやってコンピュータにスキャンすればいいのかについては、第4章「ソースコードのスキャン」を参照。

(ソースコードの実物はftp://ftp.nic.surfnet.nl/surfnet/net-security/encryption/cracking_DES/で入手可能。)


8

ハードウェア基板の回路

本章の内容:

この章では、DESクラッカー用にわれわれが設計してつくったプリント基板のダイヤグラムを掲載する。また、その他ハードウェアに関する細かい記述もある。

各ハードウェア基板は、DESクラッカーチップ64個をそなえている。この回路では、チップのうち8つがどう接続されているかを示してある。残りの部分もほとんど同じような回路となる。各「All Active Out」ピンは、つぎの「All Active In」ピンにデイジーチェーンされる。各チップの「Chip ID」ピンは、GNDか電源に直接つながっていて、チップごとに、基板上のバイナリチップ番号を示すようになっている。掲載されている8つのピンについて、この番号がどうなっているかを調べれば、どういうふうにそれが変化しているかがわかる。

基板は、ラックにさしてあって、このラックを通じ各基板とホストコンピュータは50線のリボンケーブルで結ばれる。ラックはSun-4/470サーバ用のラックを改造したものとなっている。バックプレーンにどのような改造をしたかは、この章の後半に記述してある。

基板の回路

回路はつぎのページから始まる。[註:読みやすくするために、スキャンでは回路図は150%拡大してある。]

8-1


8-2

回路図


8-3

回路図


8-4

回路図


8-5

回路図

8-6

回路図


8-7

回路図


8-8

回路図


8-9

回路図


8-10

Sun-4/470 バックプレーンの改造

さいしょのDESクラッカーは、Sun-4/470サーバからリサイクルしたシャーシをいくつか使っている。各シャーシはカード用ラックと電源、ファン、カバーでできている。ラック部分にはバックプレーンがある。これは、ラックに挿入する基板をさしこむコネクタがついた、プリント基板である。各列には、1番から12番まで番号のついたコネクタが並んでいる。ラックは"9U" VMEバス基板用のサイズとなっており、それぞれに大きな96ピンコネクタが3つついている。したがって、バックプレーンにも96ピンコネクタがそれぞれのボートごとに3つずつついていて、P1, P2, P3 と名前がついている。この96ピンコネクタはそれぞれ、32ピンが3列並ぶ形になっていて、それぞれの列はA, B, Cと呼ばれている。

このバックプレーンを以下のように改造した:

てっぺんの列 (P1): 変更なし。基板からコネクタへの信号をそのまま使う。

まん中の列 (P2): 変更なし。この列は、ただのカードの保持用に使っている。基板からこのコネクタへは信号がきていない。

いちばん下の列 (P3): DESクラッカー基板用の電源と信号。割り当ては以下の通り:

Table 8-1: いちばん下のコネクタへの信号割り当て

A列 もとの割り当て信号 新しい割り当て
Pin 1 to 25 +5 Volts DES クラッカーチップ用の電源供給
Pin 26 to 27 +12 Volts 未使用
Pins 28 to 29 -12 Volts 未使用
Pins 30 to 32 -5 Volts 未使用

B列

もとの割り当て信号 新しい割り当て
Pin 1 予約 未使用
Pin 2 予約 未使用
Pin 3 予約 Reset (C_RST)
Pin 4 予約 Read Strobe (C_RDB)
Pin 5 予約 Write Strobe (C_WRB)
Pin 6 予約 Address Latch Enable (C_AEN)
Pin 7 予約 Control_1 (C_CNT1) or C_ADRSELB
Pin 8 予約 Control_2 (C_CNT2) or C_CSB
Pin 9 予約 Data 7 (C_D7)
Pin 10 予約 Data 6 (C_D6)
Pin 11 予約 Data 5 (C_D5)
Pin 12 予約 Data 4 (C_D4)
Pin 13 予約 Data 3 (C_D3)
Pin 14 予約 Data 2 (C_D2)
Pin 15 予約 Data 1 (C_D1)


8-1

Table 8-1: いちばん下のコネクタへの信号割り当て (continued)

Pin 16 予約 Data 0 (C_D0)
Pin 17 予約 Address 7 (C_A7)
Pin 18 予約 Address 6 (C_A6)
Pin 19 予約 Address 5 (C_A5)
Pin 20 予約 Address 4 (C_A4)
Pin 21 予約 Address 3 (C_A3)
Pin 22 予約 Address 2 (C_A2)
Pin 23 予約 Address 1 (C_A1)
Pin 24 予約 Address 0 (C_A0)
Pin 25 予約 GND
Pin 26 予約 GND
Pin 27 予約 GND
Pin 28 予約 GND
Pin 29 予約 GND
Pin 30 予約 GND
Pin 31 予約 全インターフェースIC用の+5 V 供給
Pin 32 予約 全インターフェースIC用の+5 V 供給

C列

もとの割り当て信号 新しい割り当て
Pins 1 to 25 GND GND
Pins 26 to 27 +12 Volts 未使用
Pins 28 to 29 -12 Volts 未使用
Pins 30 to 32 -5 Volts 未使用

A列の pins 1-25 は、DESクラッカーチップの電源を供給している。これは通常は+5 ボルトだ。

チップをもっとひくい電圧で駆動して、電力消費と発熱をおさえることもできる。この時には、ボルトのちがう二種類の電源が必要になる。DESクラッカーチップ用のひくい電圧は、A列のpins 1-25に供給する。インターフェース回路用の +5 ボルトはB列の pins 31 と 32 に供給する。低電圧でうごかすときには、DES基板のジャンパ JP1 を取り除くこと。DESチップが +5 ボルトを使っている場合、B列の31-32ピンには外部電源はつながず、DES基板のジャンパJP1もつないだままにしておく。

P3 バス (いちばん下の列)の物理的な改造

バックプレーンのP3 バス (いちばん下の列)にはスロットが12個ある。スロットの一部は隣のスロットと接続されて、バスになっている。もとのSunの仕様では、P3バスはおもにCPU基板とメモリ基板との間の高速メモリバスとして使われていた。そして、4つの独立したグループに分割されている。

グループ 1

このグループにはスロットが7つある(番号1から7)。B列がいっしょに接続されてバスになっている。


8-12

グループ 2

これはスロット8のみ。このB列は、ほかのスロットとは接続されていない。

グループ 3

これはスロット9のみ。このB列は、ほかのスロットとは接続されていない。

グループ 4

このグループにはスロットが3つある(番号10から12)。B列がいっしょに接続されてバスになっている。

バックプレーンを改造して、これらの4グループがすべて相互につながるようにした。これでP3のB列はすべてのスロットがバックプレーンで結ばれることになった。

スロット 1 とスロット 12 には、二列ヘッダをP3コネクタのB列とC列につけた(信号とGND用)。そしてそこから50ピンのリボンケーブルをバスにつなげるようにした。このヘッダを使って、各シャーシがつぎのシャーシに接続できて、またさいしょのシャーシを汎用コンピュータにつなぐこともできる。この汎用コンピュータで、DESクラッカーを制御するソフトが走るわけだ。

スロット 11 にもA列とB列に二列式ヘッダをつけて、スロット12にリボンケーブルがついていないときに、ターミネーション用の抵抗をつけられるようにした。これでバス上の信号の信頼性が保護される。

PC インターフェース

さいしょのシャーシは、リボンケーブルで制御用のコンピュータと接続されている。リボンケーブルは、スロット1の二列ヘッダにつながる。このケーブルは、PC側ではプラグイン式のハードウェアカードにつながり、このカードがパラレルI/Oポートを3つ提供している。ソフトはこのカードとやりとりをして、リボンケーブルにコマンドを書かせたり、あるいはリボンケーブルから結果を読み込んだりさせる。ソフトはふつうのIBM互換PCで動き、ほかの汎用コンピュータにも移植できる。

われわれのプロジェクトでは、以下のインターフェースカードのどちらかを使っている。いずれもテキサス州オースチンのNational Instruments Corporation の製品で、連絡先は http://www.natinst.com または +1 512 794 0100 である。かれらの PC-AT バスインターフェースカードはPC-DIO-24 で、注文番号は777368-01である。ラップトップ用にはPC カード (PCMCIA) インターフェースもある。DAQCard-DIO-24 で、注文番号は 776912-01である。このカードはPSH27-SOF-D1ケーブルが必要で、この注文番号は 776989-01。

24ビットI/Oのある他のパラレルインターフェースカードでも使うようにできる。


8-13

正誤表

このページには、ここに公開したハードウェアやソフトについて、その後見つかったまちがいについて記述してある。

読み込みのためのチップ選択

DES クラッカーチップは、データバッファをきちんとトライステートにしない。どこかの基板のチップが読み込みをしていると、その他のDESクラッカーチップはデータピンにゴミを出力してしまう。バッファのエネーブルは、Board EnableとChip Enable信号を確認していなかった。これを回避するために初期のハード基板は改良されて、チップごとに個別RDB信号を供給し、それをFPGAで外部からエネーブルするようにした。これをきちんと修正するためには、チップVHLDのtop.vhdの最後近くを修正することだ。以下の部分:

     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');

同時に、CHIP_EN を upi.vhdの出力として追加する。


pp. 9-1 to 9-5

9

百万DES鍵を破る:Yvo Desmedt著

この部分は、禁無断複製なので、別ファイルにしておく。

http://www.genpaku.org/crackdes/des9.html


pp. 10-1 to 10-26

10

暗号解析ハードウェアのアーキテクチャ考察

Ian Goldberg and David Wagner

[iang,daw]@cs.berkeley.edu

http://www.cs.berkeley.edu/~iang/isaac/hardware/main.html (HTML)

http://www.cs.berkeley.edu/~iang/isaac/hardware/paper.ps (Postscript)


11

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

本章の内容:

1997年6月にRocke Verserの率いるグループがRSA Data Security社の DES challengeを、多数のコンピュータによるしらみつぶし式鍵探索方式で解決した。これはDESの歴史的な瞬間である。この結果が有用なのは、それがDESがどれほど弱くなったかを、公開された形で実証することができたからだ。でも一方で、これはDESを攻撃するのに大規模な分散型の攻撃以上の手はないというまちがった印象を与えるおそれがある。DESの設計は、ソフトで攻撃するにはかなり時間がかかるが、ハードで実装すればコンパクトで高速になるようになっている。これはDESだけでなく、ブロック式暗号(block cypher)やハッシュ関数攻撃、楕円曲線暗号システムへの攻撃のほとんどすべてにあてはまる。ハードウェアを使った効率的な攻撃に対抗するには、じゅうぶんに鍵のながいアルゴリズムを使う必要がある。たとえば、トリプルDES 128-bit RC5,* CAST-128+などだ。

この論文では、ハードウェア手法を使ったDES鍵探索のコストを推定し、またDESへの攻撃をかわすための手段として提案されているいくつかの手法について、その有効性を検討する。

_______________________

Michael J. Wiener, Entrust Technologies, 750 Heron Road, Suite E08, Ottawa, Ontario, Canada K1V 1A7

この論文はRSA Laboratoriesの1997年秋Cryptobytes newsletterに掲載された。著者とRSA Data Security, Inc.の許可を得て掲載している。

* R. Rivest, "The RC5 Encryption Algorithm", Fast Software Encryption--Lecture Notes in Computer Science (1008), pp. 86-96. Springer, 1995.

+ C. Adams, "Constructing Symmetric Ciphers Using the CAST Design Procedure", Designs, Codes and Cryptography, vol. 12, no. 3, pp. 283-316, Nov. 1997. また、"The CAST-128 Encryption Algorithm", RFC 2144, May 1997.としても入手可能。

11-1


11-2

技術の進歩

DESを攻撃する方法として知られているもののうち、いちばんいいのは56ビットの鍵をすべて試していって、正しいのが見つかるまでつづける、という方法だ。平均では、鍵空間の半分くらいを試せば正しい鍵が見つかることになる。1993年に、しらみつぶし方式のDES鍵探索マシンの設計が、詳細なチップ設計を含めて公開された。* このマシンの100万ドル版は、鍵探索チップを57600個使っていて、そのチップそれぞれが、毎秒5000万鍵をテストできる。全体としてこのマシンは、DES鍵を平均で3.5時間で見つけることができる。

この設計が完了して4年半がたった。そしてムーアの法則によれば、この間に処理速度は倍の倍の倍になったはずだ。もちろん、このような形で推測を行うのは、かつての設計で採用した慎重な分析と設計努力に比べれば、あまりよいやりかたとはいえない。もとのチップ設計は0.8 ミクロン CMOS プロセスで行われており、現在使える密度からいえば、同じシリコン面積にかつての設計を4個分つめこむことが可能になる。1993年の推測での控えめな推定という方針を踏襲して、探索チップの速度は、もとの50MHzから75MHzまでしかあがらないと想定している。このため、現在版のチップは、同じコストで6倍の速度となる。おもしろいことに、このチップを21個使えば、DES challengeを解決したチームの使ったコンピュータすべてに匹敵するだけの探索パワーが得られることになる。

現代版の100万ドルマシンは、DES鍵を平均で35分ほどで見つけることができる(3.5時間の1/6)。この時間は、以下の表に示すように、かけた金額と線形に比例する。

鍵探索マシンコスト 期待探索時間

$10,000    

2.5 日

$100,000    

6 時間

$1,000,000    

35 分

$10,000,000    

3.5 分

なお、表中のコストは、チップや基板の設計コストは含んでいない。こうした最初の一回だけのコストは、50万ドルはすると思われるため、多数のマシンを複数の顧客用につくるのでない限り、100万ドル以下のマシンをつくろうとするのは、無駄が多いことになる(訳注:要するに、チップ数の少ない10万ドルのマシンを1台つくろうとしても、チップの設計に50万ドルかかるならあまりコスト削減にはならないということ。)

この鍵探索エンジンは、DESの標準電子コードブック(ECB)モードを使った平文・暗号文対が与えられているときに、DES鍵を回復するように設計されている。しかし、このっマシンは変更を加えなくても、以下のモードも扱える:暗号ブロック連鎖(cipher-block chaining, CBC)、64ビット暗号フィードバック(cipher feedback, CFB)、64ビット出力フィードバック(output feedback, OFB)。

_____________________

* 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) に再録。現在は以下で入手可能: ftp://ripem.msu.edu/pub/crypt/docs/des-keysearch.ps


11-3

OFB の場合、連続した平文が2つ必要になる。チップ設計を変更すれば、よく使われるDESのモードをほかに2つ(1 ビットと 8 ビット CFB)扱えるようになるが、コストは多少高くなる。100万ドルで買えるチップが少なくなるので、すべてのモードでの探索時間は平均40分にまであがる。ただし 1 ビット CFB の場合は、これが平均で80分になる。

プログラマブル・ハードウェア

チップ設計に必要なコストは、小者の攻撃者やホビイストにとっては、大きな障壁となる。初期投資がずっと少なくてすむ代替案としては、プログラマブル・ハードウェアを使うことだ。こうしたテクノロジーの一種としては、現場プログラミング可能ゲートアレイ(Field Programmable Gate Array, FPGA) がある。PC上で回路を設計して、それをFPGAの載った基板にダウンロードして実行させればいい。1996年初期の報告では、FPGA 5万ドル分あれば、DES鍵を平均で4ヶ月で回復できると推定されている。これはチップ設計を行った場合に比べればずいぶん遅いけれど、資金の乏しい者にはずっと手が出しやすい。

別の有望なプログラマブル・ハードウェアは、複合プログラマブル・論理デバイス(Complex Programmable Logic Device, CPLD) である。CPLD はFPGAよりは設計の自由度が低いが、その分、値段も低い。鍵探索は、その性格上、CPLDにむいていると思われる。CPLDがDES鍵探索に使えるかどうかを評価するには、さらなる研究が必要となる。

既知の平文を避ける

以上で説明してきた設計は、攻撃者がなんらかの平文を知っているものという想定に依存している。ふつうは、8バイトのブロックが一つあれば十分だ。攻撃をさけるための手法として提案されているものとしては、既知の平文をすべて避ける、というものがある。これはなかなかむずかしいだろう。データは、固定ヘッダではじまることが多いからだ。たとえばMicrosoft Wordのすべてのバージョンでは、作成したファイルの先頭には固定バイト長の文字列がついてくる。

また既知の平文が完全にはわかっていない場合でも、キー探索の設計をわかっている部分にあわせて変えることができる。仮に、平文についてある程度の情報がわかっているとしよう(たとえば、ASCII文字コーディングが使われている、とする)。でも、テキストの全文はわかっていない。そうしたら、わかっている平文を何度も暗号化して結果を暗号文と比較するかわりに、暗号文のほうを何度も復号してみて、でてきた平文の候補をこちらの期待と比較してみればいい。たとえば期待されるのが7ビットのASCIIの平文なら、正しい形式を持った平文を与えてくれる鍵は256個に1つしかない。この鍵を別の暗号文ブロックに試してみる必要がある。これを扱うための論理回路は、鍵探索チップのコストを10-20%ほど増やすだけだ。

_____________________

* M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M. Wiener, "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security", 現在は以下で入手可能: http://www.bsa.org/policy/encryption/cryptographers.html


平文ブロックの中に、同じビットが1カ所繰り返し出てくるのがわかっただけでも、可能な鍵の数は半減する。こうしたブロックが56個あれば、正しい鍵を一意的に同定することができる。しかしこれでも、実行時間が平文のわかっているときに比べて56倍になるということではない。追加の論理回路のコストを考慮すれば、100万ドルのマシンでの実行時間は、この場合には2時間になる。

ひんぱんに鍵を変える

鍵探索攻撃をかわすためによく提案されるのが、DES鍵をしょっちゅう変えることだ。ここでの想定では、暗号化された情報は鍵が変更されたあとではもう役に立たない、ということだが、これはあまり適切な想定ではない場合が多い。もしDES鍵を見つけるのに35分かかるなら、鍵を5分ごとに変えたらどうなるだろう?この理屈の問題点は、鍵を見つけるのにかかる時間は正確に35分というわけではない、ということだ。実際にかかる時間は、0分から70分の間に均等に分布している。運がよければ、鍵はすぐに見つかるし、運が悪ければ、70分近くかかってしまう。攻撃者が、鍵の変わる5分以内に鍵を見つける確率は 5/70 = 1/14 だ。もし鍵が変わるごとに攻撃者があきらめてつぎの鍵探しをはじめたら、鍵が14回変更されるうちに(つまりは70分以内に)成功するものと期待できる。一般に、ひんぱんな鍵の変更は、攻撃者にとって期待実行時間を2倍ほどにするだけであり、単純にもっとながい鍵をもった強力な暗号を使うのに比べれば、代案としては大いに劣っている。

結論

現在の技術を使うと、コスト100万ドルのカスタムデザインのマシンを使えば、DES鍵は35分で回復できる。チップを設計してこうしたマシンをつくるだけのリソースがない攻撃者の場合にも、FPGAやCPLDなどのプログラム可能なハードウェアを使えば、PCやワークステーション上のソフトでやるよりもDES鍵空間をずっと高速に探索できる。鍵探索攻撃をかわすために、既知の平文を避けたり、鍵をひんぱんに変えたりしても、ほとんど役にはたたない。いちばんいいのは、トリプルDES、128ビットRC5、CAST-128 +など、もっとながい鍵をもった強力な暗号アルゴリズムを使うことである。

_____________________

+ 訳注:"The CAST-256 Encryption Algorithm", RFC 2612, June 1999. (CAST-128は過去の暗号になりつつあるので、延命措置として256bit。だそうな。山根信二氏のご教示に感謝。)


12

著者紹介

本章の内容:

The Electronic Frontier Foundation

Electronic Frontier Foundation
1550 Bryant Street, Suite 725
San Francisco CA 94103 USA
+1 415 436 9333 (voice)
+1 415 436 9993 (fax)
http://www.eff.org
info@eff.org

The Electronic Frontier Foundation (EFF) は、非営利の公益組織で、オンラインの権利を保護し、自由を推進している。1990年にミッチェル・ケイパー、ジョン・ペリー・バーロウ、ジョン・ギルモアが創設した。

EFFは、個人や組織、企業や政府にたいして、コンピュータと通信技術が世界を既存の法的社会的マトリックスから大きく変えてしまうときに生じる問題について、教育しようとしている。

EFFは、暗号政策について長年にわたり活動を展開してきた。「クリッパーチップ」とそれに続く「キーエスクロウ」提案の採用を止めるにあたっては大きな役割を果たし、小細工のない、解読不可能な暗号技術の広範な流通と使用を推進している。EFF は、Daniel Bernstein教授がアメリカの暗号に対する輸出法規制をひっくり返そうとする訴訟を支援している。教授は、アメリカ合州国憲法の修正第一条が、自分の暗号研究の成果を自由に発表する権利を保護しており、いちいち政府の許可を得たりする必要はないはずだ、と主張している。この初の公表されたDESクラッカーを作成し、その技術的な詳細を公開するという研究活動は、暗号技術の社会的・技術的ない意義について一般市民に理解してもらい、啓蒙しようというEFFの努力の一環だ。

12-1


12-2

EFF は、みなさんに、社会が今日の急速な技術的変化にいちばんいい形で対応するにはどうしたらいいかをわれわれと検討してほしいと願っている。EFFの会員になろう。詳しくは、以下を参照:http://www.eff.org/join/

John Gilmore

John Gilmore は、起業家で市民リバータリアンである。かれは初期のSun Microsystems 社員であり、Cygnus Solutions, the Electronic Frontier Foundation, the Cypherpunks, インターネットの "alt" ニュースグループの共同創始者である。コンピュータ産業では25年にわたる経験を持ち、プログラミング、ハード/ソフトの研究、マネジメントなどを経験。世界のオープンソース(フリーソフト)開発に、大きな貢献をしている。かれの暗号政策支援は、オープンな社会におけるプライバシーとアカウンタビリティにとっての本質的な技術である暗号技術について、一般の理解を深めることを目標としている。現在はMoniker pty ltd, Internet Society, Electronic Frontier Foundationの顧問委員である。

John はEFF の暗号政策に関する動きを指導しており、DESクラッカーの製作をマネジメントして、本書の文章のかなりの部分を執筆している。

Johnに連絡をとりたい場合には、以下のメールアドレスへどうぞ: gnu@des.toad.com; またホームページは: http://www.cygnus.com/~gnu/

Cryptography Research

Cryptography Research
870 Market Street, Suite 1088
San Francisco, CA 94102 USA
+1 415 397 0123 (voice)
+1 415 397 0127 (fax)
http://www.cryptography.com

Cryptography Research はPaul Kocherのコンサルティング会社で、サンフランシスコにある。 Cryptography Research は、多くの大企業や新興企業にたいしてコンサルティング、デザイン、教育、分析サービスを提供している。Kocher と同社はその技術的な仕事と研究で広く知られている。たとえば世界的な暗号プロトコル(SSL 3.0など)の開発や、暗号分析(たとえばRSAなどの暗号システムに対する時間計測攻撃の発見など)、そして大規模会議での無数のプレゼンテーションなど。Cryptography Researchへの連絡は、以下へメールでどうぞ。 info@cryptography.com


12-3

Cryptography Research は、DESクラッカーのハードとソフトの設計をマネジメントし、チップシミュレータとドライバソフトを書いた。

Paul Kocher, Josh Jaffe をはじめとする Cryptography Research の全員は、このユニークなプロジェクトに出資してきれたJohn Gilmore と EFF に感謝したい。そして AWTもそのすばらしいハードウェア作業を感謝!

Paul Kocher

Paul Kocher は暗号研究家であり、暗号をつかった高セキュリティシステムの作成に関する現実的な技能を専門としている。現在はCryptography Research (http://www.cryptography.com) の社長と、ValiCert (http://www.valicert.com)の主任科学者を兼任。 Paulは無数のソフトやハードプロジェクトに参加してきており、多数の暗号システムを設計、実装、解読してきた。Paulへの連絡は電子メールで以下までどうぞ: paul@cryptography.com.

Advanced Wireless Technologies

Advanced Wireless Technologies, Inc.
3375 Scott Blvd, Suite 410
Santa Clara, CA 95054 USA
+1 408 727 5780 (voice)
+1 408 727 8842 (fax)
http://www.awti.com

Advanced Wireless Technologies, Inc. (AWT) は、ハイテク企業にたいしてアプリケーション専用IC (ASIC) と基板レベルのソリューションを、最高の品質で最低の価格で提供している。AWTの設計哲学は、製品開発コスト/リスクと、関連コストを下げることである。AWTは、システムアーキテクチャからシステムインテグレーションと試験まで、一貫した設計フローを採用している。

AWT は1993年に創業された。エンジニアリングチームは、技能のすぐれたフルタイムの職員と、技術マネジメントスタッフで構成されている。社員は知識豊富でやる気も高く、有能で、システムエンジニアリング、チップ設計、完全なサブシステム設計の経験が3年から25年ある。

AWT は、顧客の個別ニーズにあわせたデジタルASIC/ゲートアレイと基板設計サービスを提供している。仕様の決定から、設計の実装、プロトタイプのテストまで、あらゆる開発フェーズでの参加が可能。

またエンジニアリングサービスにとどまらず、AWTは通信産業で使われる、先進的な製品を開発してきている。AWTの代表的な製品としては、変調復元、フォワードエラー訂正や暗号の複合などの分野における IP Core、 ASICs, 基板レベルの製品などがある。


12-4

AWT は、カスタムASIC、ロジックボード、インターフェースアダプタなど、DESクラッカーのハードを設計・製作した。DESクラッカーユニットの購入に興味があれば、AWTまでご一報を。

エンジニアリングのニーズがあれば、以下のwebサイト http://www.awti.com を見るか、あるいは +1 408 727 5780 まで電話で連絡いただければ幸甚。


Note: URLs for other parts welcomed


Scan and HTML by JYA/Urban Deadline

Valid HTML 4.0! Errata to: jy@jya.com
翻訳上のまちがいなどについては:hiyori13@alum.mit.eduまでご一報を。
Typoなどを多数指摘してくださった武井 伸光氏<tak@Polytype.cc.kochi-u.ac.jp>、およびミスや用語について教えてくれた山根信二氏<s-yamane@vacia.is.tohoku.ac.jp>に感謝!