• III.3.3.3.1 解析原理
  • III.3.3.3.1.1 SEMD (Single Exponent Multiple Data)攻撃
  • III.3.3.3.1.2 MESD (Multiple Exponent Single Data)攻撃
  • III.3.3.3.1.3 ZEMD (Zero Exponent Multiple Data)攻撃

III.3.3.3 RSAに対する電力解析

本節では，RSAに対する電力解析の原理を解説する[MDS99b]． 対処方法についてはIII.3.3.5.3.3節を参照されたい．

III.3.3.3.1 解析原理

スマートカードを用いた公開鍵暗号システム（RSA暗号や楕円曲線暗号など）において，個人の秘密鍵に相当する秘密情報がスマートカード内に保管され利用される．スマートカードはその利用の際に，カードリーダーにより認証される．ここで重要なことはこのリーダーはある別のメンバにより製造されたものであるため，利用者にとって信用できるデバイスではないということである．従って，カードをカードリーダーに入れ，カードリーダーによるカードのコントロールを許した場合にでも，カード内部に保管される秘密情報の秘匿性は維持されるべきである．RSA暗号を用いてカードの認証を行う場合，カードリーダはランダムなチャレンジをカードに対して与え，その値に対してカード内部に秘密に保管されている秘密冪指数を用いて冪乗演算するように要求する．従って，例え不正に製造されたカードリーダーがカードにアクセスし，カードの冪乗演算実行中の電力消費を観測したとしても，カード内部の秘密情報が明かされないようにすることが必要である．

剰余冪演算は公開鍵暗号を実装する際には極めて重要な技術である．剰余冪演算を行う最も代表的なアルゴリズムは「平方乗算法(square-and-multiply algorithm)」である．また，楕円曲線暗号においてはこれによく似た「倍加算法(double-and-add algorithm)」を用いる．平方乗算法としては次の二つのアルゴリズムが代表的である．これを図III.20，III.21に示す．図III.20は最上位のゼロでないビットから始まり下位のビットに向かって演算が進んでいく．逆に図III.21は最下位のゼロでないビットから始まり上位のビットに向けて演算が進んでいく．図III.21では図III.20に比べて余分なメモリを必要とする．

図 III.20: exp1(M,e,N)

図 III.21: exp2(M,e,N)

文献[MDS99b]において示されている後述の３つの攻撃法はこれら二つのアルゴリズムのいずれにも原理的には適用可能である．とりわけMESD及びSEMDは平方乗算法に対しての攻撃であるが，この演算方法は公開鍵暗号に対しては何らかの形で実装されているので適用は可能である．ZEMD攻撃を成功させるには攻撃者がスマートカード内でどのような手法で演算が行われているのかを知っている必要があるが，とりうる演算手法はそれほど多くはないので，あらゆる可能性のある演算方法を想定してこの攻撃を適用することにより，攻撃を成功させることは可能であろう．

ここで述べられる攻撃の目的は，スマートカード内に秘密に保管される秘密の冪指数$e$を導出することである．攻撃者はスマートカードの動作を完全に制御することが可能であるとする．つまり，スマートカードは秘密鍵$e$を出力する以外のあらゆる攻撃者の命令に従うものとする．スマートカードに最も必要とされる機能は「内部認証(internal authenticate)」，即ち入力$M$に対して，$M^e$を出力する機能である．スマートカードの中にはオペレーションを行う際にPIN(Personal Identification Number)の入力を要求するものもあるが，ここではそれについては考慮しない．さらに攻撃者の計測回数に関しても制限しない．これらは現実の実装の観点から見て正当な仮定と言える．

まずはじめに，単純に乗算命令による電力信号とカードから出力される電力信号との相関をとることにより，$e$を決定することが可能かどうかを見てみよう． これにより冪乗演算全体に要する電力信号の相関を調査することにより，単一の剰余乗算もしくは剰余平方を区別することが可能かを見ることができる．ここで，剰余乗算の電力信号を$S_m[j]$，剰余冪演算の電力信号を$S_e[j+\tau]$とする．このとき，相関信号$S_c[j]$は次のように計算できる．

$$S_c[j] = \sum_{\tau=0}^{W} S_m[\tau]S_e[j+\tau]$$

ここで，$W$は乗算信号のサンプル総数とする．$T_m$を剰余乗算に要する時間，$T$をサンプルレートとすると，$W=T/T_m$となる．攻撃者は事前にスマートカードの設計書等を解析することにより，攻撃にとって適切な$W$を知ることが出来る．

実際のスマートカードにおいて入力値を固定し，5000回の出力の測定値を測定ノイズ除去のために平均化した結果を測定する実験で，この攻撃の可能性が検証されている[MDS99b]．

あらかじめ既知の冪係数について測定した場合と，未知の冪係数について測定した場合の電力信号と相関信号を観測した場合に，剰余乗算と剰余平方の位置がどのように現れるかを調べたところ，確かにこれらの計算が実行されている部分で，電力相関信号はピークを形成しているが，これら二つの間で大きな相違を見ることは出来ない．つまり，ここで述べられている電力相関の測定は剰余乗算と剰余平方のいずれが行われているのかを特定するためには用いることができない．だが，これらの測定により平方情報アルゴリズムに要する時間情報が決定できることは興味深い．この情報は電力攻撃とタイミング攻撃をともに用いる可能性を示している．相関信号は全ての中間処理のタイミングを明らかに出来るので，この攻撃は単純な時間攻撃に比べ非常に強力であるといえる．

III.3.3.3.1.1 SEMD (Single Exponent Multiple Data)攻撃

SEMD攻撃はスマートカードが二つの冪指数（一方は秘密指数で一方は公開指数）を用いて任意の数のランダムな値に対して冪演算を実行する場面を想定する． このような場面はISO7816[ISO] 標準の「外部認証コマンド(external authenticate command)」をサポートするスマートカードシステムで起こりうる．内部認証コマンド(internal authenticate command)が秘密指数を用いて冪演算を行うのに対して，外部認証コマンドは特定のスマートカードリーダに関連付けられた公開鍵を用いて冪演算を実行する．攻撃者はこの公開鍵のビットを知っているものとする．

この攻撃の大前提は未知の冪指数を用いた実行された冪演算の電力信号と，既知の冪指数を用いて実行された冪演算の電力信号をを互いに比較することにより，攻撃者は二つの冪指数のビットの違いを測定して秘密鍵を解き明かすことが可能であるということである．実際には，平方乗算アルゴリズムの中間データの結果が電力信号に大きな影響を及ぼすので，この比較は単純ではない．単純な電力差分解析は秘密冪指数を用いて$L$個のランダムな値を冪乗させ，それらの電力信号$S_i[j]$を収集することにより開始する．同様に，公開冪指数に対しても$L$個の電力信号$P_i[j]$を測定する．これらを用いて電力差分解析(DPA)バイアス信号$D_j$は次のように構成できる．

$$D[j] = \frac{1}{L}\sum_{i=1}^{L} S_i[j] - \frac{1}{L}\sum_{i=1}^{L} P_i[j] = \bar{S}[j] -\bar{P}[j]$$

中間データに依存する$\bar{S}[j]$と$\bar{S}[j]$の分布は同じ値に平均化される．つまりデータに依存するサンプル点$j$においては次が成立する．

$$\bar{S}[j] = \bar{S}[j] \approx \mu$$

だが，冪指数に依存するサンプル点$j$では，剰余乗算が行われるか剰余平方が行われるかに従って異なる値($\mu_s,\mu_p$)に平均化されるはずであり，従ってDPAバイアス信号$D[j]$もゼロでない値となるであろう．これを用いて以下のように平方と乗算の位置を抽出することが可能である．

$$D[j] \approx \left\{ \begin{array}{ll} 0 & (j \mbox{におけ.. ...& (j \mbox{における冪演算処理が異なるなら)} \end{array}\right.$$

SEMD攻撃の可能性を実験で検証した結果が報告されている[MDS99b]．実験では，法および冪指数を64ビットと短いビット長を用いている．短いビット長の冪指数を用いた場合，より多くの電力信号をデジタルオシロスコープに収めることが出来るため，一回の測定で，より長いビットに対して攻撃を行うことが出来る．実際のサイズ（例えば1024ビットなど）の冪指数に対しては一度の測定で冪指数の一部だけが攻撃可能である．一度に攻撃可能なビット長は攻撃者の持つデジタルオシロスコープの解像度（メモリ）に依存する．測定結果を観察したところ，DPAバイアス信号は，平方と乗算とで異なる処理の行われている部分において，DPAバイアス信号が強く増幅されていることが分かった．出力に対して適切なフィルタリングを行うことにより，この相違点は簡単に特定可能であり，SEMD攻撃の有効性は実証されている．つまり，スマートカードシステムを実装する際にはSEMD攻撃への対応を考慮することが重要であろう．

III.3.3.3.1.2 MESD (Multiple Exponent Single Data)攻撃

MESD攻撃はSEMD攻撃よりも強力であるが，スマートカードに対していくつかの仮定を追加する必要がある．前述のSEMD攻撃は攻撃者の側に複雑な処理を必要としない単純な攻撃であるが，DPAバイアス信号を頻繁に測定することはしばしば困難である．MESD攻撃はSEMD攻撃の信号対雑音比(SNR)を改善する．MESD攻撃の仮定は「攻撃者が自由に選択した冪指数を用いて，スマートカードに対して定数（攻撃者が知らなくても可）を冪乗演算させることが出来る」というものである．このような仮定は現実的に起こりえないものではない．何故なら，しばしばスマートカードは新しい冪指数をセットアップできるように構成されていることがあるからである．スマートカードは無限のメモリを持っていないので，既に冪乗された値のリストを全て保持することは出来ない．従ってカードの側では定数を冪乗するように繰り返し依頼されたとしても，それを検地することは出来ない．

MESD攻撃のアルゴリズムは図III.22に示される．アルゴリズムの第一ステップは任意の値$M$を選択し，$M$を秘密指数$e$を用いて冪乗させ，対応する平均電力信号$S_M[j]$を収集することである．次に，アルゴリズムは$e$の第一ビットから順に最後のビットまで進んでいく．$i$番目のビットを攻撃するために，攻撃syは$i$番目のビットが$0$か$1$であると推測し，それぞれの予想値を用いて冪演算をカードに実行させる．攻撃者は既に$i-1$番目までのビットを推測していると仮定すると，$i-1$番目までのビットによる演算の中間データは測定結果と予想結果は一致するだろう．従って$i$番目のビットの予想が正しければ，中間結果の予想は$i$番目でも一致するはずであり，もし予想が正しくなければ結果は異なってくるはずである．この相違は相関電力を調べることで確認できる．$M$を$e_g$を用いて冪乗するのに要する平均電力信号を，$e_g$の$i$番目のビットが1である場合$S_1[j]$，0である場合$S_0[j]$とする．二つのDPAバイアス信号は次のように計算できる．

$$D_1[j] = S_M[j] -S_1[j] \qquad D_0[j] = S_M[j] -S_0[j]$$

予想が正しい場合，電力信号は秘密冪による電力信号と一致するためバイアス電力は0になる．

図 III.22: MESD攻撃アルゴリズム

実際のスマートカードを用いて，この攻撃の有効性を検証したところ，SNRは明らかにSEMD攻撃に比べ向上している．SNRが高いということはMESD攻撃の実現に要する試行測定回数が少なくてすむことを示す．また，攻撃者は一度だけDPAバイアス信号を計算すればよい．例えば，攻撃者は全てのビットが1であると予測するとする．予測が正しければバイアス信号は$0$のまま続き，予測がずれた時点で$0$以外の値になる．このテクニックにより攻撃アルゴリズムの実行時間は効率的に削減される．実際，この測定結果は冪指数一ビットにつき200回の試行により測定された．MESD攻撃は可能な状況では，カードを実装する際にこの攻撃を考慮する必要がある．

III.3.3.3.1.3 ZEMD (Zero Exponent Multiple Data)攻撃

ZEMD攻撃はMESD攻撃に似ているが仮定に相違がある．ZEMD攻撃の仮定は「攻撃者が多くのランダムなメッセージに対する秘密冪指数を用いた冪演算をスマートカードに実行させることが出来る」というものである．この攻撃では攻撃者は冪指数に関する予備知識をまったく必要としない（このためZero Exponentと呼んでいる）が，そのかわりに攻撃者はオフラインのシミュレーションにおいて平方乗算アルゴリズムの中間結果を予測できなければならない．そのため，攻撃者はカード内部で冪演算を実行するために行われているアルゴリズムの詳細を知っている必要がある．だが，これらのアルゴリズムの候補は数少ないので全数探索的に全てのアルゴリズムを考慮して攻撃を行うことは可能であろう．

ZEMD攻撃は図III.23に示される．ZEMD攻撃は第1ビットから順に最終ビットまで実行される．このアルゴリズムでは変数$e_g$が徐々に秘密指数に等しくなっていく．それぞれの繰り返しで，冪のある1ビットを求めることができ，$e_g$は次々に更新されていく．アルゴリズムを$i$回目に繰り返したとき，$e_g$の$i-1$番目のビットまでは正確であると仮定する．アルゴリズムは$i$番目のビットが$1$であると仮定し，それが正しいかどうかをDPAバイアス信号を用いて推測していく．DPAバイアス信号はランダムな入力$M$を選び，消費電力をシミュレーションにより求めることにより決定する．消費電力は冪指数のハミング重みにより推測可能である．

図 III.23: ZEMD攻撃アルゴリズム

実験による検証で，実際にZEND攻撃成功させるためには，200個程度のランダムな電力信号の測定で十分であることが報告されている[MDS99b]．