next up previous contents
Next: III.3.2.2 タイミング解析の適用例 Up: III.3.2 タイミング解析 Previous: III.3.2 タイミング解析


III.3.2.1 タイミング解析の原理

タイミング解析は,暗号化の処理時間が秘密鍵データに依存して異なるとき, その差を統計的に解析して秘密情報を推定する攻撃法である. 1996年にKocherによってそのアイディアが発表され,同時に Diffie-Hellman [DH76],RSA [RSA78] などのべき乗剰余算, 中国剰余定理を用いたRSA,さらにDSS (Digital Signature Standard)に ついての攻撃法の原理が提案された[Koc96].その後,タイミング解析に よって実際に秘密情報を推定した報告もなされている [DK+98].

タイミング解析は,暗号アルゴリズム自体ではなく,スマートカードへの 不注意な実装方法に対して行われる攻撃法である. 暗号アルゴリズムを実装する場合,処理時間の短縮やプログラムサイズの 縮小を狙って,処理の最適化を行うことが多い.最適化とは,例えばデータのある ビットが1であるか0であるかによって,行う必要のない処理をスキップしたり, 分岐して異なる処理を行ったりすることである. このような方法で実装すると処理時間が データに依存して異なってくる.そのため処理時間を見ることで秘密情報を 推定することができる.これがタイミング解析の原理である.

タイミング解析を行う上で,次の仮定をおく.

上のような状況のとき,攻撃は次のように行われる.

  1. 実装アルゴリズム中で,処理時間差を生じる部分のうち1ヶ所に注目する.
  2. 計測できるのは暗号化全体の時間だけなので,注目した部分以外の 時間差が(統計的に)無視できるまでの量のメッセージ(平文)を入力し, 暗号化の処理時間を計測する.
  3. その計測データから秘密鍵情報を推定する.

III.3.2.2節以降で,現在までに報告されている各暗号方式への適用例を述べる.