CRYPTO 99 訪問記すずきひろのぶ hironobu@h2np.net 本文はSoftware Designに書いた原稿をWeb Publication用に公開したものです。 CRYPTO99は、毎年8月に米国カリフォルニア州サンタバーバラ市にあるカリフォ ルニア州立サンタバーバラ校(UCSB)で行なわれる国際暗号学会(IACR)主催の暗 号学会です。今年は8月15日から19日が開催期間でした。 アメリカの夏休みは、卒業生を送りだし、新入生を迎える静かな時期にあたり ます。CryptoはUCSBの夏休みで空いた施設を使って行うのでいつも同じ季節に 行なわれます。 IACRはヨーロッパ地域で開催するEUROCRYPTO、アジア地域で開催する ASIACRYPTO、そしてアメリカで開催するCRYPTOの3つの大きなカンファレンス を開催しています。その中で最も参加者が多いのがコンピュータ産業の中心地 アメリカ西海岸で開催されるこのCRYPTO99です。 開催地のサンタバーバラという場所は、ロサンゼルスから1号線を北へ約 100マイルほどいった所にあります。いつもはロサンゼルス空港からレンタカー を借りて運転しているのですが、たまにはちがったコースもいいだろうという ことで、今年はサンフランシスコ空港からシャトル便と呼ばれる国内の地方空 港を結ぶを使ってサンタバーバラまで移動しました。サンタバーバラ空港は広 い滑走路にぽつんと小さな平屋のオフィスがあるだけのまるでバスターミナル のような空港です。 サンタバーバラはアメリカ西海岸地域では有名な高級別荘地として知られ、地 元広報誌の言葉を借りると「アメリカにある(ヨーロッパの高級リゾート地と して知られる)リビエラ」だそうです。たしかに沖に流れる寒流の関係で夏で もさほど気温はあがらず夜は長袖のトレーナーが必要なほどで、冬は逆にそん なに気温も下がらないという非常に理想的な気候の地域です。筆者は仕事のス ケジュールの関係で残念ながらこのCryptoだけ出席して日本にすぐ戻らなけれ ばいけませんが、もし時間が許すなら、ここで1、2週間ほどゆったりと休暇を 取ってみたいものです。 UCSBのキャンパスはサンタバーバラ市内から約10マイルほど離れた海岸沿いに あります。目の前に広がる美しい海原は大学にやってきたというよりも何かリ ゾート地に来たような錯覚さえします。もちろんキャンパスはアメリカの大学 らしく広々としており、キャンパス内にラグーン(海の一部が隔離された湖)を 持つほどです。Cryoto99の期間中、参加者は大学のドミトリー(宿舎)に宿泊し 食事は大学の学食で取ります。 参加者は約490名で、約5割弱がアメリカですが、残りの半分は世界中から集まっ ています。国別参加者(主催者発表)のトップ10は次のようになっています。
Cryptoが行なわれる前後の期間は、北米で色々なセキュリティ関連のカンファ レンスが連続して行なわれています。暗号関係者の場合、この前の週に東海岸 側でカナダのトロントとボストンで開かれている暗号に関連した2つのカンファ レンスをこなし北米を縦断して西海岸のCryptoに参加するパターンになります。 一方、コンピュータセキュリティ関係者だと次の週にワシントンDCで行なわれ るコンピュータセキュリティのカンファレンスのために東海岸へと飛ぶパター ンになります。セキュリティ関連の研究者はこの時期、西海岸に飛んだり、東 海岸に飛んだり慌ただしく移動する期間でもあります。 ちょっと真面目な話ここから先は真面目な話をしましょう。最先端の暗号研究とはどんなものなの か、ちょっと触れてみることにしよう。暗号の基礎理論分野というのは、たぶ ん多くの皆さんが抱いているコンピュータの応用分野というイメージとは違い、 むしろ数学の応用の分野の1つと考えた方がいいかも知れません。私は数のマ ジックの1つだと思っています。今回のCrypto99でどのような内容を行ったかざっと流れを説明します。今年の 場合、恒例の2つ招待講演を含む、8つの細分化したセクションが設定されてい ます。 招待講演2つの招待講演は、1つは最先端理論の研究者を招いてのオーバービュー的なレ クチャーをしてくれるもの、もう1つは過去の暗号研究の歴史に大きな足跡を 残した偉人が歴史や周辺的な話をしてくれるものです。ここ何年かで私が面白 いと思ったのは97年のGilles Brassardによる量子情報処理研究のレクチャー でした。量子力学の不確定性の特性を使って暗号通信を行うという理論がある のですが、(97年当時は)参考文献もあまりなくオーバービュー的な話を聞くと いうのはこれが最初でしたし、興味深いポイントがいくつもあってなかなかオ トクな気分になったものです。今年99年は、Ueli Maurerによる情報理論に基 づく暗号のレクチャーでした。RC5やDESの解読コンテストで既におなじみになっていると思いますが、現在、 コンピュータで使っている暗号の安全性は第三者が解読しようとすると膨大な 計算量が必要となるという「計算量に基づく安全性」によって保たれています。 ところが情報理論に基づく暗号も、先の量子力学に基づく暗号も、無条件に安 全な(このことをUnconditional Securecyといいます)、つまりどんなことをし ても解読することは不可能な絶対的な暗号なのです。理論は理論としてあるの ですが、実用的なシステムを作るとなるとまだまだ先の話になるでしょう。 偉人たちのレクチャーは、今年は公開鍵暗号の理論を作ったMartin Hellmanで した。もう1人の共同研究者であったWhitfield Diffieも当然会場にます。今 日的暗号の世界が幕をきって落したのがつい最近なので、これらの偉人と呼ば れる人達も実はそんなに年は取っていません。彼らの多くはベビーブーマー世 代、ベトナム反戦の世代、また、政府を決して信用しない世代でもあります。 私が聞いた中で一番面白かったのは97年(だと記憶していますが、間違ってい たらごめんなさい)に行ったAdi Shamirのレクチャーでした。ShamirはRSA暗号 を考案した1人です。RSA暗号を考案した当時はMITに暗号の研究者としてでは なくアルゴリズムの先生として招かれてました(現在は、イスラエルの大学に 戻っています)。RSAの論文を発表しようとしたらNSA(国家安全保安局/アメリ カのいわゆる諜報組織)から圧力がかかったて、中断したという話が広く知ら れていました。それは尾ひれのついた噂かも知れないと私は思っていたのです が、実は紛れもない事実だったのです。「これがNSAから送られてきた有名な 手紙です」とShamirは、NSAから送られてきた証拠の手紙をOHPに映し出しまし た(このようにいずれ悪は露見するものです)。Shamirが言うにはNSAは後に 「その手紙はNSAに勤める一個人が懸念を表明したものでNSAは一切関知してい ない」と表明したそうです。なんか安物のTVドラマか何かに出て来るありがち なトカゲの尻尾切りみたいなことをするものですね。 発表のトレンドさて発表セクションですが、これは近年のトレンドにあわせてどんどん変更さ れています。このセクションの取り方を見ているだけで、暗号研究のトレンド がよくわかります。今年はこんなセクション分けをしていました。
この中からいくつか面白いと思ったものを取り上げて簡単に解説してみましょ う。 数学と暗号の境界公開鍵暗号に対する暗号分析で最も興味を引かれたのは次の発表でした。
Factoring N = p^r q for Large r RSAタイプの暗号は、2つの大きな素数をかけて作った数を素因数分解をする には莫大な計算量が必要であるということを安全性の寄りどころとしています。 ただし大きな素数同士(pとq)をそのまま計算すると、暗号化や復号化に時間が かかるのでpをr乗の形にしたのものを使って(N = p^r q) 計算を高速化させま す。これはNTTのお家芸ともいえる計算手法で例えばESIGN電子署名方法や最近 発表したEPOCなどはN=p^2 qの形を取っています。 ところがp^rの形を取る時、rが大きくなっていくと段々と素因数分解が簡単に なっていき最後には、あっというまに素因数分解ができてしまうことになって しまうという特性があるということを発見したというのがこの論文です。この 研究自体がやっていることは数がどのような振舞いをするかを調べる数学の世 界の話題に分類できますが、そのモチベーションは暗号の安全性にむすびつい ています。結論はN=p^r q の時、√log p よりも大きいrの場合、素因数分解 が簡単になってしまうこと、もしN=p^r qの形式を使って計算を高速化する場 合、pの桁数とrの桁数を慎重に選ぶことです。 スマートカードは危険？インパクトを与える話としては、やはり次の発表でしょう。
Differential Power Analysis Power Analysisとは、組み込み暗号ハードウェアが暗号処理を行う時に発生す る電力消費量などをモニターして、そこから暗号を解読する、あるいは組み込 んである鍵を見つけるという方法です。ここ数年のトレンドでしたが、今まで は組込み暗号チップやメモリといえば、特別なシステムに組み込む専用ハード ウェアのような特殊なハードウェアと解読を行うための作業環境を必要として いました。理論的には可能でも、実際の脅威からは程遠いものでした。 最近ではスマートカードのようにICカードの中に暗号の機能を組み込んでいて 身近なものとなりつつあります。スマートカードは暗号テクノロジーを組み込 んでいるから安全だと考えられており、今後、爆発的な普及の兆しを見せてい ます。 この論文ではそのようスマートカードで実行される暗号処理の電力消費パター ンを解析することは簡単であることを示しました。スマートカードにアナライ ザーをつけてスマートカードを実行させます。そもそもスマートカードの処理 速度(クロックサイクル)は遅いので非常に分かりやすく、はっきりモニタでき ます。最近の研究ではアルゴリズム側では、このようなPower Analysisを防ぐ のは非常に難しいということが段々とわかってきています。 今のクレジットカードのようにプラスチックに磁気テープだけの安全性の低い ものから、安全性の高いスマートカードへ切り替わろうとするのトレンドです。 フランスに至っては国がスマートカードを使うように指導しています。所が、 その安全性の高いはずだったスマートカードは、実は、スマートカードを使う とせっかくの暗号アルゴリズムも台無しになるほど弱いものだったことが今回 の論文ではっきりしてきました。プラスチックに磁気テープのカードよりはマ シですが、スマートカードは本来考えていたほどの安全性ではないということ です。 ちなみに、この研究を行ったCryptographic Research社の研究グループはDES Challenge IIIの際に使ったDES解読専用チップを作った人達で、この手の具体 的な分析が非常に得意です。それだけに机上だけの理論ではなく、インパクト もその分大きいと思われます。 NSAが作った暗号はもうボロボロかつてNSAが作って国民に押しつけようとしたSkipjackは、実は、かなり程度 の低い暗号だということが段々とわかってきました。ここ1年程、世界中のトッ プ中のトップである暗号学者が集中的にSkipjackをターゲットに暗号分析を行っ ています。
Truncated Differentials and Skipjack この1年前にShamirとEri BihamらがSkipjackへのアタックの口火を切ったの ははじまりです。今やShamir、Biham、Kundsen、Robshaw、Wagnerというトッ プクラスがSkipjackをターゲットにしています。たぶん、あと1年ぐらいは続々 と続くでしょう。 さて、Skipjackはラウンドと呼ぶデータをかき混ぜる手順が32回あるのですが、 この途中の16回分を抜きだして分析してみると、ほとんどかき混ぜられてい ない状態にあるという非常におかしい結果が出ています。前半の16回分では 2^17の暗号文と平文の組合せがあれば解読可能となっている所まで現在の研究 は進んでいます。 この調子で分析が進めば、近年中にSkipjackは完全に分析されることになるで しょう。私の友人の暗号研究者は以前、Skipjackを指して「デザインが中途半 端でやっつけ仕事的な印象」と言っていました。どうやらそれは本当のようで す。 Skipjackはアメリカ国防総省内で実際に使われているDefense Message System (情報伝達システム)や他のシステムでも使用されている暗号カードFORTEZZAに 組み込まれて使われています。つまり、アメリカ国防総省のメッセージシステ ムで使っている暗号は、現在AESとして選ぼうとしているいくつもの民生品の 暗号より、かなり弱くて問題のある暗号を使っているということになります。 この論文は、情報分野の民生品レベルが世界最大最強であるはずのアメリカ合 衆国の軍隊レベルをどんどん越えていっているという現実を示している非常に 興味深いものだと言えるでしょう。 おわりに今年は西海岸についたとたんに熱を出してしまい、座って発表を聞いているだ けでもかなり苦しい思いをしました。みなさんも夏風邪には注意しましょう。 |