本文章は、共立出版Bit 1998年12月号と、技術評論社 Software Design 1998 年11月号に書いた記事をベースに、Web公開用に再編集したものです。



AES Conference / CRYPTO 98 訪問記

鈴木裕信

hironobu at h2np.net

AESやっとのことで会場に

やっとのことでたどり着いた場所は、カルフォルニア州ベンチェラ市のダブル・ ツリー・ホテルである。着いた時には、初日最後の発表が残されるのみになっ ていた。前日まで日本で仕事があった関係で成田を20日夕方出発、LA20 日朝9時に到着、そこからレンタカーを飛ばし、70マイル離れたベンチェラ へ向かった。しかし、ベンチェラについてから1時間ばかり迷い、やっと着い たのが既に午後3時だった。

休憩で人が会場からゾロゾロと出て来るが、妙に参加者がざわついてる。 誰かれとなく、真剣に話し込んでいる。いったい何があったのだろう。好運な ことに、友人の Philip Zimmermann (PGP作者)をすぐに見つけたのので、彼に聞いてみた。

「こんなすごいカンファレンスは見たことがない。Cryptographerという種類 の200匹もの闘犬がお互い噛みあって、血まみれになっていているようなもん だ。こっちにまで血しぶぎが飛んでくるような感じさ」と、飛沫をよけるしぐ さをしながら満面の笑みを浮かべていた。

それって、一体どういう状況なのだ!?

AESに至るまでの話

さて暗号に関する基本的な話は一気に割愛させていただく。そのかわり、裏話、 ヤジウマ的な話をどんどん入れていきたい。また、本文中の登場人物には、敬 称を省略させてもらうこととする。伏して御了承頂きたい。

AES (Advanced Encryptio Standard) は、現在、アメリカ合州国政府が決めようとしている次世代標準化暗号のこと である。その暗号アルゴリズムは公募で世界各地から集め、公開プロセスで決 めていこうとしている。おおまかなスケジュールは、1998年6月に応募を締め きり、最終的に提案されたどの暗号を使うかを決定するのは2000年である。

70年代の標準化暗号作業から数えると、新しい標準化暗号が発行されるまで、 約30年の間隔が開いてしまった。現実世界での1年が7年に換算されるコンピュー タ技術の世界でこれは異常な状況であると誰もが思うだろう。これは技術的な 問題が原因ではなく、政治的な混乱が引き起こした結果である。

米国には NSA (国家安全保障局)を中心として、暗号は国家が管理するものであ るという勢力が根強く残っている。そのため、NSAは暗号アルゴリズムを隠し、 かつ、その鍵を国家が管理しようとする、いわゆる クリッパー計画 を遂行しようとしていた。 しかし、 DES によって暗号は中身を公開してこそ皆が信頼するというパラダイムが既に出来 上がっている。今更、隠した所で誰も従うはずもない。DESという禁断のリン ゴを我々は噛ってしまったのだ。

その後、紆余曲折があって、公募により決めるという方法に落ち着いた。ただ、 現在でも、最終的にAESとしてどのような暗号が決まるのかの基準は曖昧であ る。しかし、今の所は、少なくとも、このようにAES選出のためのプロセスを オープンにするスタンスを取っている。

その最初のカンファレンスが、今回、筆者が潜り込んだ The First AES Candidate Conference なのである。1998年8月20日から22日まで行なわれた。 参加者は約200名であった。 主催は NIST ( 米国商務省傘下の技術標準化組織で、AES Candidateを仕切っている ) で ある。AESに応募があった暗号は全部で21。その内、書類上の手続きを満足し ていなかった6つの暗号が事前に落された。残った 15 が審査に望むわけだが、 この時点では、暗号のアルゴリズムが正当かどうかの評価を一切していない。 もし、今後、少しでも不透明な部分があってAESが選出されるようなことがあ れば、世界中の暗号関係者は、もう2度と米国政府を信用しなくなり、その時 点で、暗号の標準化という方法論自体が崩壊するだろう。安心して使える標準 化暗号がなければ、経済的にも大きなロスが発生し、システム開発も混乱をき たす事になるだろう。

AES会場にてパート II

Philが言うには、ドイツテレコムが出した MAGENTA が、発表直後、すぐに暗号が破られてしまったのだそうだ。MAGENTAの発表は、 ちょうど筆者が会場に到着したと同時ぐらいに終った発表である。筆者の驚き の表情を前に、彼が話を続ける。

「ドイツテレコムでは既に使っているとか、既に安全性分析を行なって解読不 可能だと散々説明し終った次の瞬間だ。」ニコニコしながらPhilは右手をあげ た。

Adi Shamir (RSAのShamir)が、解読方法を思いついたといって、解読方法を 説明する。Shamirが説明を終ったら、次の人が手を上げる。私は、今の解読方 法さらに改良したとね。そしてまた次。今まで数々の暗号関係のカンファレン スに出ているけど、こんなのは始めてだ。すごいエキサイティングだよ。」

あとから色々な人に聞いたが、さすがにこんなのは始めてなのだそうであ る。「10秒後には使い物にならなくなった暗号」という伝説は暗号関係者には 長く語り継がれることになるだろう。

初日終了後、カンファレンスに来ていた暗号研究者があつまり、詳しい分析を 行なった。Adi Shamir, Eli Biham (差分攻撃法), Bruce Schneier (Twofish設計者) などなど暗号解読のエキスパート中のエキスパートが集まっ た、まさに"ドリームチーム"である。 分析結果であるが、MAGENTAはキースケジュールに問題があり、ある条件下で 2^32の平文/暗号文のペアがあれば解読可能であるというものであった。分析 結果は、早くも翌日の朝には ペーパー として配布されている。 現在、DESを解 くのに最新の研究でさえ約0.73 x 2^42のペアが必要である。つまり、DESの後 継として、 ドイツテレコム が面子をかけて出してきたものは、約30年前に基本デザインが行なわれたDES よりも弱かったのである。この時のドイツテレコムの人達のショックは相当な ものだったろう。

MAGENTAは、今回の発表以前に自社Webで発表を行なうなど一切していなかった ので、こんな悲劇的なことになってしまったが、事前にWebで公開した後すぐ に暗号分析が行なわれ欠点が指摘されていたものもある。例えばオーストラリ アから出された LOKI 97 がそうだ。 発表の時点で、誰もが興味を失っている。発表者までもだ。発表には質疑応答 含めて45分間が割り当てられているのだが、LOKI 97の発表は、たった18分で 終ってしまった。もちろん質疑応答もなにもなしである。発表者はLOKI97の開発 の歴史と概要といった内容を手短に話しただけだった。

発表者は精神的に辛いだろうと思うが、情けは禁物だ。これは学会発表ではな く、AESを巡っての激しいサバイバルゲームなのだ。しかもNISTは、クロスカッ ティング・ポリシーを表明している。つまり、お互いボロボロになるまでやり 合うことを求めているのだ。

ここベンチュラに集まっているのは、世界中のトップ中のトップの研究者であ る。暗号の教科書に名前が出て来るような研究者がゾロゾロといる。この3日 間を行き延びることだって、生半かなことではない。

このカンファレンスは、受け付けた暗号すべてに対して発表させているので、 中には箸にも棒にもかからない暗号もある。なんせみんな暗号のエキスパート 中のエキスパートだから、そんなSnake Oil(インチキ)な暗号になど興味はな い。そんな発表の時は、完全に会場がダラケ切っている。前のニーチャン(あ えて名前を伏す)は、ラップトップでゲームを始めるし、右隣のネーチャン(あ えて名前を伏す)は、意味もなく紙を割いて空いたコーラの瓶に詰めているし、 左隣のオヤジ(あえて名前を伏す)は腕を組んで寝ている始末である。

しかし、 注目すべき暗号が発表される時は、会場がピリピリするほど緊張しているのが 分かる。まるで獲物を狙っているプレデターようだ。

NTTは生き残れるか

NTTはAESに、 E2 を持ち込んできた。発表は 盛合志帆(NTT) が行なった。日本人女性としても小柄な方で、アメリカにいると本当に子供に しか見えない。ちなみに、この発表の時、妊娠9カ月であった。

彼女の暗号分析研究は世界レベルで、若い世代のトップランナーの一人なので ある。ちなみに、アジア系女性で同世代の注目株研究者といえば、 RSA Lab 社の Lisa Yin Cylink 社の Lily Chen などがいる。ちなみに、Lisaが MIT の学生だった頃は、天才少女と呼ばれてい たそうである。実際に公開鍵暗号の標準化である IEEE P1363 ワーキンググループ の中心的メンバーから、 RC6 のデザインまで幅広く活躍している。常日頃、筆者は彼女のことを本当によく 働く人だと感心している。ボスの Ron Rivest が人使いが荒いのだろうか。

さて、E2の話しに戻ろう。E2チームは、今回の発表の中で念入りに準備をして きたチームの1つである。E2は、やるべきことは全部やってきたというチーム だった。専用ICまで実際に作っていた。それ以外で、専用ICまで作ってきたの は、 IBM ぐらいである。NTTという組織力をフルに活かしたといってもいいだろう。

E2は、安全性は高いだろうという評判である。安全性に関しては、非常に慎重 に設計している。これに関してはE2の基本デザインを行なった 神田 、 青木 の話、 また、外部の意見も一致している。少々のスピードを犠牲にしても、安全マー ジンを取る方向で設計されている。筆者の目から見ると、少し8ビットCPU上で の性能を意識して、それが32ビットCPU上では少し不利に働いているように見 える。E2は、エレクトリック・コマースのICカードを強く意識しているのかも 知れない。

E2のインプリメンテーションは、NISTの指定した実行条件では、他の競争相手 となるような暗号とは遜色はない。しかし、筆者の目からみるとNISTの指定し た実行環境は酷すぎて、おおまかな目安程度ではあっても、これでは、まとも な速度比較などできない。

このことは IBM の MARS のペーパーを見るとはっきりする。NISTが指定したイン プリメントのCのプラットフォームとは、 Pentium-Pro 200Mhzの上で Borland C (++) 5.0 を使うことだった。ところが、このBorland Cは、非常に効率の悪いコー ドを吐き出す。MARSのペーパーには、 pgcc (GCCをPentium用のオプティマイズができるように拡張したもの)を使えば、 Borland C (C++)よりも2倍以上高速になることが示されているのだ。これでは、 実際のインプリメントで本当にどの暗号が速いのか、現在のNISTの指定してい るプラットフォームを使ってのデータではわからない。

さて、このようにE2は、保守的で慎重なデザインであるが故に安全性がいきな り崩壊するようなことにはならないだろうし、E2チームもそう簡単には安全性 を崩せないと自信を持ってる。これから何段階のステージを経て、AESに応募 した暗号は次から次へとふるい落とされていくわけだが、最終ステージまでE2 は残るだろう。とはいえ、AESカンファレンスと、次の週の IACR 主催の CRYPTO98 (国際暗号学会年次大会)が終る約10日間、筆者はE2チームが緊張しているのが わかった。 MAGENTAやLOKI97のような悪夢を心の底では恐れていたのだろう。もし、ここ でNTTが以前の FEAL の汚名をさらに上塗りしてしまうような暗号を出してくるようなことがあれば、 もう2度と立ち直れないほどNTTの信用は失墜する。処理効率を多少犠牲にして も、保守的でかつ、安全性を高める方向で設計した背景には、そんな理由があっ た。 E2の発表自体は、盛合が発表を行なったためか、ごく落ち着いた雰囲気で終り (これも シホ信者 が多いためだろう)、質問も内容の確認といったものしか出なかった。また、 期間中、とくにE2の安全性に関するシリアスな問題点が指摘されることもなく 過ぎた。西海岸の10日間をE2は生き延びた。たった10日間と思われるかも知れ ないが、これはすごいことなのだ。

生き残るのはどれか

もし、AESに出された15の暗号のうち、自分の金を賭けろと言われたら、RC6に 持ち金の半分、あとの残りを、TWOFISH、E2、MARSに賭ける。下の西海岸にい たあいだ得た情報を元に筆者なりのランキングをつけるとしたら、次のように なる。

第一グループ

  • RC6
  • Twofish

    第二グループ

  • MARS
  • E2
  • DFC
  • SERPENT

    第一グループは、非常に勝ち残る可能性が濃厚なもの。第二グループは、第一 グループに何か問題点が発見されれば、すぐに入れ替わりが可能なものである。 しかし、SERPENTは、一部では評価が高く、また、逆にTwofishを嫌う人もいる。 人それぞれの評価基準があり難しい所だ。筆者は現時点で、この6つの暗号の 安全性は、ほぼ同じだと考える。あとの判断は、処理速度である。

    RC6のペーパーを見た時は驚いた。最近のプロセッサの得意な命令を選んで暗 号を作っていたように見えるのだ。この印象は、正しいようである。Twofish の設計に関わった hi/fm (ハイフンと読む)の技術者が教えてくれたのだが、RC6 は、ただのPentiumとPentium Proでは3倍程度速度が違うのだそうだ。完全に Pentium Proの命令をターゲットにして作っているとしか思えないのだそうだ。

    一寸先は闇

    しかし、このサバイバルゲーム、誰が残るかは、まだまだわからない。なぜな ら、CRYPTO98のランプセッションでイスラエルのチームがまったく新しい暗号 分析法が発表したからだ。その数日まえから、ShamirとBihamが今までとは異 なる暗号分析法をランプセッションで公開するらしい、という噂が流れていた。 ある話では、ShamirがNSAの人間を捕まえて「ランプセッションで、SKIPJACK の分析について話すから是非とも聞きたまえ」みたいなことをいったらしい。

    SKIPJACK とは、対称鍵暗号のアルゴリズムでクリッパー計画の中核を担う暗号技術とし て発表されたものだ。現在は Fortezza PC Card という暗号ハードウェアに組み込まれ、 国防総省 も含めた米国政府内での標準システムとして大量に使われている。その SKIPJACKが、使いものにならないらしいという噂も出ていた。数日前から噂が 噂を呼び、前評判が高まった中で発表されたが、実際の話はもっとショッキン グなものだった。

    Impossible Differential Attackと名付けられたその暗号解読法を使えば(筆 者の理解に間違いがなければ)SKIPJACKが2^33の平文/暗号文ペアで解けると いう内容だった。この数が出たとき、さすがに会場はざわめいた。インフォー マルな発表の場であるランプセッションなので、割り当てられた時間がたった の17分である。しかも、簡単なOHPと口頭での発表なので筆者は、ぜんぜん構 造を理解できなかった。ポイントはどうやらFeistel構造の暗号化する過程を、 平文側と、暗号化した側からと同時に追っていくことらしい。ちょうどヨーヨー のようにいったり来たりしながら、ビットの変化の確率を縮めていくようだ。 といっても、筆者も分かっていっているわけではない。

    ちなみに、筆者の知合いの暗号研究者の何人かに聞いたがすぐには理解できな かったそうだ。もう少し時間が経てばフルペーパーがWebサイトに載せられる だろうから、そちらを 参考 にして欲しい。

    この発表が終ったあとの休憩は、これまたいろんな話が聞けた。Philは、「発 表の最前列にはNSAの人が陣取っていて、必死にメモを取っていた。」と筆者 に教えてくれた。どうやらNSAもこの解読法を知らなかったらしい。アカデミッ クが世界最大の諜報組織を乗り越えた歴史的な瞬間だったのかも知れない。 Philにとって宿敵とも言えるNSA連中の慌てる姿を見ることは、さそがし痛快 だったに違いない。

    さて、このIDAが出て来たおかげで、AESで何が生き残れるかの予想はさらに混 迷を深める。次の日には、IBMのMARSは、IDAには弱いのではないかという噂が 流れた。フルペーパーがない状態のIDAの発表を聞いての話だから、真実味は ない。しかし、これから先、今まで安全性が高いだろうと思われていたいくつ かの暗号がバタバタと倒れる可能性も否定できないのである。最後はSERPENT しか残らないという可能性だってある。

    次のAES カンファレンスは、3月にローマで開かれる。次ぎのAESカンファレン スのポスターは、古代ローマ時代に作られたコロシアムの写真である。古代ロー マ時代、ローマ貴族の娯楽のために、奴隷が戦士となり殺し合いを行なった場 所である。1999年3月、今度は、AESのサバイバルゲームの渦中いるプレイヤー が暗号というフィールドで同じことを行なう。

    これが噂のDEEP CRACK

    これが EFF (Electronic Frontier Foundation)が作った噂の DEEP CRACK である。DESの鍵空間をブルートフォースするためだけに特別に設計されたチッ プAWT-6001をボードに大量に装着し、古いSUNのシャーシ(VMEバス)に差し込ん でいる。 チップ1個の中に24個の検索ユニットが入っている。ボード1枚に、64個のチッ プがつけられている。VMEバスを持ったSUNのシャーシ1台に、ボードが12枚刺 さっている。そして、そのシャーシが2台ある。

    36864個の鍵空間検索のユニットが同時に動作でき、毎秒約921億個の鍵を 試行し、平均約4.5日でDESをクラックする。製作に25万ドルが使われた。これ がDEEP CRACKの正体である。このボードについているチップが損傷し、稼働し なくなっても、他のチップの動作に影響を与えないような設計になっている。

    EFFは RSA 社が主催する DESCHALL2 の 成功者 という栄光と賞金1万ドルをDEEP CRACKを使って得たわけだが、EFFの目的は、 あくまでも政府が暗号を簡単に解読できるという論拠を提示することである。 それにしても、25万ドルをつぎこんで、ここまでやるEFFは根性がある。ラン プセッションの時、Ron Rivestは、 John Gilmore にこう言いながら1万ドルの小切手を手渡した。「空調代程度しかならないけ ど...」

    Johnは、持ってきたDEEP CRACK のボードをラップトップに接続し、どんな風 に動くかをデモしてくれた。場所は、ドミトリー(宿舎)のフリースペースとし て割り当てられた部屋である。このようデモは、普通はワンサと人が集まるの だろうが、CRYPTO98は最先端を行く暗号学者ばかりなので、この程度のテクノ ロジーに興味を示す人はごくわずかだった。

    バーベキューパーティーの会場でテキーラを片手に、筆者と 下山 は 下山/金子の改良線形解読法 をどこまでアクセラレートできるかを話していた。もし、DEEP CRACKの処理能 力があれば、1時間から、少なくとも2時間以内にはDESを解読できるというレ ベルまで話は見えていた。その時、近くにJohn Gilmoreを見つけたので、彼を 捕まえ、さっそくこのアイデアを話してみた。

    しかし、残念ながら、DEEP CRACKは、平文/暗号文を処理するような汎用的な 能力はなく、ただひたすら鍵空間を潰すための非常に特化した設計になってい る(だから速い)とのことだった。彼から「通常のDESチップを使う方が良いの ではないか」という提案をもらった。

    心地よい海風にあたりながらの桟橋まで歩いていた下山と筆者に 黒澤(東工大) が加わって、また、「何分でDESを解くか」という議論で盛り上がった。最終 的に技術的には難しくないが、ハードなどの調達があり研究者の人件費を見込 まないでも開発費用には3000万程度の予算は必要ではないかという意見に落ち 着いた。ただし、「DESを2時間で解きます」と力説した所で、誰も3000万円を ポンと出してくれる所はないだろうし、どこかに出す研究費申請の理由にして も「まずは解いてみたいから」ということじゃ何処も相手にしてくれないだろ う、というのが3人の一致した意見だった。やっぱり「山に登るのは、そこに 山があるからだ」というのでは、難しい。

    最後に

    CRYPTO98のスケジュールも終り、ランチを食べながら、今後のPGPに関して Philと話し合った。ここだけの話だが、 PGP の現仕様のパケットを改良して鍵が可変長なAESに対応することと、Twofishと SERPENTを次のPGPに組み入れるつもりでいると語った。午後にPGPの拡張に関 するミーティングが開かれたが、筆者は参加しなかった。

    暗号技術は、今が旬の分野である。技術も日進月歩以上の速度で進む。とりま く社会的状況もダイナミックに変化している。情報の民主化、国家の統制、な ど色々な政治的思惑が入り乱れる一方で純粋な数学の発展場でもある。そこ出 て来た技術はすぐさまシステムに応用され、莫大な富を生む材料にされる。ま さに、エキサイティングとしか言いようがない。こんな面白い分野は、今、他 にない。

    おしまい