CRYPTO2006 カンファレンス レポート

すずきひろのぶ hironobu /at/ h2np /dot/ net

技術評論社 Software Design 2006年 11月号12月号 の原稿をベースにWeb用に再編集 したものです。

2006年8月20〜24日米国カリフォルニア州サンタバーバラ市にあるUCSB(カリフォ ルニア州立大学サンタバーバラ校)にて開催されたCRYPTO2006カンファレンス (国際暗号学会IACR主催)と、それに続いて行われたNIST(米国国立標準技術研 究所)が主催した第二回Hash Workshopが24〜25日に行なわれました。そのレポー トをお届けします。

どんな所なのか

CRYPTO2006の正式名称はCRYPTO 2006 The 26th Annual International Cryptology Conferenceというもので、国際暗号学会(IACR: The International Association for Cryptologic Research) という学術団体が主 催している、暗号の研究に関するアカデミックな国際会議です。毎年、この時 期に University of California, Santa Barbara で開かれています。夏休みの学生がいなくなったこの時期に 大学の施設を有効利用しています。

サンタバーバラは、ロサンゼルスから北に大体100マイルほど行った所にある。 風光明媚な海岸の街です。海流の関係で冬はあたたかく、夏もあまり気温があ がらない地域です。街の紹介文には「アメリカのリビエラ」という言葉が載っ ています。熱い東京から、夜になるとトレーナーが欲しくなるほど温度が下が るサンタバーバラへの移動は、慣れないと体調を崩す時もあるほどです。

なんだかんだと今回で10回目なのですが、今回は後ろにハッシュ関数ワーク ショップがあるので、今までで一番長くUCSBのドミトリーに宿泊するはめにな りました。アメリカの夏休みは年度の切替えなので、それまで住んでいた学生 が退去します。そこに参加者が泊まるのですが、これが若い人向けというか、 硬いベットで3、4日も寝ていると身体が痛くなる代物です。外に泊まろうにも 街まで遠いし、この夏の季節はホテルのピーク価格なので、ちょっとした部屋 でも一泊200ドルとか300ドルとか平気でしますので負担もかなりになります。 ちなみにドミトリーの宿泊費は朝晩の食事がついて一泊あたり約80 ドルです。 このようなわけで選択肢はなく、この硬いベットに毎夜寝ることになるのでし た。

今年のCRYPTO

最近のCRYPTOは参加者が減少しています。ピークの2000年頃は参加者は500名 を軽く越えていたのですが、今回は大体350名前後です。ITバブル崩壊以降、 米国ではコンピュータ方面に進む人達が減少傾向にあります。それに拍車をか けてアカデミックな方面でのセキュリティ研究人口が減少の傾向にあります。 その流れの上にあるようです。ちなみに真面目で難しい方面はこんな感じです が、そうではないセキュリティ方面は人が増えています。

さて、今年のCRYPTOは、ちょっと今までと違う構成になっていました。それは 今までは、暗号研究全般を広く取り上げ、さらに今日特に取り上げるべきテー マを絞るというスタイルを取ってきました。ですからここに来ると現状の暗号 技術の最先端情報が一通り知ることができるという価値がありました。発表セッ ションのプログラム構成を見ると、今のトレンドを知ることができました。所 が今年は、採択内容が非常に偏っており、各セッションにタイトルも付かない 並びになっていて、体系的にチョイスしていません。

発表内容を見てみると暗号プロトコルのテーマの発表が多く、発表者の構成は さらに興味深いもので、イスラエルから、あるいはイスラエル関係者がからん だ発表数は9(全体数34)ありました。これは全体の25%を越えていました。 噂ではプログラム委員長の意向がかなり反映されたようです。さすがにこれで は運営に批判が集まり、水曜の午後最後にあるIACRのミーティングではやり玉 にあがっていました。改革案の中には「プログラム委員が共著者に入っている 論文は採択しない」という、ちょっと首をひねるようなものも入っていました。

発表

最優秀論文賞は一日目に発表した次の論文です。

On The Power of The Randomized Iterate Iftach Haitner, Danny Harnik, and Omer Reingold

これはRandomized Iterateと呼ぶ繰り返し一方向性関数(ハッシュ関数)を呼ん で疑似乱数を作っていく方法を改良したものです。この方法は以前の方法より 高速であるという内容と同時に、一方向性関数により困難性を大きくしていく (Hardness Amplification)を理論的にも新しく先に進めている点が興味の引く 所です。たとえ通常の弱い一方向性ハッシュ関数でも十分な疑似乱数を生成で きるということを理論的に証明しています。

同様にハッシュ関数にコリジョン困難性の喪失に起因する内容でおもしろと思っ たのは、今回のカンファレンスの最後の最後で発表したものでした。

New Proofs for NMAC and HMAC: Security without Collision-Resistance Mihir Bellare

これはNMACやHMACはハッシュ関数を内部に使った使ったデータの改竄検出のた めの値(Message Authentification Code)を計算する方法です。MD5やSHA-1を 使ってSSH、SSL/TLS、IPsecなどに組み込まれています。この時に必要とする のはハッシュ関数の性質はコリジョン困難性ではなく疑似乱数関数(PRF: Pseudo Random Function)の性質を満たしていれば十分であることをこの論文 は証明しています。

筆者が段々とわかってきたのは、今までハッシュ関数に負わせてきたコリジョ ン困難性ハッシュ関数(CRHF)という能力と疑似乱数生成(PRF)の能力を本来は 別にわけるべきだなということです。Bellare論文でやっと示されたように、 今まではハッシュ関数という一言で終わらせていて、そこに必要なのはCRHFな のかPRFなのか区別する必要もなかったし、そのため明確化もされていません でした。

現存するハッシュ関数に関する分析技術が進み、CRHFを満たすための処理はか なり重い処理が必要になってきたことがわかる一方、PRFであればよいのであ れば軽い処理で済ませることができます。軽くてCRHFなものがあればハッピー ですが、そんなうまくはいかないでしょう。ですから、今後は重いCRHFと軽い PRFを使う使い分けをする方向に向かう可能性もあるというということです。 ただし2 つ使い分けるのは実装方面では面倒にはなるのです。たとえばICカー ド上では利用する基本アルゴリズムがひとつ増えるだけで大変です。

なかなかこの辺は次世代のハッシュ関数がどうなるかとも絡んできて難しい問 題です。

Invited Talk

今年の招待講演は次の2つです。

  • Lattice-Based Cryptography Oded Regev (Tel Aviv University, Israel)
  • Cryptograhic Protocols for Electronic Voting David Wagner (UC Berkeley,USA)

    Lattice-Based Cryptographyは、最も短いベクトルを見つける問題、the shortest vector problem (SVP)などに基づく計算量的に安全な公開鍵暗号アル ゴリズム群です。暗号に使われているタイプは計算量的には現在知られている 解き方では指数時間が必要な難しい(difficult)と考えられていますがNP困難 (NP-hard)ではないと考えられています。さて、公開鍵暗号として有名なRSAは 量子コンピュータができると現在2のO(n log log n/log n)乗という計算量が必 要なものが、O((log n)^2 * loglog n)で解けてしまいます。ですが、計算量的 に難しい問題は量子コンピュータを使っても難しい問題なので、よって、 Lattice-Basedの暗号は安全です。Oded Regevもそのあたりを強調していました。 理論的にはおもしろいと思う人はいるかも知れません(筆者はその面白さがわか りませんけれども)。そもそも筆者の回りでも、あまり興味を持つ人がいないの で、その意味ではLattice-Based Cryptography を俯瞰する形で話を聞くことは 滅多にないので、よかったはよかったかな、と思いました。ただし量子コン ピュータができた時の保険という意味で有用性があるかどうかは疑問です。な ぜならば、量子コンピュータを前提とした暗号アルゴリズムが既に提案されて いたりするからです。

    David Wagnerは暗号技術の問題よりも電子投票のダメダメさを痛烈に批判して いました。David Wagnerはバークレーで暗号だけではなく広く情報セキュリティ を教えている教員であるとともに、若手から中堅へと移る年代の最先端にいる 研究者です。また彼の研究チームには優秀な学生が集まっており、大体、大き なセキュリティのカンファレンスでは必ず論文が入っています。CRYPTOのカン ファレンスだけではなくUSENIX Securityなんかでもよく発表をしています。 アメリカの電子投票システムはいろいろ作られていて、かつ、使われ始めてい るんですが、とにかく暗号技術とかセキュリティという以前の問題としてかな りダメダメなようです。そのうち日本でもアメリカの惨澹たる内容を見ずに 「アメリカでもやっています」と宣伝して売り込み始めるメーカーがいるのだ ろうと思うとちょっと頭痛がしてきました。

    Crypto 2006 Rump Session

    今年のRump Sessionは、いまひとつでした。面白かったのは、Adi Shamirは、 USBポートの電力変化からPower Analysisを仕掛けるという研究の成果をさらっ と流して、こう結論づけます。「どうやってもあなたのPCを守ることはできな い」というのは普及品レベルのPCを使う限り、暗号解読はわりと簡単だという はその通りです。なんかミッション・インポッシブルでの小道具で使われそう なネタでね。

    あとちょっと当り前といえば当り前、でも実際にかなりヤバいというのが、 Daniel Bleichenbacherの鉛筆と紙でRSA署名の偽造する発表です。これは実装 時のRSAのパディング方法と検証の時に使う鍵パラメータ(公開鍵)eが3の時の コンビネーションの微妙な相互関係で、実際に紙と鉛筆で偽造できます。見て いて、思わず「ほぉーー」とつぶやきました。みごとなものです。言われれば 誰でもわかる。でも今まで誰も気がついていなかったという、ある意味、驚く べきことです。

    これはeを大きくとれば問題ないのですが、いくつかの実装ではeを3にできる ので、この問題の影響を受けます。ちなみに署名系でeのデフォルトが3である ようなものは筆者は知りません。この発表後、US-CERTでは9月5日づけで Vulnerability Note VU#845620 "Multiple RSA implementations fail to properly handle signatures"という脆弱性情報を出しました。ちなみに JPCERT/CCとIPAが共同管理で運営しているJVNでは JVNVU#845620 「複数の RSA 実装において署名が正しく検証されない脆弱性」 というので登録されています。 ちょっと前ならCNETあたりで「RSAに重大な欠陥」とか派手な見出しを出して いたことでしょう。今回はマスコミから注目されていなかったせいか静かなも のでした。

    2nd NIST Hash Workshop

    CRYPTO2006に引き続き行われた The Second Cryptographic Hash Workshop に参加しました。NICT (National Institute of Standard and Technology)が主催して いるこのワークショップは、今後ハッシュ関数をどうしていくのか議論をする ために開催しています。

    ハッシュ関数の性質

    ここではハッシュ関数と呼んでいますが、ここではハッシュ関数の頭の部分に 「暗号技術で使われる」という言葉があるものとして読んでください。広い意 味でのハッシュ関数とは「任意の長さの入力に対して、一定の長さの出力を行 う関数」です。一方、「暗号学的な意味においての」、あるいは「暗号技術で 使われる」とは古典的には次の性質を期待されています。

  • OWHF (One-Way Hash Function /一方向性ハッシュ関数)
  • CRHF (Collision Resistance Hash Function / 衝突困難ハッシュ関数)

    OWHFとは、ある入力xが与えれた場合、ハッシュ関数Hにより出力されるy から xを求めることが困難である性質です。

          H(x) = y        easy
          H^-1(y) =  x    hard
    

    CRHFとは、ある入力xが与えられた場合のハッシュ関数Hより出力されるyと同 じ値を持つ異なる入力x'を見つけることが困難である性質です。

          x != x' 
          H(x) !=  H(x')
    

    ちょっと繰り返しの説明になりますが、近年では、これだけではなくPRF (Pseudo Random Fuction)の性質も求められます。ランダムオラクルモデルと いう方法では入力に対してランダムな値を出力する関数が使われます。それに ハッシュ関数が使われています。近年、このPRF であるという性質をハッシュ 関数に求める状況というのが多くなっています。たとえばHMACというハッシュ 関数を利用したMAC (Message Authentic Code / 偽造されないかのチェックコー ド) の一種は1996年に提案されてた後、SSL、SSH など広く使われているシス テムに既に組み込まれています。現在はハッシュ関数を使っているが、この時 のハッシュ関数はCRHFの性質ではなくPRFの性質さえ満たしていれば十分です。

    求められるPRFである条件はCRHFよりも緩くなっています。別のいい方をする と、CRHFの処理関数の処理速度は、良くてPRFと同じか、それより処理が重い というわけです。現実的には今後は、軽いPRFを使うか、重いCRHFを使うかの 選択が迫られることになるでしょう。

    もちろんCRHFであればPRFであるし、RPFとおなじレベルで高速な処理が可能な 夢のようなCRHFがあれば別です。ただし、たぶんそれは難しいことでしょう。 今までのハッシュ関数といっていたものが、将来はニーズによって細分化され、 あと10年ぐらいするとPRFのことをオラクル関数とか撹乱化関数と呼び、ハッ シュ関数とは別扱いする時代になるかも知れません。

    そもそも、なぜ今ハッシュ?

    2003年頃から、暗号研究のコミュニティではハッシュ関数の安全性について研 究が進んでいました。BihamやJouxといった元気のいい優秀な暗号研究者がハッ シュ関数について集中的に研究を進めており、ハッシュ関数に関するいろいろ な性質や分析結果が出てきていた所でした。とはいえ、まだ現在主流となって いるハッシュ関数の安全性を完全に脅かすといったレベルまでは達しておらず、 将来的には現在のハッシュ関数を改定する必要はあるが、まだ、その時期は先 だろうと考えていました。わかり易くいえば、「あのような一流の連中を集め ても、まだ、このレベルしか達していないのだから、将来は改定する必要があ るとしてもハッシュ関数の寿命はまだまだ持つ。」という感じです。

    ところが2004年8月のCRYPTO2004で行われたランプセッションで、その状況は 一変しました。中国から来たまったく無名の女性研究者・ 王小雲 (XiaoyunWang) が画期的なハッシュ関数への攻撃法があると発表したのです。中国国内 では既に発表済みだったその論文は、ヨーロッパから中国の大学に戻ったRai によって見出され、 短いメモ書きのような英語の文章 として発表前日にIACR ePrintに投稿されました。

    新しいハッシュ関数に対する攻撃方法を開発し、その方法を使えば簡単にコリ ジョンを見つけることができたという内容で、BihamやJouxのようなレベルで すらできなかったことを既に成し遂げていました。王はLisa Yinと組み本格的 な論文を翌年のEUROCRYPTOやCRYPTO2005で次々に発表します。とうとう今まで 誰も手をつけることができなかった標準化ハッシュ関数SHA1に対する有効な攻 撃方法まで開発するに至りました(しかしまだ現実的な攻撃は成功していませ ん)。NISTは声明を出し、今後はSHA1ではなくSHA256 のような長い出力を持 つ関数を使うようにとするほどででした。

    本来、もっと先のはずであった次期ハッシュ関数の標準化スケジュールが、こ の突然現れた一人の中国人研究者によって早急に着手しなければならない事態 になってしまったのです。

    筆者は幸運にも、CRYPTO2004のランプセッションで王が発表する場面に立ち会 うことができました。あの日あの時の会場の緊張感と発表の終わった時の興奮 は、どんなに言葉を重ねようとも伝えることは無理でしょう。それをもって、 どれだけの衝撃的なものだったかを想像して欲しいです。いずれにしろ王の研 究が世界に知れることになり、ハッシュ関数の尻に火がついたことは間違いは ありません。

    だが大きな問題があります。ハッシュ関数に関して、我々は何を知っているの かということです。実は、あまり知っていることは多くはありません。たとえ ばHMAC で使うハッシュ関数はPRFで十分満たすことができるというような、あ る意味、基本的な証明ですら今回のCRYPTO2006で発表されたばかりです。

    ハッシュ関数の評価に必要なクライテリアすらも十分には持ってはいません。 現在では、その役割に大きなものを負わしている半面、深くその性質や分析方 法に関して我々は十分な知見を持っていないし、王の発表にしても、いくつか の部分で十分に公開していない情報があります。ちなみに、それを影では Chinese Trickと呼んでいたりします。

    ワークショップ概要

    木曜日の午前にCRYPTO2006が終了し、その午後と翌日土曜日の9時から5時まで 開催されるスケジュールでした。場所は同じくUCSBの大学構内のホールです。

    内容は、多角的にハッシュ関数を眺めることと、今後のNISTの次期ハッシュ関 数標準化をどうするか、という議論です。論文として発表されたもののレベル は玉石混合で、方向性としては深く内容を突っ込むより、広くハッシュ関数に 関する話題を集めるといった方がいいかも知れません。ただし中には「査読を しないという画期的な査読」「どこにも出せない論文の流れついた先」などと 批判する人もいたことも事実です。

    日本からは3本ほど発表がありました。NTT DATA の松尾氏がおこなった「実際 のハッシュがどのように組み込まれ使われているか」を、実際のシステムにお けるハッシュ関数への要求仕様とした角度からみて筆者は興味を持ちました。

    あとLisa Yinが発表したHMAC/NMACの分析内容が非常に興味深いものでした。 この発表によればコリジョンはHMAC/NMAC鍵を復元するのに有効なのだそうで す。しかもMD5やSHA0のようなSHA-1よりも弱いもを使った場合の方が結果とし て復元しにくいというパラドクスが発生するそうです(何で?)。

    その分析はまだまだ改良の余地があるようで、YinとBihamがこの発表の前日の 夜11 時にさらに有効な攻撃法を開発したとプレゼンテーションには書かれて いました。改訂版はNISTのサイトにアップデートされるとのことです。Yinや Biham は天才クラスなので別格ではありますが、しかし顔をあわせて1時間か2 時間話しただけで、このようなものが出てくるハッシュ関数の分野は、次に何 が出てくるかは筆者のような凡人には思いもつきません。

    ディスカッションのためのパネルは2つありました。初日のパネルは暗号研究 界の大御所を壇上にあげてのディスカッションでした。内容的には一般的な話 題に終止し、特に筆者がメモや記憶に残るような内容ではありませんでした。 1つ面白かったのは、「標準化として複数のハッシュを採用するかどうか」と いう時に、質問が終わるか終わらないうちにFergusonは「1つ!」と叫んでい たことです。これは実装側にとっては切実な問題なのでよく、その気持はわか ります。

    パネリスト:

  • Ron Rivest, Massachusetts Institute of Technology
  • Adi Shamir, Weizmann Institute of Science
  • Bart Preneel, Katholieke Universiteit Leuven
  • Antoine Joux, Saint-Quentin-en-Yvelines
  • Niels Ferguson, Microsoft
  • 最後のセッションでは、NISTが今後標準化ハッシュ関数を改定するスケジュー ル案の提示とそれに対するディスカッションです。NISTはコンセンサス重視の 姿勢を取っており(とある日本人研究者の言葉を借りると「みなさまあっての NISTです」)、みなさんの意見を採り入れるというスタンスを取っています。

    現在考えられているスケジュールは以下の通りです。

  • 2006/8 : (現在) 第二回ハッシュワークショップ

  • 2007: 第三回ハッシュワークショップ, 必要であれば第四回のハッシュワークショップも行う, ハッシュ関数コンペティションの公募・審査のための必要事項や, 評価基準などを作る

  • 一年目(2008?), 応募要項案・評価基準案作成, 最終案決定, 公募開始

  • 二年目(2009?), 応募されたものが応募要項に沿っているかをチェック, 第三四半期に第一回のハッシュ関数カンファレンス (the First Hash Function Candidate Conference)・一次審査へ進むアルゴリズムを選択

  • 三年目(2010?), 第一四半期に第二回ハッシュ関数カンファレンス, 第三四半期二次審査へ進むアルゴリズム(ファイナリスト)を選出

  • 四年目(2011?), 第二四半期に第三回ハッシュ関数カンファレンス, 第四四半期採択するハッシュ関数の発表

  • 五年目(2012?), 準化 (注)何かイベントがあるたびにNISTはパブリックコメントを求める体制にして いるが上記のリストの記述では繰り返しなので、割愛させてもらっている。
  • (追記)これは2006年8月時点においてのスケジュールであり、現在のスケジュールではない。現在のスケジュールは以下を参照すること。
  • http://www.csrc.nist.gov/pki/HashWorkshop/timeline.html
  • 来年2007年は、ハッシュ関数を選ぶにあたりどのような基準で行うかなどをま ず議論する年となります。もし必要であれば、後ろをずらすことも考えている ようです。ただし一度走り始めたスケジュールはなかなか止められないものな ので、今回の発表のスケジュールで進むでしょう。前回のAESの際は、どのよ うな基準で選ぶのかが最初わからないため、かなり不信感があったのは事実で す。あの頃は、世間には米国政府による陰謀論を信じて疑わない人達も見受け られました。最後は米国から提案されたものではなく、ヨーロッパから提案さ れたRijndael が選ばれたので陰謀論は一蹴されましたが、とはいえ、最初に 評価基準などを明確にすべきであった反省点はあります。今回は、そのあたり をきちんと詰めてから始めましょうということなのでしょう。

    おしまい

  • 20080306 バックトラック記録をみると、説明で抜けている部分とエラー の部分を教えてくれている人がいました。そこを加筆・校正しました。