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


CRYPTO2004 レポート

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

2004年8月15日〜19日まで米国カリフォルニア州サンタバーバラにあるUCSBキャ ンパスで開催された暗号学会 CRYPTO2004 のレポートをお届けします。

鳴り止まぬ拍手

発表者であるXiaoyun Wangが発表を終えると会場では地鳴りのような拍手が湧 き起こった。スタンディングオペーションをする者もいる。10秒、20秒。拍手 が鳴り止まない。まるでテレビで見るアカデミー賞か何かに出席しているよう な気分になるが、まぎれもなくアカデミックなカンファレンスに来ているのだ。 拍手はまだ続く。ずいぶん長く続いた拍手に続き、やっと共同発表者のXuejia Laiが 壇上に上がり補足説明を始めた。こんな劇的な発表に立ち会えるのは、人生の なかで、そう何度もないだろうなと心の中でつぶやいた。

さて、いつものスタイルに戻しましょう。CRYPTOは、 IACR ( International Association for Cryptologic Research / 国際暗号学研究会 ) が毎年8月にカリフォルニア州立大学サンタバーバラ校で開催している学術分 野では世界最大規模の暗号研究のカンファレンスです。最大といっても 何千人もやってくるわけではなく、せいぜい400人規模のサイズです。CRYPTO では暗号の理論的なものが中心です。いわゆる「学会発表の場」というイメー ジで捉えてもらうと判りやすいと思います。

筆者は8月15日日曜日の午後、ロサンゼルス経由のフライトでサンタバーバラ に到着しました。始めてCRYPTOに参加してから早くも10 年、途中1回サボって いるので、9回目のCRYTPOです。 サンタバーバラはアメリカのリビエラと呼ばれるほど全米でも屈指のリゾート 地域として有名で、ブラットピットやジョントラボルタが別荘を構えていたり します。ついでにマイケルジャクソンのネバーランドがサンタバーバラにある ので、あの有名な裁判が現在サンタバーバラ地裁で行われています。ちょうど 滞在中にもマイケルジャクソンの公判が開かれていました。海がきれいで、気 候がすごしやすく、静かな街なので1週間ぐらい休暇を楽しむのには最高の街 です。

一方で、カンファレンス参加者はUCSBキャンパス内の寄宿舎に宿泊し、午前、 午後、夜にはランプセッションやレセプションのようなソーシャルプログラム などのスケジュールが詰まっているので、完全に缶詰状態、合宿といった感じ です。しかし、最近のヒートアイランド化した灼熱の東京を抜け出して、夜に は長袖が必要なほど冷えるこの地に来るのは、やはり気持ちのいいもので、 筆者も気がつけば過去10年間で一回しかサボっていないという理由もこの辺に あると思います。

本編の内容だったのだが...

今年のセッションは全部で15、採択された論文が33論文あります。セクション を眺めてみると最近の暗号技術のトレンドがわかるのでリストアップしてみま す。

  • Linear Cryptanalysis : 線形暗号解読法
  • Group Signatures : グループ署名
  • Foundation : 暗号基礎技術
  • Efficient Representations : 効率的暗号化技術
  • Public Key Cryptanalysis : 公開鍵分析
  • Zero-Knowledge : ゼロ知識証明
  • Hash Collisions : ハッシュの衝突
  • Secure Computation : 安全な計算
  • Stream Cipher Cryptanalysis : ストリーム暗号分析
  • Public Key Encryption: 公開鍵暗号
  • Bounded Storage Model : 情報理論に基づく安全モデル
  • Key Management : 鍵管理
  • Computationally Unbounded Adversaries : 非特定対象者のための手法

    今年の印象は「いつもにも増して地味」といったところでしょうか。去年は、 わかりやすいセッションを作っていたのですが、その反動からか今年は本来の 学術系に戻そうといった方向性なのでしょうか、それとも単純にこのようなな らびになったかわかりませんが、実に「アカデミックな学会」の雰囲気を漂わ せています。

    Invited Talk

    Invited Talkは次の通りです。

  • Victor Shoup, "14 years of Chosen Ciphertext Security: A Survey of Public Key Encryption" (16日午後)
  • Susan Landau, "Security, Liberty, and Electronic Communication" (18日午後)

    公開鍵暗号法における安全性の最も強い条件は、Chosen Ciphertext Attack (選択暗号文攻撃)に耐えうることを証明しているものです。公開鍵暗号法にお いてのChosen Ciphertext Attackとは、秘匿鍵(復号鍵)を計算するために、 任意の暗号文を与え、復号の計算をさせ、その結果の値をたくさん集めて、そ こから計算して秘匿鍵を見つけていく攻撃方法です。 復号する計算に値を与えれば、当然、なんらかの計算値が返却されます。返却 された計算値は、実際に計算した値なわけですから、計算につかった情報を含 んでいます。一方で、復号を行ったプロセスでは、計算した値が正しいものな のか否かを持っていないので、計算した値を返さざる得ません。答えを返せば 返すほど相手にどんどん情報を漏らしていってしまいます。 ではその情報を外部に漏らさない方法はどうすればいいのでしょうか、という のがChosen Ciphertext Securityの話題です。その歴史から、今日までの技術 をサーベイしています。 彼は公開鍵暗号法の規格であるISO-18033-2 (資料は http://www.shoup.net/か ら入手できます。) の取りまとめをしていたりする、この分野での第一人者な ので、なかなか面白かったです。ちなみに、以前IBM Zurich Research Laboratoryにいたのですが、今はNew York Universityに移っていました。

    トリビアの泉 : RSA-OAEPはだれも安全性証明をしないまま使っていた

    SSL/TLS の公開鍵規約RKCS #1 v2.0やIEEE P1363ではChosen Ciphertext Attackからの安全性を高めるためRSA-OAEPという方式を採用しています。 RSA-OAEPは広まっているので安全性が証明されていているだろうと思い込んで いました。ところが実は誰も証明してはいなかったのです。 何年か前、フランス人研究者David PointchevalがNTT研究所を訪問するため来 日しましたが、その折、長いフライト中、やることもないだろうから、目を通 していなかった論文でも読もうかと機内に持ち込み読み始めて、しばらくして 気がついたのです。「RSA-OAEPのきちんとした証明は誰もしていない!」。そ れから日本とフランスの合同研究チームでRSA-OAEPの安全性を証明して発表し ました。RSA-OAEPは93年頃から提唱されていて、それから数年の間、世界中の 優秀な研究者が全員揃って、こんなメジャーな技術の基本部分を見逃していた のですから、うっかりミスというか、思い込みみたいなものが、あるんだなぁ、 と逆に驚いてしまいます。

    Sun Microsystems LaboratoriesのSenior Staff Engineerである Susan Landau の話は、9/11以降アメリカ政府における市民への監視や盗聴の懸念です。テロ という煽り文句の裏で、現実には、市民はどんどん監視社会の檻の中に追い込 まれつつあり、これではアメリカの民主主義や健全な市民生活が脅かされると いう社会的なテーマです。9/11以降のブッシュ政権では、何でもアリみたいな 状況です。9/11とブッシュ大統領のトラウマはアメリカに長く残ることでしょ う。

    論文等について

    ハッシュに関しては後程書くので、それ以外に関して、個人的に興味を引いた のは、Alex Biryukovらの"Linear Cryptanalysis"とNicolas T. Courtoisの "Feistel Schemes and Bi-linear Cryptanalysis"です。三菱電機の松井充さ んによって開発されたLinear Cryptanalysisによって世界で始めてフルスペッ クのDESを解読したわけですが、それをさらに発展させています。 Biryukovの方はベイズ推定を使い、走査する鍵空間の確率密度をあげるという 技を使っています。筆者もインターネットを飛び交うパケットを検知し、 ベイズ推定を使い危険度を計るという研究 をしているので、こんなベイズ推定の使い方もあるのか、と感心しました。最 初のDES解読の計算量は2^43でしたが、この方式では2^36程度になると見積も られています。 Courtoisの方はFeistel構造という処理構造を持った方式に対し強力に適用で きる方法で、結果からいうと解読のための計算量は2^32.6程度になると見積も られています。なんか「とうとう、ここまで来たか」と思います。 ちなみにDESはこの夏にNISTの暗号規格から外されてしましました。

    あいかわらず人気のToyocrypt

    IPAとNICTが共同でe-Japanに使うための暗号技術の推薦方式を決めるという CRYPTREC ですが、そこにストリーム暗号として提案し、却下されたToyocrypt は今年のCRYPTOでも人気でした。 E0、LILI-128、ToyocryptのようなLFSR (linear feedback shift register) 方式を使ったストリーム暗号は、簡単に暗号が解読できるので現実的には使い 物にはなりませんが、皮肉なことにLFSR方式のストリーム暗号の新しい解読方 法を開発するにはもってこいのプラットフォームとなっています。

    特にToyocryptは、簡単に解読できるので「新しい解読法では、以前よりこれ だけ改善された」という、とても判りやすい改良指標として使われているよう です。Philip Hawkesらの"Rewriting Variables: The Complexity of Fast Algebraic Attacks on Stream Ciphers" の論文では、E0が2^49で、LILI-128 が2^40、Toyocryptが2^29の計算量で解読できるとなっています。この解読方 式はFFT (高速フーリエ変換)を使うというとても洗練された方式なので、興味 を引く所ではありますが、それ以上に2002年に出た最初のToyocryptの分析で は計算量が2^96 であったのが、今は2^29かぁ、と妙に感心しています。 このように極端に進化するストリーム暗号解読法を見聞するたびに、ストリー ム暗号は使わずブロック暗号に適切なモードを使う方式のみにすべしというス トリーム暗号不要論者の筆者は、それみたことか、と思うのでした。

    量子コンピュータ時代のZero-Knowledge Proofs

    Zero-Knowledge Proofs(ZK: ゼロ知識証明)は自分の情報を隠しつつ、自分が 情報を持っていることを証明するような一見矛盾するような技術で、たとえば 匿名でありつつ正当な利用者であることを証明できるなど、色々な使い途があ る重要な技術です。 実用的な量子コンピュータが現われると、既存のZKは、RSA やElGamalのよう な 公開鍵暗号法と同様に解読されます。量子コンピュータ時代の公開鍵暗号 法は既にCRYPTO2000でNTTの研究グループから提案されています。今回はIvan Damgardらが"Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks"の論文の中でQuantum Zero-Knowledge Proofs (QZK: 量子ゼ ロ知識証明)という方法を提唱しました。ただ、このCRYPTO2004の論文集の方 は短いらしく、フルバージョンのドキュメントは http://www.brics.dk/RS/04/9 にあると論文の参考文献には書いてあります。執筆時点ではパーミッションが おかしく、アクセスできない状況にありますが、Damgardさんに連絡を取った ので、たぶんこの記事を読むころは大丈夫だと思います。

    ハッシュの厄日

    最初、Xiaoyun Wangの論文の存在を知ったのは、15日の夜のレセプション会場 でした。食事も終り松尾さんとビールを飲みながらたわいない世間話をしてマッ タリしていた時です。友人の Philip Zimmermann が筆者を見つけ、いきなりプリントを突き出し、「ひろのぶ。この中国の人の ペーパーを読んだか。これはすごいぞ。」とニコニコしています。彼がこんな にニコニコする時は、大体において、画期的な暗号解読法が見つかった時です。 思い起こせば、ドイツテレコムのMAGENDAがあっさり破られた時、米国政府が 作ったSkipJack が破られた時も、こんな感じでニコニコしていました。

    Xiaoyun Wang et. al, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"というこの論文(論文というよりはメモだと思 うのですが、Paperの訳語は論文なので、文中は論文としておきます)のいっ ていることは極めて明白で、「MD4、MD5、HAVAL-128、RIPEMDのハッシュに関 してコリジョンを見つけた」ということです。 これはeprint.iacr.org (番号は2004/199です)から入手できますが、最初の登 録は8月16日となっています。この時点で筆者の見たものは、きっとリバイス 途中のものだったのでしょう。

    ほとんど情報がなくて、「IBM P690でMD5が前処理に1時間かかり、発見するの は15秒から5分である」と書いてあってコリジョンの値が書いてあります。他 にはHAVAL-128、MD4、RIPEMD について各々コリジョンと、どれだけ処理にか かるかが書いています。理論的背景に関しては理解に役立つような情報は書い ていません。ただ、「コリジョンがわかっている」という現実を突き付けるだ けです。 もし、このペーパーの共著者にXuejia Laiが入っていなかったら、きっとこれ は冗談の一種なんだろうと思ったことでしょう。Xuejia LaiはPGPに使われて いて有名な共通鍵暗号IDEAの設計者であり、ETHの元教授James L. Masseyの門 下生なので、アカデミックなバックグラウンドはきちんとしている人です。あ る意味、この論文に嘘はないということを担保している人といっていいでしょ う。 しかし、あまりにもよくわからないので、他の人に意見を聞こうと思い「中国 の人のハッシュの話って知ってる?」と何人かに聞いたのですが、筆者の聞い た範囲では「BihamさんとJouxさんのなら今年の論文に載っているから知って いるけど、中国の人のは知らない」というという反応でした。きっとLaiと Zimmermann はPGPつながりがあるので公開する前に渡っていたのだと思います。

    明けて16日、この辺からが話が急に展開していきます。午前中のセッションが 終り昼食時ともなると、17日の夜のランプセッションで急拠この発表のために 時間を割いてプレゼンが行われるという噂が飛び交います。16日の午後には、 ePrint経由で配布が開始されました。17日午前中のセッションで、今晩のラン プセッションはインターネット経由でストリーミングが行われますというアナ ウンスが出ます。午後は自由時間なので、筆者は学食をやめて、おいしいメキ シコ料理を探しにサンタバーバラ市内に向かいましたが、この頃世間ではちょっ とした騒ぎになっていたようでした。

    ニュースサイトで、「重大な欠陥発見の報告相次ぐ」なんていうような刺激的 な見出しで、さらに今夜Eli Bihamが画期的な発表をするらしいというような ことを書いて煽っていたので(この煽り文句はアップデートによりなくなって います)、あまり暗号技術に詳しくない人は、その記事をみて、ちょっとした パニックになっていたようです。 日本のメーカーやベンダーの研究者が当然何人か来ているわけですが、日本か ら「いったいどんな内容が発表されたんだ。すぐ報告しろ」というような趣旨 のメールが来ていたそうです。会社の出張としてではなく、夏休み期間を利用 し参加している研究熱心な人などは、お盆料金の割高旅費と参加費を自腹で払っ ているので、「ちょっと複雑な気持だよね」といっていました。

    Eli Biham

    夜7時にランプセッションチェアのStuart Haberが簡単にオープニングを済ま せ、さっそく最初のEli Biham発表に移ります。尚、彼のSHA-0に関する論文と 発表は既にCRYPTO2004の本編に組み込まれています。SHA-1はフルスペックで は処理ラウンドが80ラウンドあるのですが、現在は34 ラウンドまではコリジョ ンを見つけることは出来るという内容を発表しました。悲観的に見るとSHA-1 はあと46ラウンドしか残っていない、楽観的に見ると46 ラウンドも残ってい る、というわけです。筆者の意見としてはSHA-1の寿命は急速に尽きるという わけではないのですし、SHA256のように既に次に使うべきロードマップが用意 されているので、そんなに慌てることはないでしょう。 CRYPTO2004の前の週に行われたカナダのUniversity of Waterlooで開催された SAC (Selected Areas in Cryptography) のカンファレンスに参加された方に よると、この内容はそこでの招待講演で話した内容と同じだそうです。

    Antoine Joux

    彼は、つい先週SHA-0のコリジョンを見つけたので、そのコリジョンの発表で す。尚、彼のSHA-0の安全性分析に関する論文と発表はBihamと同様に CRYPTO2004の本編に入っています。 CEA DAM open laboratoryのTERA NOVAという256ノードのIntel Itenium2シス テムが使われ160個のCPUを約20日間稼働させて見つけたといういうことを説明 していました。ちなみにCEAというのはフランスの国立研究組織でエネルギー、 医学、情報、軍事という幅広い分野をカバーしている所です。

    Xiaoyun Wang

    Xiaoyun Wangは、少なくとも世界レベルでの暗号分野ではまったくの無名の研 究者です。そこで山東大学のウェブサイトについて色々と探しました。
  • 王 小 云 (Wang Xiaoyun) 1966年生まれ
    中国 山東大学 数学系 副教授
  • 英語版 http://www.prime.sdu.edu.cn/third/05wangxiaoyun.html
  • 中国版 http://mathserver.sdu.edu.cn/html/professor/gehai/wangxiaoyun.htm

    この論文リストをみると、今回発表した内容のベースとなっているのは1996年 から2000 年にかけてのハッシュの研究の成果のようです。また自分でもハッ シュを設計して、これらの内容に関しては国内の暗号学会には既に発表済のよ うです。経歴からはバックグランドは数論で、離散対数問題の研究から暗号方 面に入ったことが伺えます。

    そもそも何でこの論文がCRYPTO2004に出てきたかというと、スイスで働いてい た Xuejia Lai (来学嘉) が2004年になって中国上海の上海交通大学にある Cryptography and Information Security Lab の教授として戻り、そこで中国 国内でのみ発表されているこの研究を知ったそうです。それで知った中国国内 でのこの内容に驚き、それをIACR経由で紹介しようという流れになったという 話しです。

    IBM p690を使いMD5の前処理に一時間、発見には15秒から5分程度ということが 論文に書かれていましたが、たぶんこのマシンは 山東省高性能計算中心 ( Shandong University High Performance Computing Center ) にあるIBM p690 で1.7 GHz Power4+の32wayでメモリ128GBを使ったのではないかと思います。

    プレゼン始まる

    彼女が演台に上がり話し始めました。が、しかし、英語であることはわかるの ですが、何を話しているのかさっぱりわかりません。たぶん英語ネイティブな 人でも無理でしょう。しかし会場全体は、雰囲気を何と表現したら良いのかわ かりませんが、とにかく妙に張り詰めた空気が漂っています。何を話してるか わからないのに。不思議です。 パワーポイントのスライドが変わるたび「MD5のコリジョンを多数発見してい る。事前処理に1時間、発見には15秒から5秒」「HAVAL-128は2^6の計算量」 「MD4は手でも計算出来る」「RIPEMD-128のコリジョンを発見」と読み間違い のしようがないくらいにシンプルに書かれています。 「MD4は手でも計算できる」というページに来た時に、筆者の頭の中でソロバ ンを手にもった何十万、何百万という中国人が地平まで広がる絵を思い浮かべ てしまって、それが頭から離れず、笑いを堪えるのが必死でした。

    ノートパソコンの画面から目を話し、前を向いて一呼吸おいてから"Thank you"という言葉を述べます。聴衆は、これで説明は終ったということがわかり、 少しの間があって、そして万雷の拍手がおこります。 この妙に高揚した拍手の嵐の中、ゆっくりと会場を見回します。そうすると、 あちこちでスタンディングオベーションをしている人がいるではないですか。 そもそも、ここは論文発表会場ではなく、夜に行う非公式な余興の場といえる ランプセッションです。筆者も色々な海外のカンファレンスに出ているつもり ですが、こんなのは始めてです。 拍手が鳴り止んでから、Laiが壇上に立ち、最初に出した論文のは色々と不備 があったので、それに関連してのコメントを述べていました。

    余談ですが、会場から戻ってきてslashdot.jpを覗いてみると、このランプセッ ションの話題が出ていたので、「さっき、その会場から戻ってきました」とい う内容で会場の雰囲気を 手短にレポート しました。

    バーベキューパーティにて

    とにかくWang Xiaoyunは、ハッシュ関数に関してはIARCメンバーよりも、さら に高度な知見を持っていることは事実で、しかしながらその方法に関しては、 ブラックボックスなわけですから、とにかくあちこちで捕まっては質問されて いました。彼女は英語の聞き取りは問題ないようですが、話す方はまったく何 を言っているのかはやはり英語のネイティブスピーカーでもわからないようで す。期間中、Xuejia LaiやLily Chenなど一流どころの中国系暗号研究者が付 き添っていて通訳のサポートしていました。ちなみにLily Chenは現在モトロー ラに在籍して、最近は暗号規格などで活躍している有名な人です。

    それを見てた誰かが「常にグルーピーと、ボディーガードに囲まれているなん て、なんかロックスター並だね」といっているのを筆者は聞いて、それは言え て妙だと思ったりしました。でも、見かけは本当に普通の人なので、なんだか 奇妙な感じです。 水曜日の夜、恒例のバーベキューパーティーが、いつもの調子で始まります。 みんながビール片手に「今回のランプセッションは凄かったねぇ」「朝のセッ ションでJouxへの質問の時、彼女がiterateが良くないとか言っているけど、 いったいその背景の研究って何があるんだろうね。中国は奥が深いね。」 「CRYPTRECの方はSHA256があるから大丈夫」などと、話題はランプセッション のことで盛り上がります。

    新しいビールを取りにいこうとすると、桟橋の方に向かう二人の姿を見つけま した。一人はXiaoyun Wangですが、もう一人の男性がよくわかりません。です が、その後ろ姿は長年寄り添った仲の良い夫婦というオーラーが出ています。 テーブルに戻り、それを話すと、「それはWangさんの旦那さんだよ。Wangさん は中国にいるけど、旦那さんは今は米国にいる。」とのこと。これで9/11以降、 中国から米国入国のビザが大変取りづらくなっている中、このカルフォルニア まですんなり問題なくやってこれた理由がわかりました。

    最後に

    今年のCRYPTO2004は仕事が忙しい上に、プログラムを見てもめぼしいものがな かったので、サボろうかな始めは考えてみました。いつもCRYPTOで顔を会わせ る松尾さんに背中を押されなければ、たぶん参加しなかったでしょう。しか し今年のCRYPTOは今までの中で一番感動的でした。継続は力なり。最後に、誘っ てくれた松尾さんに感謝します。

    ここまで