現在利用されている公開鍵暗号のほとんどはRSA暗号方式であると言っても過言ではないが、標準化がされている公開鍵暗号の方式は他にも存在する。特に楕円曲線暗号（ECC）は同レベルの強度を持つRSA暗号と比較して鍵長が短いことに加え処理の速さも特徴となっていることからポストRSA暗号として注目を浴びている。
　本技術調査では2010年上期に「楕円曲線暗号の整備動向」を報告した[1]。ECCはWindowsのCNG（Cryptography Next Generation）や、著名な暗号ライブラリ・SSL/TLSミドルウェアであるOpenSSLといった、広く使われるプラットフォームで採用がされている。また7月に正式公開されたJava Platform SE（Standard Edition）7ではJCE（Java Cryptographic Extension）プロバイダでECCに対応するなど利用プラットフォーム整備が進んでいる。
　ECCは単一の暗号アルゴリズムではなく、楕円曲線上の離散対数問題を安全性の根拠とする暗号方式の総称である。そこには、楕円曲線上でDH（Diffie-Hellman）鍵共有を行うECDHや楕円曲線上でDSA（Digital Signature Algorithm）を実現するECDSA、楕円曲線上でMQV（Menezes-Qu-Vanstone）方式を実現するECMQVなどが含まれる。
　2011年5月にECCの代表的電子署名方式であるECDSAについて、OpenSSLの実装に脆弱性があることが報告された[2][3]。OpenSSLはさまざまなシステムで利用されているため脆弱性が発見されるとその影響が大きい。しかし2011年7月29日現在、この脆弱性対応は行われていない。
　本調査ではこの脆弱性の概要と脆弱性を利用した攻撃の現実的な脅威について報告し、利用者がOpenSSLでECCを利用するための判断材料を提供することを目的とする。

　ECDSAの署名生成では最初にランダムな値を生成する。これをnonceと呼ぶ。そのnonceとプライベート鍵、署名対象データを用いて署名生成を行う。nonceが漏えいすると署名データから簡単な演算で容易にプライベート鍵の計算が可能になるため、nonceの保護もプライベート鍵の保護には重要となる。
　ECDSAの署名計算時には楕円曲線上の点を整数倍する演算（スカラ倍算）が行われる。その演算方法は、利用される楕円曲線などの特徴を利用した個別の効率の良い演算方法が存在している。米国国立標準技術研究所（NIST）やIETF（Internet Engineering Task Force）、SECG (The Standards for Efficient Cryptography Group) で標準化されている楕円曲線パラメータは楕円曲線を構成する有限体の標数によりふたつに大別される。ひとつは標数に大きな素数を用いる素体上の楕円曲線と、もうひとつは標数に2を用いてその拡大体上で構成する楕円曲線である。OpenSSLでは、この素体と標数2の拡大体でスカラ倍算の演算構成が異なっており、この脆弱性は2の拡大体を用いた曲線の演算実装に存在する（図1）。

図1

　OpenSSLでは2の拡大体を用いた曲線のスカラ倍算にモンゴメリ梯子算 （Montgomery's Ladder）が採用されており、その実装ではnonceデータ上位何ビット目に初めて1が表れるかという情報をもとに演算が行なわれている部分が存在する。そこは、nonceの値に従ってわずかながら内部演算の回数が変わるようになっており、その結果演算処理時間が異なってくる。おそらく無駄な内部演算の回数を削減することで演算の効率を高めるための処理だと思われるが、この処理時間の異なりが脆弱性を生むことになっている。署名生成の演算処理を計測しておくことで、nonce情報の一部を取得可能になり、nonce値を取得可能なタイミング攻撃を可能にしてしまう脆弱性となる（図2）。この脆弱性は2011年5月にBrumleyとTuveriによって指摘がされた[2]。

図2

　暗号演算等を行うソフトウェア・ハードウェアにおいてその動作を観測することで暗号で用いられる機密情報を得る攻撃はサイドチャネル攻撃と呼ばれ、タイミング攻撃はその攻撃の一種である。

　攻撃は「署名データの収集」と「プライベート鍵の解析」のふたつから構成される。
　「署名データの収集」では攻撃者は署名生成をする機器の署名データとその処理時間を観測する。そして署名データを多く集め、その中で署名時間が少ないものを一定数抽出する。「プライベート鍵の解析」では抽出された署名データを変換し、Lattice攻撃と呼ばれる攻撃を実施する。
　「署名データの収集」時に行なわれる処理時間の観測には、直接CPUクロックを見て処理時間が観測可能な場合はその処理時間を測定する。
　直接観測が不可能な場合には、SSL/TLSのクライアントとしてSSL/TLSのハンドシェイクにおけるCllientHello送信開始からServerKeyExchange受領までの時間を計測する。ServerKeyExchangeには署名生成がされたデータが入るために、nonce値によって処理時間が変化することから間接的な計測が可能となる（図3）。
　一方「プライベート鍵の解析」は観測環境に依存せず攻撃者の任意の環境で実施が可能である。

図3

　脆弱性発見者らは楕円曲線パラメータB-163を用いて攻撃実験を行った。「署名データの収集」は以下の3つのケースで実験が行なわれた。
 　(1)　署名生成機器のプロセスレベルまで観測可能な状態での直接観測
 　(2)　署名生成機器をSSL/TLSサーバ・クライアントとして間接観測
 　(3)　署名生成機器とスイッチで接続された機器による間接観測

　脆弱性発見者らの実験結果では上記2の環境で16384個の署名データを集めるまで数分という結果が得られている。観測と署名データ収集後のLattice攻撃に関する詳細な攻撃時間の評価は行なわれていないが、あるケースでは数分で完了したものがあるとしている。

　脆弱性発見者らが論文[2] 上で示している攻撃の実験環境は、ネットワークを介しているとしているが1台スイッチを介してSSL/TLSハンドシェイクをしているもので、リモート接続としては通信の距離が短く通信遅延が非常に少なく、攻撃者に有利な環境であると言える。しかしその環境においても既に通信遅延やその誤差による判定ミスがおこっている。つまり、攻撃者に有利なリモート接続環境であっても、nonceの処理時間の差が非常に小さいために通信の遅延や誤差によりその差が攻撃者から明確に判断することが難しくなっている。
　より一般的な攻撃環境である、他のネットワークからの攻撃を想定すると、通信の影響による誤差はより高くなることは容易に考えられ、処理時間の差異は通信時間の遅延誤差に埋没してしまい攻撃が失敗する可能性が高いと考えられる。
　また、本攻撃は2の拡大体上の曲線パラメータを選択したときの脅威であり、素体のパラメータを用いれば攻撃は回避可能である。さらに、Windows環境では2の拡大体上の曲線パラメータは対応していない。
　これらのことから、2の拡大体上の曲線パラメータを選択したとしても攻撃成功率は低いと予想され、さらにECCによる暗号システム設計時や移行時に素体の曲線パラメータを選択すれば攻撃は回避可能であることから、現実的な脅威は低いと言える。

以上