next up previous contents
Next: IV. 安全性評価の標準化動向 Up: III.3.3 電力解析 Previous: III.3.3.4 楕円曲線暗号に対する電力解析


III.3.3.5 電力解析の対策

ここでは電力解析への対処方法として, 主に電力差分解析に関して各設計レベル毎に整理する.

III.3.3.5.1 トランジスタレベルでの対策

ゲートレベルにおける論理回路デザインの工夫により, 外部に漏れる情報を大幅に削減する方法が開発されている[KJJ98]. また,現在のところトランジスタにとって代わるデバイスは実用化されていないが, 光コンピューティング等の新しい計算技術を実用化することで問題を解決することもできる.


III.3.3.5.2 回路,プロセッサ等ハードウェアレベルでの対策

物理的に大きなシステムでは,電力供給にフィルタリングを施したり, 遮蔽シールドで保護するなどの対策が考えられる. コストやサイズの制約があるスマートカードなど のシステムでは,主に次のような対策が考えられる.

消費電力信号の振幅を小さくする具体的な方法として, 一定のパスコードを用いる,消費電力の変化が小さい命令を用いる, ハミング重みと状態遷移のバランスをとる,等を挙げることができる. また,雑音を付加する方法として, 解析に必要なサンプル数を実際には不可能な程度まで大きくする, 実行のタイミングやオーダーに関する情報を外部から検出不可能にする, 等の対処方法を用いることができる. ただし,これらの対策は,攻撃者が長時間の解析を行えない場合において有効であるが, 消費電力と秘密情報を用いた演算内容 との相関を完全になくすには至らないため,根本的な解決策とはいえない.


III.3.3.5.3 ソフトウェアおよびアルゴリズムレベルでの対策

最も効果的な解決策は,ハードウエアが情報を漏らしてしまうことを 不可避なものとする立場に立った対処方法である. 非線形な鍵の更新は電力解析を困難にする. 例えばSHAを用いて160ビットの鍵のハッシュ値をとり, それを用いて演算を行うと解析を困難にすることができる. また,冪指数や剰余の法などのパラメタを頻繁に更新す ることも有効である.鍵の使用回数を記録する装置を装備するのもよい.

以下,電力解析の適用例として本報告書で調査した DES,AES候補,RSA,楕円曲線暗号における対処方法をまとめる.


III.3.3.5.3.1 DESにおける対処方法

単純電力解析
単純電力解析を防ぐ方法は比較的簡単に実装することができる. 条件分岐演算について秘密の中間プロセスや鍵を用いることで 多くの単純電力解析の特徴を隠すことができる. しかし条件分岐を本質的に仮定しているアルゴリズムでは, 新たな符号化を要し重大なパフォーマンスの低下を招いてしまう.

さらに,オペランド値に大きく依存した電力消費をするシステムでは, 実行パスを同一にしても単純電力解析により解析が可能である.

ただ,現在の共通鍵暗号を実装したデバイスのほとんどは電力消費量が小さく, 単純電力解析により鍵情報を得ることが困難である.

電力差分解析
電力差分解析を防ぐ方法は大きく3つに分類することができる. 初めの2つが,III.3.3.5.2節で述べた 消費電力信号の振幅を小さくする方法と 消費電力測定に雑音を付加する方法であり, 最後の1つが本節の冒頭部で述べた ハードウェアからの情報のリークは不可避なものとの 仮定に立った対処方法である.


III.3.3.5.3.2 AES候補における対処方法

文献[CJ+99a] では,あらゆる電力解析攻撃への対処方法は不可能であると しているものの,現実的な観点からは高階電力差分解析,単純電力解析,電力 差分解析などの一般によく知られた攻撃に耐える実装であれば十分であるとし ている.この前提のもとに挙げられている対処方法を以下に挙げ,解説する.


III.3.3.5.3.3 RSAにおける対処方法

RSAに対する3種類の電力解析攻撃に対して採りうる対策としては,タイミング解析 を防ぐために用いられるアプローチと同様のものが考えられる. ブラインド署名[Cha82]のテクニックを用いるというKocher [Koc96] のテクニックは電力解析攻撃を防ぐためにも有効である.冪演算を実行する前に,メッセージは乱数$v_i$でブラインド化され,冪演算実行後に $v_f={({v_i}^{-1})}^e \bmod N$ を乗ずることによりアンブラインド化(ブラインドの影響を取り去ること)が行われる. Kocherはこの効率的な手法を提案している.

メッセージのブラインド化はMESD攻撃とZEMD攻撃を防ぐものの,SEMD攻撃を防ぐことはできない.SEMD攻撃を防ぐためには冪指数自体をブラインド化することが必要になる.RSA暗号においては冪指数に$\phi(N)$の倍数を加えることにより冪指数のブラインド化を実現できる.これらをまとめてブラインド処理を施した冪演算アルゴリズムは図III.27の通りである.

図 III.27: ブラインド化による冪乗演算アルゴリズム
\begin{figure}
\begin{center}
\frame{
\begin{tabular}{ll}
1. Blind the message $...
...d the result:& $S = (v_f\hat{S}) \bmod N$\end{tabular}}
\end{center}\end{figure}

別の方法は冪演算アルゴリズム自体をランダムに変化させることである. exp1アルゴリズム(図III.20)とexp2アルゴリズム(図III.21)を ランダムなポイントで切り替えて用いることである. このランダム化により達成できる安全性は冪指数のビット長に依存する もののビット長が十分長ければ事実上電力解析攻撃は不可能である.


表 III.6: 電力解析攻撃の分類
攻撃名 試行回数 仮定 対処法
SEMD 20,000 攻撃者がひとつの公開冪指数を知っている 冪のブラインド化
MESD 200 攻撃者がひとつの冪指数を自由に設定できる メッセージのブラインド化
ZEMD 200 攻撃者は冪演算アルゴリズムを知っている メッセージのブラインド化


III.3.3.5.3.4 楕円曲線暗号における対処方法

ここでは,III.3.3.4節で示された楕円曲線暗号系に対する電力差分解析への対処方 法について述べる.[Cor99]において示された乱数を有効に利用する三つ の手法を紹介する.これらの対処方法は実装が容易で あり効率性に支障をきたすことはない.しかし,この対処方法により楕円曲線 暗号系に対するすべての電力差分解析に対処可能であるかは不明である.

III.3.3.5.3.4.1 秘密鍵のランダム化を用いた対処法
$\sharp \varepsilon$を楕円曲線上の点の数とする.$Q=dP$の計算を次のように行うことで電力差分解析を防ぐ.

  1. $n$ビット(20ビット程度)の乱数$k$を選ぶ.
  2. $d' = d + k\sharp \varepsilon$を計算.
  3. $Q = d'P$を計算. $\sharp \varepsilon P=0$であるから,$Q=dP$となる.

この手法を用いた場合,毎回異なる$d'$を用いて$d'P$を計算することになるため 電力差分解析の適用は不可能であり, 攻撃を防ぐことができる.

III.3.3.5.3.4.2 Pのブラインド化を用いた対処法
RSA暗号に対するChaumのブラインド署名技術を応用する方法を示す.ランダム に点Rを選び,$S=dR$を計算する.スカラー乗算は$d(R+P)-S$により行われる.$R$$S$ははじめからスマート内に収められており,新しい計算の度に $R
\leftarrow (-1)^b 2R,
S \leftarrow (-1)^b 2S$を計算し$R,S$を更新する($b$はランダムな1ビット). 攻撃者は$P'=P+R$の値を知らないため電力差分解析を適用することはできない.

III.3.3.5.3.4.3 射影座標のランダム化を用いた対処法
$P=(x,y)$の射影座標$(X,Y,Z)$は次のように与えられる.


\begin{displaymath}
x=X/Z, y=Y/Z
\end{displaymath}

$(X,Y,Z)$はユニークではなく,有限体上$\lambda$すべて $(\lambda \neq 0)$ に対して $(X,Y,Z)=
(\lambda X, \lambda Y,\lambda Z)$$P$の射影座標となっている.これを利用し,計算を実行するた びにランダムに$\lambda$に対する$P$の射影座標を求め,それを次の計算に利用する. この手法により$P$の射影座標の特定のビットと電力消費量との間の有意な相関 は表れないものとなる.したがって,電力差分解析を防ぐことができる.


next up previous contents
Next: IV. 安全性評価の標準化動向 Up: III.3.3 電力解析 Previous: III.3.3.4 楕円曲線暗号に対する電力解析