本ドキュメントはSoftwareDesign2003年11月号の原稿を元にHTMLドキュメント化したものです。


CRYPTO2003 レポート

すずきひろのぶ
hironobu @ h2np.net

2003年8月17日 --- 21日まで米国サンタバーバラで開催された暗号学会CRYPTO2003の レポートをお届けします。

CRYPTO2003とは

国際暗号学会IACRが毎年8月に米国で開催している暗号学のカンファレンスで す。研究者しか集まらないので参加者は400名〜500名ぐらいですが、暗号学で は最もレベルの高いカンファレンスなので、暗号の教科書に載っているような 著名な研究者や、もっともホットな研究をしている人達が集まる場所となって います。発表論文のレベルはまちがいなく世界で最もレベルが高いカンファレ ンスです。

毎年8月University California Santa Bararaのキャンパスを使って開催され ます。アメリカの大学で8月というとちょうど卒業と入学の端境期です。キャ ンパス内の寄宿舎が参加者の宿になり、まるで合宿のような雰囲気になります。

スケジュール

スケジュールは次のようになっていました。

     8/17 日曜日     17:00 --- 20:00        レジストレーション開始
                     17:30 --- 21:30        夜のレセプション
     8/18 月曜日     8:50  --- 17:00        論文発表・招待講演
                     19:00 --- 22:00        レセプション
     8/19 火曜日      9:00 --- 12:25        論文発表
                     14:00 --- 17:00        BOF / 自由時間
                     18:30 --- 22:00        ビュッフェ  (アルコールは23:00まで)
                     19:00 --- 終るまで     ランプセッション

     8/20 水曜日      9:00 --- 17:00        論文発表・招待講演
                     17:00 --- 17:50        IACR年次総会
                     18:00 --- 20:30        ビーチバーバキュー
                     20:00 --- 22:30        お茶会 (Crypto Cafe)
     8/21 木曜日      9:00 --- 12:30        論文発表

今年のプログラム構成

CRYPTO2003のプログラムの特徴は、一番最初のセッションにインパクトの強い 「今年の目玉」的な論文発表があります。今年は、最終日の最後セッションに わかりやすくて一般ウケする内容を持ってきいました。「途中で帰ると面白い 所は聞けないぞ」的なプログラム構成です。

面白い内容だと思うのですが、残念ながら、このインターネット時代において もあまり一般に広く知られることはありません。コンピュータ関連の情報は、 今やWeb情報発信型のジャーナリズムにシフトしていますが、ここで情報発信 しているインターネット・ジャーナリストとか呼ばれる人達のレベルは、プレ ス発表やすでにある情報を右から左に流すレベルなので、この手の学術レベル の内容を噛み砕けないのです。

すべての内容を紹介するにはあまりにも紙面が少なすぎるので、また、全部解 説していくと大変な思いをすることになるので、面白いと思う所をかい摘んで 取り上げましょう。

RSA暗号を解読する機械

CRYPTO2003のトップバッターはこの発表で、かなりのインパクトがあります。 RSAは大きな2つの素数を掛け合わせた数は因数分解が困難であることを前提に、 安全性が保たれていますが、その因数分解をする高速に行うハードウェアの発 表です。

Factoring Large Numbers with the TWIRL
Adi Shamir and Eran Tromer

現在、Number Field Sieve (数体ふるい法)という計算アルゴリズムがもっと も高速な因数分解方法です。実際に530-bit長のRSA暗号は解読できます。しか し1024-bit長ともなると、現実にはまだ解読できません。たぶん現在のCPUの 構造では、現実的な時間で因数分解するのは難しいと考えられます。

よく量子コンピュータができれば解読できるという言葉を目にしますが、これ は真空管計算機の時代に、超VLSI技術をつかった(今日のような)CPUをのぞ むのと同じようなもので、量子コンピュータに至るには何度も革新的な技術の ブレークスルーが必要です。

今日の技術の延長線上にある現実的なアイデアとして1999年にTWINKLEという 光デバイスを用いた因数分解ハードウェアが提案されました。それでも光デバ イスなので乗り越えなければいけない壁が大きく、まあ、理論上は可能だけど ね、というレベルです。

今回提案されたTWIRLは、現在の半導体プロセス技術だけで十分作成可能なも のです。このTWIRLチップが1GHzで計算し、194 個が並列に動作できるならば、 このハードウェアを使い1024-bit長のRSA暗号を1年以内に解読できるとこの論 文では述べています。

ハードウェアの構造の説明を見ると、パラレルに計算するタイミングが非常に クリティカルで、かなり難しいハードウェアに思えますが、努力すると解決で きるレベルに思えます。それに書き換え可能なVLSIであるFPGAの性能がどんど ん向上する今日では、FPGAを使いTWIRLで使うチップを作るのは、筆者が思う よりも意外と簡単になるかも知れません。NSA辺りが作っていても不思議では ないようなハードウェアで、結構、ドッキっとさせられる内容です。

ストリーム暗号の高速な解読

次の論文は、LFSR(Linear Feedback Shift Register: リニアフィードバック シフトレジスタ)を用いたストリーム暗号は安全ではないことを示したもので す。

Fast Algebraic Attacks on Stream Ciphers with Linear Feedback
Nicolas T. Courtois

これはLFSRを使ったストリーム暗号はとてもではないが、まともな暗号として は使えないということです。この論文の爼上にあげられたのはE0 (Bluetooth の仕様に入っている)、LILI-128、Toyocryptでした。この3 つの安全性の低さ は、どれもドングリの背比べで、はっきりいってぜんぜんダメです。どうやら 東洋通信機(株)のWebページには英文で「日本ではCRYPTRECの第二段階まで 進んでいる」と以前は書いてあったらしく、発表者は「日本の政府はこんなも のを採用する所だった」(もちろん事実ではない)と煽っていました。

LFSRというのは高速な乱数生成に使われる手法でデジタル通信などをやってい る符号屋さんには馴染の手法です。しかしながら、統計的に偏りのない数列を 生成することと、暗号で使うための予測が困難な結果を出力することとは、まっ たくコンセプトが違うことなのです。符号理論系や数学系からやってきて、暗 号学に日が浅い人は、よく、このコンセプトの違いが理解できずに「自称安全 な暗号」を作っているのを見かけます。

筆者は以前より安全評価の済んだブロック暗号に適切なモードを加え、出力列 を生成し安全なストリームを作ろうという主張をしています。この方法と比較 して、さらに高速で同等に安全なストリーム暗号というものは直観的にも、現 在までの暗号分析理論の進展展開をみてもありえないと筆者は思うのです。な ぜならば、プリミティブな計算レベルで高速であるということは、どこかで計 算を端折っているわけで、その分、複雑性がどこかで犠牲になっているはずだ と思うからです。歴史をみても無線LANのWEPで使われているRC4、携帯電話で 使われているGSM、Bluetoothで使われているE0などのストリーム暗号のどれも 既に安全ではないという検証がなされています。ストリーム暗号という幻想を 追うのはやめて、現実をみましょうよ、といいたい所です。

さらに効率のよい素数判定

昨年、3人のインドの数学者が計算量のオーダーが多項式時間の決定性素数判 定を開発し、けっこう話題になりましたが、今回は、それに楕円曲線素数判定 の手法を加え、さらに改良された効率のよい決定性素数判定が発表されました。

Primality Proving via One Round in ECPP and One Iteration in AKS
Qi Cheng

計算量は以前のはヒューリスティック時間でO(log^6 n)ですが、これはヒュー リスティック時間でO(log^4 n)となっています。 これは正直言って純粋に数論の論文だと思うのですが、これがCRYPTO2003に投 稿されるという所が、いかにもCRYPTO2003らしい所です。ちなみに数学が専門 ではない筆者には、すごいなぁ、と思うだけです。

新しい公開鍵暗号方式

公開鍵暗号方式ではRSA、ElGamal、楕円曲線暗号などが有名ですが、この他に もたくさんの方式があります。何年か前にIBMが新しい公開鍵暗号方式をここ USCBで発表するからといって、CNNの撮影クルーが来ていたこともあります。 たぶんIBMがCNNにでもネタを売り込んだのでしょう。 今回のCRYPTOでもまた新しいコンセプトの公開鍵暗号方式が出てきました。

Torus-Based Cryptography
Karl Rubin and Alice Silverberg

ちなみにトーラス(Torus)とは円環体のことで、簡単にいえばドーナッツ型 のことです。その円環体上での計算を行うというのが味噌です。この公開鍵暗 号法の名前はCEILIDH (Compact, Efficient, Improves on LUC, and Improves on Diffie-Hellman )と書き、ケーリィーと読みます。発表者のSilverbergの かっていたネコちゃんの名前だそうで、論文の脚注には"この論文はケーリィー と名付けられた猫の思いでに捧げる"と書いてあります。もちろん論文発表の 際にもCeilidhの遺影を写しています。ちなみにSilverbergのWebサイトを調べ ていたら、その中にネコちゃんに捧げるCeilidhダンス(もちろん"踊り"です) というのも見つけました。

RSAで1024bit長レベルの安全性はCEILIDHでは160bit長で確保できるとし、ま た暗号化、復号化の計算でも次数の高い計算をするわけではないので高速に計 算できるように見えます。

ただ出たばかりなので、評価は半年から1年ぐらいまたなければいけないでしょ う。ちょっと気になるCEILIDHでした。

ダメ出しセッション

CRYPTO2003の最終セッションは、とてもわかりやすい実践的な「ダメ出し」の セッションでした。

Password Interception in a SSL/TLS Channel
Brice Canvel, Alain Hiltgen, Serge Vaudenaym and Martin Vuagnoux

SSL/TLSのインプリメンテーションに対し色々な分析をしている論文で、なか なか分かりやすい論文です。

ちなみに、メールクライアントとIMAPサーバをSSL/TLSで長時間接続している ような場合で、もし暗号化にRC4_MD5を利用していると何度も何度もIMAPのロ グイン手続きを繰り返すので暗号が解読されてしまいます。Outlook のデフォ ルト設定だと、安全ではないという指摘が論文ではなされていますが、基本的 には何であれ、同じです。この場合はサーバ側のSSL/TLSの設定でRC4を拒否す る指定にしてしまえば十分でしょう。

この発表を聞いていて、日本のCRYPTRECでは「SSL/TLSを使う限りRC4を許す」 というのを思い出しました。やっぱRC4は使っちゃダメじゃん。

Instant Cipher-Only Cryptoanalysis of GSM Encrypted Communication
Elad Barkan, Eli Biham, and Nathan Keller

GSMは、ヨーロッパの携帯電話方式で世の中で最も広く使われている方式です。 GSM方式は2002年末で191ヶ国で7億8千7百万の利用者おり、世界の携帯電話市 場の71%を占めています。GSMで使っている暗号はA5というストリーム暗号で、 これは簡単に解読できます。どれくらい簡単かというとPentium III 800Mhz搭 載のLinux Boxを使い40分で解読できるそうです。ダメじゃん。

Making a Faster Cryptanalytic Time-Memory Trade-Off
Philippe Oechslin

これはTime-Memoryのトレードオフの真面目な論文です。このケーススタ ディーにMS Windowsのパスワードを使ったことで、あちこちのニュースサイト で取り上げられて「マイクロソフトのパスワードはダメじゃん」という部分だ け一人歩きしてしまった、ある意味、本来彼の言わんとする部分が霞んでしまっ た不幸な論文だったかも知れません。

マイクロソフトのWindowsのパスワードですが、以前から今のハードウェアレ ベルだと簡単に見つけることができるというのは、暗号学方面のシステム セキュリティを専門にしている人達には共通認識です。別にマイクロソフ トに限らなくとも、UNIXでも互換性のために古いパスワードシステムを使えば、 結果はさして変わりません。

今年の新機軸 BOF

夜のランプセッションに備えて昼寝をするか、暇潰しに街に観光にいくか、あ るいはサッカーかソフトボールをする自由時間であった火曜日の午後に、今年 からはBird-Of-Featherのセッションに割り当てられました。もちろん自由時 間なので、出るも出ないも自由です。

初めての今年は、5つの企画がありました。
Cliff Bergman
Iowa State University
Crypto Courses 暗号学をどんな風に教えるかのBOF
Matt Blaze
AT&T Labs
Physical Cryptography 錠前を開錠させる方法 : 理論と実演
Hironobu SUZUKI OpenPGP BOF OpenPGP関係者のミーティング
Greg Rose PGP Keysigning PGPの公開鍵のKeysiging Party
Dave Del Torto
CryptoRights Foundation
HighFire - Communications Privacy for Human Rights 人権保護のためのコミュニケーションのプライバシー

OpenPGP BOFのセッションは筆者が世話役になりました。ひとくちにOpenPGP関 係者といいますが、キーサーバー関係者、フリーソフトウェアGNUPG関係者、 暗号研究者、PGP関係者という具合にコミュニティーが微妙に分かれています。 それに、なかなかみんな顔を会わす機会がありません。そこで、今回は筆者が 提案して、暗号研究者とPGP関係者がこの機会に顔を会わせて話し合おうとい うことになりました。

BOFは世話役の人がCRYPTO2003実行委員会に申し込んで場所と時間を割り当て てもらいます。OpenPGP BOFと PGP Keysigning は連続して行われましたがPGP Keysigningの方はCRYPTO2003実行委員長であるGreg Rose に世話役になっても らいました。

さてOpenPGP BOFの様子ですが、全部で12〜3人ぐらいの集まりで、以前PGPを 開発していたNetwork Associatesでの責任者、現在のPGP Corpの技術執行役員、 PGPを作った本人であるPhilip Zimmermannなど、PGPのキーパーソンが集まり ました。

まず、このBOFのAgendaをプレゼンテーションし開催趣旨を説明し、 さらに引続き筆者の行っているフリーソフトウェアプロジェクトOpenPKSDのシ ステムに関するプレゼンテーション (この時のプレゼンテーションはopenpksd.orgに おいてあります)を行いました。OpenPKSDに関しては、PGP Corp も商用の鍵サーバの機能で良いものは採り入れるという方向に進みそう です。これに関してはPGP Corpから直接マニュアルを送ってもらい、このマニュ アルにある情報の範囲であれば、知的財産権には触れないという共通認識が、 このBOF でなされました。その他にも色々な意見をもらい発表した側としては 十分満足するものでした。あとはフリーディスカッションが続き、公開鍵暗号 に対するパディングをどうするかといった内容が時間まで話し合われました。

この場をお借りしてBOF会場でお手伝いして頂いた東大の古原さん、日立の渡辺さんに お礼を申し上げます。ありがとうございました。

一番人が集まっていたのは、Matt Blazeの鍵あけのBOFでしょう。彼は色々な 錠前をピッキングツールで開けていく名人です。その理論と実践をBOFで公開 していました。以前に夜のお茶会Crypto Cafeで実演していたりしているのを 筆者も見たことがあるりますが、それは見事なものです。

ランプセッション

火曜日の夜7時から12時近くまで行うランプセッションは、持ち時間3〜5 分で、 学会開催のお知らせ、自分の研究、お笑いネタなどどんどんプレゼンテーショ ンしていくセッションです。

今年もっとも笑えたのはCounterpane社のYoshi KohnoとBruce Schneirが報告 した、世にも悲惨な暗号実装をしている投票システムでした。暗号の素人が、 参考書すらもよく読まないで、いきあたりばったりで作ったような内容で「こ んな方式で」と紹介するたびに会場が笑いで一杯になりました。

『このシステムの解説には「Schneirの本には、このアルゴリズムが書いてあ る(から安全)」とあるが、本のもうちょっと先には「... というアルゴリ ズムがあるが、今日では安全ではないから使わないようにしましょう」とちゃ んと書かいてあるぞ』とSchneir本人がツッコむと、会場大爆笑でした。

日本にも悲惨なシステムが溢れてしますが、こういうのを聞くたびにアメリカ も似たり寄ったりなのかなぁ、と思います。筆者もこの手のネタは結構もって いるのですが、調子にのってこれを日本でやるとウケる前に、客が引くでしょ う。

もちろん筆者は、最後まで聞かずに11時前には部屋に戻り寝ています。この日 はBOFが終った開放感もあってかなりビールを飲みすぎ、次の朝は二日酔状態 で、朝起きるのに、かなりきついものがありました。

さいごに

今年のカリフォルニアは天候もよく、寒くも熱くもないちょうどよい気候でと ても過ごしやすい日々でした。 帰国フライトのため一泊したサンスフランシスコでは、ちょうど地元ジャイア ンツのナイトゲームがあり観戦したりなどなど、今年は充実感があったのです が...成田に向かう飛行機の中でクレジットカード入の財布をなくしたことに 気づいたり、その後、ラップトップを開けてみると液晶が割れていて使い物に ならなくなっていたりして「世の中、いいことばかりは続かない」と思わせる 今年のCRYPTO2003でした。

ここまで