next up previous contents
Next: III.3.3.2 AES候補に対する電力解析 Up: III.3.3 電力解析 Previous: III.3.3 電力解析

III.3.3.1 DESに対する電力解析

III.3.3.1.1 単純電力解析

本節では，Kocherら [KJJ98,KJJ99]が発表した単純電力解析について，彼らがスマートカードに対して実際に行った単純電力解析の原理と測定結果，および攻撃の有効性についてまとめる． 対処方法についてはIII.3.3.5.3.1節を参照のこと．

III.3.3.1.1.1 解析原理

スマートカードなどの耐タンパデバイスのほとんどはトランジスタで構成された論理回路からなり，ゲートに電圧が加えられたときに電流が流れ，電力が消費される．一般に回路の消費電力は，実行している演算と用いられているデータの値に関係する．例えば，乗法演算は0を書き込む場合よりも1を書き込む場合のほうが消費電力が大きくなり，乗法演算と平方演算ではそれぞれ異なる電力を消費する．これより秘密情報を用いた演算を行っているデバイスの消費電力の変化を観察することで，秘密情報に関してハミング重みなどの情報を得ることができ，エントロピーを小さくすることができる．消費電力の変化を直接解析に用いる方法を単純電力解析と呼ぶ．

III.3.3.1.1.2 測定

デバイスの消費電力は，デバイスと電源または接地との間に抵抗を直列に挿入し，抵抗を流れる電流値から求めることができる．実際にDESの演算を行っているスマートカードに対して消費電力測定を行うと，測定波形よりDESの16段の演算がはっきり確かめられる．さらに，消費電力波形を詳しく解析することにより鍵レジスタの交換等の情報を得ることができる．

III.3.3.1.1.3 評価

このように単純電力解析はデバイスが実行している一連の演算を反映するため，例えば次のような演算から情報を得ることができる．

鍵スケジュール
DESの鍵生成部では各段においてビットシフトを行う．このときシフトされる鍵のビットが"0"か"1"かで電流がそれぞれ異なる経路を流れる場合，消費電力の違いから単純電力解析が有効となる．
転置
DESのアルゴリズムでは多くの置換が行われる．置換されるデータによって置換アルゴリズムが異なる場合，置換時の消費電力の違いから情報を得ることができる．
比較
記号列や数値の比較を行ってミスマッチが生じた時，条件分岐がしばしば起きる．このような条件分岐は消費電力の大きな違いとなって外から観察可能である．
乗算
乗法剰余演算回路は演算するデータについて，非常に多くの情報を外に漏らす．具体的にそれがどのような消費電力の変化となるかは回路構成によるが，オペランド値やハミング重みなどの情報が得られることが知られている．
冪乗演算
単純な冪乗剰余演算は冪指数を上位桁から順にスキャンしていき，ビット値が"1"のとき乗算を行いながら平方演算を繰り返す．もし，平方演算と乗法演算がそれぞれ異なる電力を消費したり，異なる計算時間をとったり，異なる計算回路を用いる場合，冪指数についての情報を得ることができる．

III.3.3.1.2 電力差分解析

本節では，Kocherら [KJJ98,KJJ99]が発表した電力差分解析について解析の原理，詳細，測定例，解析の改善法についてまとめる． 対処方法についてはIII.3.3.5.3.1節を参照されたい．

III.3.3.1.2.1 解析原理

耐タンパデバイスの消費電力は一般に演算内容と演算に用いられている秘密情報に依存する．しかしこれらの内容に依存した消費電力の変化は小さく，測定誤差やノイズなどから見分けることは一般に困難である．

そこでKocherらは大量の測定値の平均をとって測定誤差やノイズなどの影響を小さくし，全データの平均値との差分を取ることで演算プロセスによる電力消費の影響を除いて，用いられる秘密情報による消費電力の変化のみを取り出す方法(電力差分解析)を提案した．

彼らはDESに対する適用例を示している．まず，第1段(または第16段)に入る鍵の一部のビットについて予想し，第1段(または第16段)の最後にメモリに書きこまれる(と予想される)データの1ビットの値に注目して，その値に従って消費電力の観測データを分類する．次にそれぞれのグループについて測定値の平均をとり，それらの差分をとる．予想が正しい場合注目したビットが演算に用いられるとき消費電力の差分が大きくなる．予想が異なる場合目立った差分は確認されない．

III.3.3.1.2.2 解析の詳細

  1. $m$ 回暗号化プロセスを観測し，それぞれ第16段の消費電力の変化 $T_{1}, \cdots, T_{m}$ を観測する．さらに，暗号文 $C_{1}, \cdots, C_{m}$ を記録する．第16段の消費電力の変化を解析に用いる場合，平文の情報は必要ない．なお， $m$ は $1000$ 程度で十分である．
  2. 鍵に依存した分配関数 $D(K_{s}, C)$ を選択する．ただし， $K_{s}$ は何らかの鍵情報， $C$ は暗号文である．例えば，最終段のSボックス1の出力の，1ビット目の値に着目し，Sボックス1に供給される6ビットの部分鍵を推定する場合を考える．この場合，関数 $D$ は次式で与えられる．

    \begin{displaymath}%\begin{equation}D(C_{1}, C_{6}, K_{16}) = C_{1} \oplus SBOX_{1} (C_{6} \oplus K_{16}) \end{displaymath}

    ただし $K_{16}$ は第16段にSボックス1に供給される6ビットの部分鍵の予想値， $C_{6}$ は $K_{16}$ とXORされる暗号文の6ビット， $SBOX_{1} (x)$ はSボックス1に6ビット $x$ が供給された場合の出力結果の1ビット目， $C_{1}$ は ${\rm SBOX}_{1}$の出力結果にXORされる暗号文の1ビットである．
  3. 関数 $D$ を用いて $T_{1}, \cdots, T_{m}$ を2つのグループに分ける:

    \begin{eqnarray*} S_{0} &=& \{ T_{i} \vert D(\cdot, \cdot, \cdot) = 0 \} \\ S_{1} &=& \{ T_{i} \vert D(\cdot, \cdot, \cdot) = 1 \} \end{eqnarray*}



    次に，それぞれのグループについて消費電力の平均値を取る．

    \begin{eqnarray*} A_{0} &=& \frac{1}{\vert S_{0}\vert} \sum_{T_{i} \in S_{0}} T_... ..._{1} &=& \frac{1}{\vert S_{1}\vert} \sum_{T_{i} \in S_{1}} T_{i} \end{eqnarray*}



    ただし， $\vert S_{0}\vert + \vert S_{1}\vert = m$ である．
  4. $A_{0}$ と $A_{1}$ の差分をとり，電力差分信号 $\Delta_{D}$ を得る．

    \begin{displaymath}%\begin{equation}\Delta_{D} = A_{0} - A_{1} \end{displaymath}

  5. 部分鍵の予想値 $K_{s}$ が正しくない場合， $D(\cdot, \cdot, \cdot)$ は暗号文に対してほぼランダムに"0"と"1"を出力する．従って十分多くのサンプルを取ると $\Delta_{D}$ の値は0に近づいていく．(実際には正しい予想値 $K_{s}$ との相互作用のため， $\Delta_{D}$ の波形は完全にはフラットにならない．) $K_{s}$ が正しい場合は， $D(\cdot, \cdot, \cdot)$ は注目したビットの実際の値と同じ値を取るため， $m \to \infty$ とすることで $\Delta_{D}$ は注目したビットを用いるときに消費する電力に近づいていく．他のデータ値や測定誤差など $D(\cdot, \cdot, \cdot)$ に依存しないものは0に近づいていく．消費電力はデータのビット値に依存するため， $D(\cdot, \cdot, \cdot)$ の波形は注目したビットが用いられる領域でパルスを見せ，それ以外の領域では平坦になる．
  6. 以上を繰り返し，Sボックス1に供給される部分鍵を推定する．反復の最大値は $2^6 = 64$ 回である．
  7. 同様の作業を残り7つのSボックスについて行い，秘密鍵について48ビットの情報を得る．残りの8ビットの鍵情報は全探索によって求める．

III.3.3.1.2.3 高次電力差分解析

ここで高次電力差分解析について解説する．

上に述べた電力差分解析はサンプルの一つのイベントに基づいた情報に対して解析を行っているが，高次電力差分解析は複数のイベントに基づいた情報を関連付けて解析に用いる．分配関数 $D$ はサンプルごとにそれぞれ異なる重み付けをしたり，2つ以上のグループ分けをしたりすることができる．そのような関数は多くの防御策を封じ，平文や暗号文の情報が不完全な場合でも解析が可能な場合がある．また，特徴的な統計的性質を持つサンプルに対しては，単純に平均をとるのではなく別の処理を行うことが有効である．

next up previous contents
Next: III.3.3.2 AES候補に対する電力解析 Up: III.3.3 電力解析 Previous: III.3.3 電力解析