オリジナルは2004年に公開した文章ですが、むかしのHTMLの書き方で漢字コードなどは指定していなかったりするのでオリジナルのHTMLファイルを見ると文字化けするとかトラブルかも知れません。今回SHA1初のコリジョン発見という機会にCRYPTO2004での Xiaoyun Wangの発表の様子の部分を抜き出してブログの方に掲載したいと思います。

CRYPTO2004 レポート

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回目のCRYPTOです。サンタバーバラはアメリカのリビエラと呼ばれるほど全米でも屈指のリゾート地域として有名で、ブラットピットやジョントラボルタが別荘を構えていたりします。ついでにマイケルジャクソンのネバーランドがサンタバーバラにあるので、あの有名な裁判が現在サンタバーバラ地裁で行われています。ちょうど滞在中にもマイケルジャクソンの公判が開かれていました。海がきれいで、気候がすごしやすく、静かな街なので1週間ぐらい休暇を楽しむのには最高の街です。

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

ハッシュの厄日

最初、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は今までの中で一番感動的でした。継続は力なり。最後に、誘ってくれた松尾さんに感謝します。