next up previous contents
Next: III.3.1.4 RSAへの適用 Up: III.3.1 故障利用解析 Previous: III.3.1.2 DESへの適用

III.3.1.3 RC5への適用

DESの場合と同様に,RC5に対する故障利用解析(DFA)が提案されている[MS97].提案されている攻撃法では,攻撃者が適用できるDFAのレベルとして, 拡大鍵の1ビットにビットエラーの発生(もしくは書き換え)が可能と仮定する.

RC5はブロック長,段数,鍵長を可変パラメータとしてもつブロック暗号である. 2wビットブロック長,r段,kバイトの鍵を持つRC5をRC5-w/r/kと記する.説明を 容易にするために,図III.12のhalf roundの概念を用いると,RC5アルゴ リズムは以下のように記述できる.

図 III.12: RC5のhalf round
$L_1 = L_0 + S_0$;
$R_1 = R_0 + S_1$;
${\bf for}\ i=2\ {\bf to}\ 2r+1\ {\bf do}$
$L_i = R_{i-1}$;
$R_i = ((L_{i-1}\oplus R_{i-1})<<< R_{i-1})+S_i$;
\includegraphics [scale=1.0]{rc5half.eps}

ここで,"$\oplus$"は排他的論理和,"$<<<$"はデータ依存ローテーション, "$+$"は加算を表す.

RC5の拡大鍵生成アルゴリズムはある種一方向性であるため, 一部の拡大鍵から他の拡大鍵を得ることは困難である.また,全ての 拡大鍵が分かったとしても元の鍵を得ることは困難である. DFAによる攻撃では,元の鍵は求められないが,暗号化あるいは復号に 用いられている全ての拡大鍵を求めることを目的とする.

RC5へのDFAによる攻撃は以下の方針で拡大鍵を導出する.

拡大鍵の推定には, 正しいi段目の出力$L_i,R_i$とDFAによる影響を受けた出力$L'_i,R'_i$のどのビッ トが異なっているかの情報を元に, ビット誤りの位置と加算のキャリーの伝播を考慮しつつ 場合わけと検証を繰り返し,拡大鍵 $S_i$の値の候補を絞って行く. 攻撃手順と場合わけの詳細については 文献[MS97] で発表されているが,非常に複雑でありここでは解説しない.