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$;

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

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

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

• 拡大鍵$S_i$のtビット目に起こしたビットエラーによるDFAの影響を受け た出力$L'_i,R'_i$を元に，$S_i[t]$を決定する．
• 拡大鍵$S_{i-1}$のtビット目に起こしたビットエラーによるDFAの影響を受け た出力$L'_i,R'_i$を元に，$S_{i-1}[t]$を決定し，さらに$S_i$の候補 を絞り込むための情報を得る．

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