next up previous contents
Next: III.3.1.3 RC5への適用 Up: III.3.1 故障利用解析 Previous: III.3.1.1 故障利用解析の原理


III.3.1.2 DESへの適用

本節では,まずBihamらが提案した故障差分攻撃と故障非差分攻撃それぞれの DESへの適用を述べる.

III.3.1.2.1 故障差分攻撃

BihamとShamirによる故障差分攻撃( Differential Fault Analysis: DFA)は, ICカード等の耐タンパーデバイスにおいて同一の平文を暗号化する処理中に故障 を発生させ,エラーを含んだ暗号文と正しい暗号文の差分から,故障の発生位置 とビットの誤り内容を推測する方法である[BS97].DFAにより,DESの 場合50〜200個の暗号文情報(平文は知らなくても良い)から全ての鍵ビットを求 めることができる.さらにDFAによると,DESの3倍の鍵長を持ちより安全である Triple DESであっても,同数の暗号文から168ビットのすべての鍵ビット(あるい は,768ビットの拡大鍵の全ビット)を求めることが出来る.

DFAの手順は以下の通り[BS97,MS97]

DFAの手順
  1. 耐タンパーデバイスを同じ鍵を用いて,同じ平文を繰り返し暗号化して 暗号文を観測する.この処理中に,耐タンパーデバイスに物理的影響を 与え,エラーを引き起こす.この結果,複数の誤った暗号化結果と正し い暗号化結果が得られる.
  2. 何段目でエラーが起ったか推測する.たとえば16段目のF関数の入力側で エラーが起った場合,出力差分の伝播と,暗号化結果の差分の一致から エラーの発生を絞り込むことができる.
  3. 14段目の右32ビットでエラーが起った場合も同様に考えられる.
  4. 上記観測により,計算機シミュレーションでは200個以下の暗号文から16 段目に入力される48ビットの鍵すべてを導出できる.残りの8ビットは全 数探索して求めれば良い.

先の例のF関数の入力での故障発生以外にもF関数の内部での故障発生も仮定できる. ただし攻撃が成功する確率は同程度である. またデータ暗号化処理部ではなく鍵生成部の内部での故障発生も考えられる.

Bihamらによると,故障発生の位置と発生のタイミングを自由に選択できるなら ば攻撃を効率化できる.たとえば攻撃者が最後の数段で一様に故障を発生させら れるなら必要な暗号文数は10個である.さらに最も的確な故障発生位置では,必 要な暗号文の数は3つまで減少させられる.

III.3.1.2.2 故障差分攻撃の応用

Bihamらは,DFAの種々の応用についても考察を行っている[BS97].
一時的なハードウェア障害
DFAの一形態として, 瞬間的にクロック周波数や駆動電圧を変動させることにより 一時的なハードウェア障害を発生させる攻撃がある. 設計者はこの攻撃に対しては処理を二重化し暗号化結果の比較を行うという対策をとることができる.しかし,この対策は不十分である.仮に512箇所 の故障発生位置の候補があったとすると,故障が一致する確率は1/512である. つまり,その場合には従来の攻撃では200個であった暗号文を100000個に増やせ ば良い.
拡大鍵への適用
暗号の実装ではon-the-flyではなく拡大鍵を事前に計算しておく ことがある.この時,任意の拡大鍵ビットに故障の影響を与えることが容易であ る.ただし必要な暗号文の数は変らない.
処理改竄
処理がデバイス中のソフトウェアで実行されている場合, 故障によりプログラムカウンタやループカウンタを改竄することも できる可能性がある.この場合,より少ないラウンド数で暗号を攻撃するこ とも可能となる.
鍵スケジュール部への攻撃
DESの鍵スケジュール部では中間的な鍵にローテート演算が行われ, 16段分の処理で最初の鍵と一致する.16段処理した後の鍵を次の暗 号化の鍵としても用いる場合,DFAによりローテート量を変化させ ることができれば,相関鍵解読法(related key cryptanalysis)[Bih94] や相関鍵差分解読法(differential related key cryptanalysis)[KSW96]が可能となる.また,線形解読法や 差分-線形解読法も効率化できる.
利用モードへの攻撃
DFAの応用は,暗号の様々な利用モードで用いられる鍵を求めるの にも利用できる.この攻撃はCFBモードへの差分解読法[PN+93]と同様の 効果がある.
アルゴリズム非公開暗号への適用
DFAを適用した際の全ビットが0である鍵$k_f$を1ビットずつ変化さ せた鍵とオリジナルの鍵$k_0$の暗号結果の一致を調べる手間を $O(n)$とすると,$O(n^2)$で正しい鍵が求まる.さらに,Sboxなど 演算箇所にDFAを適用することにより,秘密のSboxの内容を解析す ることが可能となる.

III.3.1.2.3 故障非差分攻撃

故障差分攻撃(DFA)に対しては,一時的な故障を発生させるのは現実的でないと いった批判がある.故障非差分攻撃( Non-Differential Fault Analysis: NDFA)は,電子ビームなどによりシリコン上の回路に操作を加えて CPUのレジスタ上のビットに常に0(あるいは常に1)となる誤りを引き起こす攻撃 法である[BS97].

NDFAは,DFAとは異なり純粋な意味での暗号文単独攻撃が可能となる.平文も 故障が発生せず正常に処理された暗号文も必要としない. NDFAにはループ繰り返し構造を持ったコードへの基本的な攻撃, ループが展開されたコードへの適用などがあり,それぞれ以下の方法で攻撃を行 う.

基本的攻撃
ループ繰り返し構造を持ったDESのICカードへの実装に対する適用 を考える.すなわちDESの暗号化では図III.10の1段の 構造が16回繰り返される.

図 III.10: DESのループ繰り返し構造
\includegraphics [scale=1.0]{ndfaone.eps}

左側のレジスタのLSBを破壊することにより,レジスタのLSBは常に 0となる.したがって,最終段での処理は図III.11で 表される.

図 III.11: DESの最終段
\includegraphics [scale=1.0]{ndfalast.eps}

左側のレジスタのLSBは破壊されているため,$L_{15}$および $L_{16}$は常に0である.したがって,暗号文のLSBとF関数出力の LSBが一致する.このビットはS7の出力であり,S7への入力の鍵6ビッ トは,およそ6個の暗号文から組合わせにより求められる. 残りの鍵のビットは,故障箇所を追加していくことにより求められ る.

ループ展開型コードへの適用
高速化などの為にループ展開されたコードの場合,攻撃はより容易と なる.一段だけのデータの破壊が可能なため,$L_{15}$のLSBを破 壊することにより,2個の暗号文から対応する鍵が求まる.また, 破壊する位置によってはより効率的である. 鍵XOR後のSboxの両端のビットを破壊した場合,Sboxによる置換が 1対1になるため,出力から入力が一意に求まる.

他の方法として,最初の2段以外の14段の拡大鍵のレジスタを全て 破壊して0にした場合,暗号文を拡大鍵0で14段分復号すれば 2段DESの解読と等価となり,容易に解読できる.この攻撃は,他のデータ 暗号化部と鍵スケジュール部が独立した暗号にも適用できる.


next up previous contents
Next: III.3.1.3 RC5への適用 Up: III.3.1 故障利用解析 Previous: III.3.1.1 故障利用解析の原理