• III.2.2.1.1 ビット位置が既知の場合
• III.2.2.1.2 ビット位置が未知の場合

III.2.2.1 プローブ解析の原理

ここではRSA，ElGamal，DSA，Schnorr型署名などの公開鍵暗号に対する攻撃を 例にとってプローブ解析の原理を説明する．

公開鍵暗号で用いるべき乗剰余算

$$A = m^d \bmod n$$

において， 指数$d$をプローブ解析によって求めることを考える． その際，べき乗剰余算の実装アルゴリズムとして実績の高い SM-1 (Standard Square-and-Multiply Algorithm)を例にとる． このアルゴリズムの処理手順は図III.3に示す通りである．

図 III.3: SM-1の処理手順

SM-1では内部ループ毎に$d$を1ビットずつ 上位ビットから下位ビットへとスキャンしながら演算処理を実行し， $i$番目のステップが終了した時点で アキュムレータ$A$に格納されている値は

$$A_i = m^{d_i} \bmod n$$

となる． ここで$d_i$は$d$の上位$i$ビットで表現される整数を表す．

プローブ解析では，アキュムレータ$A$の任意の1ビット以上の値が ステップ毎に完全な同期をもって測定可能であることを前提条件としている． すなわち，プローブするアキュムレータ$A$のビット位置を $J \subset \{1,\ldots,\vert A\vert\}$ ($\vert x\vert$は$x$のビット長を表す)とし， 観測値のセットを$A(J)$とすると， 攻撃者はステップ$i$の終了時までに

$$T_i = (A_1(J),A_2(J),\ldots,A_i(J))$$

というシークエンスを得ることになる． このプローブするビット位置$J$が既知か否かで解析手順が異なるため， 以下それぞれの場合に分けて解説する．

III.2.2.1.1 ビット位置が既知の場合

べき乗剰余算の実行において底$m$と法$n$は既知であるため， $d_i$の推測値を$\delta$とすると， 攻撃者はSM-1を用いて

$$T'_i(\delta) = (A'_1(J),A'_2(J),\ldots,A'_i(J))$$

を容易に計算することができる． 推測値$\delta$が正しくなるのは $T_i=T'_i(\delta)$の場合のみであるため， プローブ解析では$T_i$の測定毎に$T_i$と$T'_i(\delta)$とを比較し， $\delta$が正しいものであるかどうかを判定する． これを $i=1,\ldots,\vert d\vert$の間繰り返すと， 攻撃が終了した時点で得られている$\delta$の候補には 求めるべき値$d$が必ず含まれていることになる． 以上の攻撃手順をまとめたものが図III.4である． 処理(i)では$\delta$の候補が機械的に2倍に増やされるが， これはSM-1のステップ毎に$d_i$が2進数で1桁ずつ増えていくのに 対応した操作である．そして(ii)が$\delta$の判定処理となっている．

図 III.4: プローブ解析の手順(ビット位置が既知)

このプローブ解析は統計的手法を必要とせず， ポイントはチェックするべき$\delta$の候補数$\vert\Delta\vert$が ステップを重ねる毎に爆発的に増加しないかどうかにかかっている． この候補数の増減則はプローブするビット数$\vert J\vert$に依存して変わるため， 条件毎に$\vert\Delta\vert$を推算する．

$\vert\Delta\vert$の見積り: ステップ$i$終了時の$\delta$の候補数の平均値$u_i$は，

$$u_i = 1 + \varepsilon (2u_{i-1}-1)$$ (III.1)

という漸化式に従う． ここで$\varepsilon$はステップ$i-1$で正しいと判定された$\delta$が ステップ$i$でも正しいと判定される確率であり， 測定値$A_i(J)$と推測値$A'_i(J)$との間に相関が全くないと仮定して

$$\varepsilon = 2^{-\vert J\vert}$$

としている． (III.1)式は，ステップ$i-1$で生き残った$\delta$の候補には 正しい$\delta$が必ず1つ含まれ，それ以外の$2u_{i-1}-1$個は 次のステップ$i$で確率$\varepsilon$で生き残ることを意味している． この漸化式(III.1)を初期条件$u_0=1$を用いて解くと， ビット数$\vert J\vert$が1か2以上かによって$\vert\Delta\vert$の推定値を

$$\vert J\vert=1\;(\varepsilon=\frac12)\mbox{のとき}\;\; E(\vert\Delta\vert) =1+\frac{\vert d\vert}{2}$$ (III.2)

$$\vert J\vert\ge2\;(\varepsilon<\frac12)\mbox{のとき}\;\; E(\vert\Delta\vert) =\frac{1-\varepsilon-\varepsilon(2\varepsilon)^{\vert d\vert}}{1-2\varepsilon}$$

$$\le\frac{1-\varepsilon}{1-2\varepsilon}$$ (III.3)

と求めることができる． すなわちプローブするビット数が$\vert J\vert\ge2$の場合は 候補数は ${\displaystyle \frac{1-\varepsilon}{1-2\varepsilon} }$以下であり， この値は最も大きくなる$\vert J\vert=2$で1.5と非常に小さいものになっている． また$\vert J\vert=1$の場合も候補数は$\vert d\vert$のオーダーであり， 解析は実行可能であることが分かる．

III.2.2.1.2 ビット位置が未知の場合

プローブするビットの位置が未知の場合も基本的な解析手順は変わらないが， ビット位置に関するループが内側に追加されるため 攻撃手順は図III.5のように拡張される．

図 III.5: プローブ解析の手順(ビット位置が未知)

処理(ii)の $T'_i(\delta;j)$は， $j\in\{1,\ldots,\vert A\vert\}$である任意のビット$j$に関して推算した

$$T'_i(\delta;j) = (A'_1(j),A'_2(j),\ldots,A'_i(j))$$

である． $\delta$は $T_i \subset T'_i(\delta;j)$であれば $j$に関して正しいと判定され，$\Delta_j$に保存される． そして$\vert\Delta_j\vert=0$となった時， $j$はプローブしているビット位置ではないことが分かり， ビット位置に関するループから外される．

$\vert\Delta\vert$の見積り: プローブしているビットの位置が未知の場合は， 前述の漸化式(III.1)において初期条件が$u_0=\vert A\vert$となり， $\vert\Delta\vert$の推定値は次のようになる．

$$\vert J\vert=1\mbox{のとき}\;\; E(\vert\Delta\vert) =\vert A\vert+\frac{\vert d\vert}{2}$$ (III.4)

$$\vert J\vert\ge2\mbox{のとき}\;\; E(\vert\Delta\vert) =\frac{1-\varepsilon-(1-\varepsilon)(2\varepsilon)^{\vert d\vert}}{1-2\varepsilon} + \vert A\vert(2\varepsilon)^{\vert d\vert}$$

$$\le \frac{1-\varepsilon}{1-2\varepsilon} + \vert A\vert(2\varepsilon)^{\vert d\vert}$$ (III.5)

$\delta$の候補数の初期値が$\vert A\vert$であるために ($\vert A\vert$は鍵サイズで決まり，512，1024，2048といった値になる)， (III.5)式の$\vert J\vert\ge2$の場合， ビット位置が既知の(III.3)式と比較して $\vert A\vert(2\varepsilon)^{\vert d\vert}$という項が付加される． しかしこの項はステップ数10〜20程度で急速にゼロへと収束するため， ビット位置が未知の場合でも解析は現実的といえる． また$\vert J\vert=1$の場合にも候補数は$\vert A\vert$のオーダーであり， 解析は実行可能範囲に入っている． ただし$\vert J\vert$が1か2以上かで$\vert\Delta\vert$の増減則がドラスティックに変わるため， 特にビット位置が未知の場合は 2つ以上のビットのプローブが効率的であると考えられる．