CRYPTO2004 レポート ハッシュの厄日

投稿者: | 2017年2月24日

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

 

 

 

FacebooktwitterpinterestlinkedinmailFacebooktwitterpinterestlinkedinmailby feather