next up previous contents
Next: III.2.2.3 プローブ解析の対策 Up: III.2.2 プローブ解析 Previous: III.2.2.1 プローブ解析の原理

III.2.2.2 プローブ解析の適用例

III.2.2.2.1 RSA

RSA [RSA78]における処理手続きを図III.6に示す．

図 III.6: RSAの処理
\begin{figure} \begin{center} \frame{ \begin{tabular}{ll} 秘密鍵:& $p$, $q$, $d$... ...^e \bmod n$\\ 復号化:& $M = C^d \bmod n$\end{tabular}} \end{center}\end{figure}

RSAの復号化では秘密鍵$d$を指数とするべき乗剰余算が行われるため， III.2.2.1節で述べたSM-1への攻撃をそのまま用いることで RSAに対するプローブ解析を実行することができる． 復号化のべき乗剰余算では暗号文$C$と法$n$とが既知であり， プローブ解析から秘密鍵$d$を直接求めることが可能である．

III.2.2.2.2 DSA

DSA (Digital Signature Algorithm) [DSA95]における処理手続きを 図III.7に示す．

図 III.7: DSAの処理
\begin{figure} \begin{center} \frame{ \begin{tabular}{ll} 秘密鍵:& $x$\ ($0<x<q$... ...mod p) \bmod q$\\ & $v=r$ならば検証成立 \end{tabular}} \end{center}\end{figure}

前述のRSAとは異なり，DSAでは秘密鍵$x$が 署名手続きにおけるべき乗剰余算の指数として用いられていないため， (i)の$r$の計算にプローブ解析を適用する． $r$の計算では指数$k$以外の$p, q, g$は既知であり， III.2.2.1節で述べたSM-1へのプローブ攻撃を 実行して$k$を求めることができる． 一方(ii)より

\begin{displaymath}x=r^{-1}(sk-H(m)) \bmod q \end{displaymath}

であり， 署名$(r, s)$およびメッセージ$m$のハッシュ値$H(m)$が既知であるため， プローブ解析で求めた$k$を用いて 秘密鍵$x$を計算することが可能である．

III.2.2.2.3 DES

DESはアルゴリズムを図III.8に示したように 16段のFeistel型である[DES77]．

図 III.8: DESのアルゴリズム
\begin{figure} \begin{center} \frame{ \begin{tabular}{l} $(L_0\vert R_0)=IP(m_L\... ...nd for\\ $c=IP^{-1}(R_{16}\vert L_{16})$\end{tabular}} \end{center}\end{figure}

プローブ解析では各ラウンド毎に$L$か$R$どちらか片方のレジスタのビット値を測定する． 今，レジスタ$L$をプローブするとし，1組の平文と暗号文を用意して 最終16段目の鍵$K_{16}$の6ビットを求めることを考える． この鍵$K_{16}$の6ビットを$k_{16}$と書き，$k_{16}$と $F$関数等で演算処理が行われるレジスタ$L$のビットを$l_{16}$と書く．

まず $R_{16}=L_{15}\oplus F(R_{15},K_{16})$において プローブ解析から$l_{15}$と $l_{16}(=r_{15})$が分かっているため， $k_{16}$の推測値を$k'_{16}$として $r'_{16}=l_{15}\oplus F(r_{15},k'_{16})$を計算する． 一方，暗号文に初期転置$IP$をかけることで$r_{16}$の正しい値を 得ることができるため，これと$r'_{16}$とを比較することで 鍵の推測値$k'_{16}$が正しかったかどうかを判断することができる． プローブするビット数に依存すると思われるが， 文献[HPS99] では鍵の6ビットを求めるには 暗号文が6つあればよいとしている．

以上の手続きは1段目にも同様に適用可能であるため， 1段目と16段目からそれぞれ6ビットずつ， 合計12ビットをプローブ解析から得ることができる． そしてDESの鍵56ビットの残り44ビットに関しては 総当たり検索を行うことで鍵の全ビットを求める．

このようにしてプローブ解析のDESへの適用は可能であるが， triple-DESに関しては必要な総当たり検索数が$2^{100}$となり プローブ解析は現実的ではない． またDESへの攻撃に関しても，プローブするビット位置は任意ではなく 求める鍵のビットと対応していなければならない等の 技術的困難さが含まれる．

III.2.2.2.4 RC5

RC5は平文および暗号文のブロックサイズ$2w$ビット($w$=16, 32, 64)， 鍵サイズ$b$バイト($0\le b\le 255$)，段数$r$ ($0\le r\le 255$)が指定可能で， RC5-$w/b/r$と表記される[Riv95]． RC5のアルゴリズムを図III.9に示す． $x<\!<\!<y$は，$y$の下位$\log w$ビットで表される整数値分だけ $x$を左巡回シフトすることを表す． また図III.9の表記では， 1段がRC5本来の1段の半分に相当している．

図 III.9: RC5のアルゴリズム
\begin{figure} \begin{center} \frame{ \begin{tabular}{l} $L_1=L_0+S_0$\\ $R_1=R... ..._{i-1}\oplus R_{i-1})<\!<\!<R_{i-1})+S_i$\end{tabular}} \end{center}\end{figure}

RC5に対するプローブ解析ではDESへの適用と同様にレジスタ$L$か$R$どちらか 片方のビット値が各ラウンド毎にプローブ可能であることを前提条件とし， ここではレジスタ$R$のビット$p$ (上位ビット側から$p$番目)をプローブするとする． また暗号化の前処理としてRC5では秘密鍵から拡張鍵テーブルを作成するが， プローブ解析では秘密鍵そのものではなく拡張された鍵$S_i$の解読を目的とする． RC5への攻撃手順は以下の通りである．

ステップ1
最終段$2r+1$では $L_{2r}\oplus R_{2r}$が $R_{2r}(=L_{2r+1})$の下位$\log w$ビットの値で左巡回シフトされるため， 下位$\log w$ビットの値が$w-p$であるような暗号文$L_{2r+1}$に対しては， $(L_{2r}\oplus R_{2r})<\!<\!<R_{2r}$の最下位ビットがちょうど$p$になる． この最下位ビットの値は $R_{2r-1}(=L_{2r})$および$R_{2r}$への プローブ解析から知ることができるため，これと暗号文$R_{2r+1}$とから 鍵$S_{2r+1}$の最下位ビットの値を求める．

ステップ2
次に下位$\log w$ビットの値が$w-p+1$である暗号文$L_{2r+1}$に対しては， ビット$p$はシフトによって $(L_{2r}\oplus R_{2r})<\!<\!<R_{2r}$の最上位ビットへ移るため， ステップ1と同様な手続きから鍵$S_{2r+1}$の最上位ビットの値を得る． $S_{2r+1}$の残りの$w-2$ビットについても異なる暗号文を用いて順次求める．

ステップ3
得られた最終段の鍵$S_{2r+1}$を用いて$L_{2r+1}$および$R_{2r+1}$を復号化し， ステップ1，2と同様な手続きを$S_{2r}$に対して行う． この操作を繰り返すことで$S_4$までの鍵を得る．

ステップ4
残った鍵 $S_3,S_2,S_1,S_0$は 2段のブロック暗号に対する直接的な解析から求める．

Handschuhらは用意する平文/暗号文は$w$の数倍程度でよく， 解析は複雑でないとしている． しかしDESの場合と同様にプローブするビット位置が既知であることを 前提としている点などからは，技術的には困難が伴なうと予想される．

next up previous contents
Next: III.2.2.3 プローブ解析の対策 Up: III.2.2 プローブ解析 Previous: III.2.2.1 プローブ解析の原理