next up previous contents
Next: III.3.3.3 RSAに対する電力解析 Up: III.3.3 電力解析 Previous: III.3.3.1 DESに対する電力解析

III.3.3.2 AES候補に対する電力解析

本節では，AES候補に対する電力解析の解析原理， 各AES候補に対する適用例について解説する[BS99,CJ+99a,DR99]． 対処方法についてはIII.3.3.5.3.2節を参照されたい．

III.3.3.2.1 解析原理

スマートカード等の耐タンパデバイスに対する電力解析である単純電力解析 と電力差分解析は，Kocherにより提案され[KJJ98]，非常に強力な攻撃法と して注目を集めている．攻撃者は，暗号化処理やデータ処理時におけるスマー トカード内の消費電力を観測することにより，スマートカードの内部情報を取 り出す．これらの攻撃法はDES (Data Encryption Standard)にも適用できるこ とから，スマートカードを用いた多くのアプリケーションにとって大きな脅威 となり得る．

単純電力解析について，Kocherが提案した攻撃法では攻撃者は全ての入力値ま たは出力値を必要とする．しかし現実のアプリケーションを考慮した場合，攻 撃者が全ての入力値または出力値を知ることはほぼ不可能であるので，この攻 撃法は現実的ではない．しかし，入力値または出力値に関する情報を得る必要 がない攻撃法[BS99] も提案されている．以下にその具体的な攻撃法を示 す．なお，解析の対象となるプロトコルについて，プロトコル内のサブプロト コルは同一の順序で実行され，プロトコルの実行に要するクロックサイクルが 常に一定であると仮定する．

攻撃者の第一目標は，得られた電力消費グラフの中で鍵スケジュール部に関係 する部分を特定することであり，その攻撃は二つのステップに分けられる．

ステップ1:
単一のスマートカードを用いて，入力項目を変化させプ ロトコルを多数回実行する．(入力項目の変化とは，例えば，支払い金額や支 払い回数を変えることであり，実際の入力値を知る必要はない．)得られた複 数の電力消費グラフ間の同一サイクルを比較し，電力消費値に大きなばらつき が存在するサイクルを鍵スケジュール部に関係しないサイクルとして除外する． これは，単一のスマートカードにおいて，鍵スケジュールは同一であり，鍵ス ケジュール部に関係するサイクルにおける電力消費値は入力項目に依存しない からである．
ステップ2:
ステップ1で行った比較を複数のスマートカードに対して 行う．ステップ1で絞り込まれたサイクルにおいて，得られた複数の電力消費 グラフ間の同一サイクルを比較し，電力消費値のばらつきが小さいサイクルを 鍵スケジュール部に関係しないサイクルとして除外する．これは，各スマート カードにおいて，鍵スケジュールは異なると考えられ，鍵スケジュール部に関 係するサイクルにおける電力消費値はスマートカード毎に異なるからである．

鍵スケジュール部に関係するサイクルを特定する際に問題となるのは，鍵スケ ジュール部に関係するサイクル候補として，莫大なサイクル数の中から上述の 攻撃が可能な程度のサイクル数にどうやって絞り込むかということである．し かし，例えばDESでは，16のラウンドがほぼ認識可能なので，これはそれほど 重大な問題ではないと思われる．

攻撃者の第二(最終)目標は，上述の攻撃により特定したサイクルから秘密鍵を 取り出すことである．スマートカードは，その性能上，全てのサブ鍵をRAMに 保持しておくことは困難であるので，暗号化処理において各サブ鍵は用いられ る直前にそれぞれRAMへ書き込まれる．書き込み処理時における電力消費量は， "1"を書き込んだ回数に関係するので，サブ鍵の書き込み処理時の電力消費 量からサブ鍵に含まれる"1"の個数が判明する．つまり，サブ鍵の書き込み 処理時の電力消費量を観測することにより，サブ鍵のハミング重みが計測され る．8ビットのハミング重み計測一回当たり平均2.54ビットの情報が取り出さ れる．このハミング重み計測には，多くの誤りが含まれている可能性があるが， 単一のスマートカード(同一の秘密鍵)での消費電力観測を多くの回数行い，平 均化することで誤りを減少させることができる．

秘密鍵の取り出しについて，話を具体的にするためDESの場合を取り上げる． DESは56ビットの秘密鍵，16のラウンドを持ち，ラウンド $n~(n=1,2,\ldots,16)$において，48ビットの秘密鍵$K_n$は6ビットのサブ鍵 に分割される．(各ラウンドにおいて生成されるサブ鍵の数は8である．)一度 にスマートカード内のRAMへ書き込む単位を8ビットと仮定すると，RAMに保持 される8ビットのハミング重み計測を各ラウンドにつき6回行うことができる． つまり，攻撃者は16ラウンドにわたるサブ鍵のハミング重み計測により，秘密 鍵の各ビットを変数とする(56変数の) 96個の線形方程式を得ることができる． 得られた方程式を解くことにより56の変数の値，つまり秘密鍵が判明する．こ の攻撃法の問題点として，得られた方程式の解が不定になる可能性が存在する ことと，ハミング重み計測誤りを効率良く検出することが挙げられるが，前者 について，DESの構造上，得られた方程式の解は唯一解であり，後者について， 例えば以下の二つの方法が考えられる．

電力差分解析は，算術演算や論理演算等の処理において，スマートカードの消 費電力パターンと入力ビットに何らかの相関があることを利用した電力解析攻 撃である．簡単化のため，入力$n$ビット $(op_1,op_2,\ldots,op_n)$の中で $op_1$が処理$I$における消費電力$P_I$と相関を持つとする．$op_1$の値によ り処理$I$における消費電力は次式で表される．

\begin{eqnarray*} P_I(0) &=& E_{op_2,\ldots,op_n}[P(I,0,op_2,\ldots,op_n)] \\ P_I(1) &=& E_{op_2,\ldots,op_n}[P(I,1,op_2,\ldots,op_n)] \end{eqnarray*}



ここで， $E_{op_2,\ldots,op_n}$は$op_1$以外の入力 $op_2,\ldots,op_n$を全 通り入力したときの平均である．処理$I$における消費電力$P_I$と$op_1$が相 関を持つとは，言い換えると， $P_I(0) \neq P_I(1)$である．以下， $D=P_I(0)-P_I(1)$とする．$D$が雑音に比べて十分大きい場合，電力差分解析 は非常に強力な攻撃となる．

基本的に電力差分解析は以下の三つのステップに分けられる．

ターゲット指定
III.3.3.2.1.1節に挙げた処理 の内で，あるサイクルの，ある処理に注目する．始めに，スマートカード内の 秘密鍵の予想値$K$を設定する．次に，入力値の$a$ビット目のみ変えた場合の 消費電力値の差$D_a$を計算する．$D_a$が大きい入力値を攻撃に用いる．
データ収集
様々な入力値を用いて 消費電力パターンのサンプルを多数入手する．
データ解析
入力値の$a$ビット目が"0"のグループと "1"のグループをそれぞれ，$G_0, G_1$とし，二番目のステップで得られた 消費電力パターンを$G_0, G_1$に分類する．$G_i~(i=0,1)$に含まれる各サン プルでの消費電力値の和を$P_{G_i}$とすると， $\vert P_{G_0} - P_{G_1}\vert$を最大 にする秘密鍵の予想値$K$が正しい値となる．

予想値$K$が正しい場合， $\vert P_{G_0} - P_{G_1}\vert \simeq D\cdot n/2$となり， 逆に誤っている場合， $\vert P_{G_0} - P_{G_1}\vert$は0に近づく．


III.3.3.2.1.1 スマートカードの電力モデル

暗号を実際のアプリケーションに応用する場合，暗号自体への攻撃に対する耐 性のみではなく実装されるデバイスへの攻撃に対する耐性も考慮しなければな らない．

多くのスマートカードではCMOSが使われており，その特性として，チップ上で 何らかの変化が生じた場合だけ電力が消費され，状態を維持するための消費電 力は少ない．

スマートカードにおいて，以下に示す処理が特徴的な電力消費パターンを示す．

また，一般にスマートカードは，内部あるいは外部のクロックにより駆動され， 通常は全ての動作が次のクロックが立ち上がる前に終了する．なお，チップ上 のノイズ生成器等はクロックに関係なく連続的にランダムにかつ小さく電力消 費を行う．

クロックは，電力を消費する一連のイベントをチップ内部のマイクロ命令に従っ て駆動する．1つのクロックサイクルの間の一連のイベントを決定するのはチッ プ内部の状態であり，これを関連状態(relevant state)と呼ぶこととする．

クロックのエッジからのチップ全体の瞬間電力消費は，各々のイベントの瞬間 電力消費の組み合わせで得られる．しかし各イベントの消費電力はカップリン グ効果ばかりでなく，基盤やレイアウト，気温や電圧等にも依存するため，複 雑である．また電力ばかりでなく，そのタイミングも複雑である．簡単化のた め，ここではとりあえず電力消費の総和が各イベントの電力消費の総和である と仮定する．

何らかの固定コードの実行パスの中のある命令のあるサイクルを考える．$S$ を制御がこのサイクルに到達する際の関連状態(relevant state)の集合，$E$を このサイクルの中で起こりうる全てのイベント空間とする．各$s\in S$及び $e\in E$について，$occurs(e,s)$を状態$s$においてイベント$e$が起きたと き$1$，そうでないとき$0$となる2値関数とする．$delay(e,s)$を状態$s$にお いてクロックのエッジからイベント$e$が起きるまでの遅延とし，さらに $f(e,t)$をイベント$e$が起きたときの電力消費インパルスの時間$t$に関する 関数とする (このときイベントが起きる時間が$t=0$であり，また$t<0$に対し $f(e,t)=0$である)． このときこのチップのこのサイクルの状態$s$，クロッ クのエッジからの時間$t$における電力消費関数$P(s,t)$は以下のように表せ る．


$\displaystyle P(s,t)$ $\textstyle =$ $\displaystyle N_c(t) + \sum\limits_{e\in E} (f(e,t-delay(e,s) + N_d(e,s))$  
    $\displaystyle + N(e,t)) * occurs(e,s);$ (III.6)

ここで，$N(e,t)$はイベント$e$の電力消費に伴うガウス雑音，$N_d(e,s)$は 遅延関数に影響するガウス雑音，$N_c(t)$は外部ガウス雑音を表す．

数式(III.6)はこのサイクルにおいて電力消費関数と状態$s$が強い関係 にあることを示している．電力差分解析ではこの電力消費の非対称性を利用す る．特に安価なスマートカードでは状態空間が小さく，この非対称性は顕著と なるため攻撃に弱くなる．

III.3.3.2.2 AES候補への適用例

AESの候補となっている各暗号方式をスマートカードに実装した場合の電力解 析攻撃の影響を調査する． 表III.5に各AES候補の単純電力解析(SPA)と電力差分解析(DPA)に対 する耐性及びその対処の実装可能性をまとめる．なお，対処の実装可能性について，ここで は各暗号方式において行われている処理のみを考慮している．つまり，電力解 析攻撃を受けにくい(または防御が容易である)処理のみを用いている暗号方式 に対して電力解析攻撃への対処の実装が容易であるとしている．


表 III.5: 各AES候補の電力解析攻撃に対する耐性及び対処法の実装可能性
 
電力解析攻撃に対する耐性
vs. SPA vs. DPA
対処法の実装
Mars ○ △ ×
RC6 ○ △ ×
Rijndael △ × ○
Serpent ○ × ○
Twofish ◎ × △
記号の意味
◎：非常に強い
○：強い
△：やや脆弱
×：脆弱
○：容易
△：やや困難
×：困難

各暗号方式で行われている基本的な処理のうち，ビット毎の論理演算，加算， 減算，及び乗算処理は，消費電力が計測されやすく，また単純電力解析に対す る対策を講じることが困難である(特に乗算は非常に困難である)．従ってこれ らの処理を用いないことが望ましい．

以下に，各暗号方式で行われている処理とともに，それぞれの単純電力解析， 電力差分解析との関係を列挙する．

III.3.3.2.2.1 Mars

行われている処理
テーブル検索(table-lookup)，シフト演算，ビット毎の論理演算，加算，減算，乗算

vs. SPA
Marsでは，ハミング重み計測により，鍵スケジュール部に関係するサイクルに おいてRAMに書き込まれる8ビットの内，平均2.54ビットの情報が取り出される が，RAMに書き込まれる各ビットがスマートカード内の秘密鍵と直接的に対応 していないため，スマートカード内の秘密鍵を求めることは困難である．また， ハミング重み計測に誤りが生じた場合，得られた情報をスマートカード内の秘 密鍵の特定に用いることはさらに困難である．

vs. DPA
Marsにおけるホワイトニング鍵はTwofishと同じ方法で得ることができる．し かし鍵スケジュール部が複雑であるために，全てのサブ鍵を得るために攻撃さ れるべき中心ラウンド数は膨大な数になる．各々の次の展開ボックスに対し， 排他的論理和の鍵が電力差分解析で攻撃可能であり，かつ乗算鍵がbit-by-bit 電力差分解析で攻撃可能でなければならない．

III.3.3.2.2.2 RC6

行われている処理
シフト演算，ビット毎の論理演算，加算，減算， $\bmod {2^{32}}$上における 二乗演算

vs. SPA
RC6では，Marsと同様の理由によりスマートカード内の秘密鍵を求めることは 困難である．

vs. DPA
加算入力および出力ホワイトニング鍵はbit-by-bit電力差分解析で取り出すこ とが可能である．また，加算ラウンド鍵も同様に取り出すことができる．鍵ス ケジュールが複雑であるため，全てのサブ鍵を得るためには全てのラウンドを 攻撃しなければならない．

III.3.3.2.2.3 Rijndael

行われている処理
テーブル検索(table-lookup)，シフト演算

vs. SPA
Rijndaelでは，Marsと同様の理由によりスマートカード内の秘密鍵を求めるこ とは困難であるが，RAMに書き込まれる各ビットとスマートカード内の秘密鍵 との関係がMarsやRC6に比べてより直接的であるので，MarsやRC6よりは容易で あると考えられる．

vs. DPA
電力差分解析では128ビットのRijndaelの全てのサブ鍵が得られたあとに排他 的論理和がなされる0ラウンド鍵が得られる．Rijndaelの提案者は34バイトの スマートカードであれば電力差分解析に耐えると主張している．しかし，現在 のところそのようなスマートカードは存在しない．

III.3.3.2.2.4 Serpent

行われている処理
シフト演算，ビット毎の論理演算

vs. SPA
Serpentでは，Marsと同様の理由によりスマートカード内の秘密鍵を求めるこ とは困難である．

vs. DPA
SerpentはDESと同じくある種の電力差分解析(すなわち，鍵の排他的論理和の あとのS-ボックスの探索)に対して弱い．鍵スケジュールの仕方により，マス ター鍵を得るには始めの2ラウンドのサブ鍵があれば十分であることが明らか である．

III.3.3.2.2.5 Twofish

行われている処理
テーブル検索(table-lookup)，シフト演算，加算

vs. SPA
Twofishの鍵スケジュール部は複雑であるので，ハミング重み計測からスマー トカード内の秘密鍵の直接的な情報を得ることは困難である．

vs. DPA
[CJ+99a] にはTwofishに対して行った電力差分解析の実験の様子が示されて いる．ここではホワイトニング鍵(128ビット)をまず求め，これをもとにマス ター鍵(128ビット)の候補を絞り込む手法が採られている．ホワイトニングプ ロセスには特徴的な電力消費パターンが存在するため特定が容易である．この ためホワイトニング鍵については電力差分解析によりたった100個の電力サン プルから全てのビットが正しく得られたという．さらに，Twofishの仕様に基 づきマスター鍵を絞り込む場合，ホワイトニング鍵がわかっていればその候補 は$9^8$個以下に減らすことができるという．これは全探索が困難でない個数 である．

next up previous contents
Next: III.3.3.3 RSAに対する電力解析 Up: III.3.3 電力解析 Previous: III.3.3.1 DESに対する電力解析