next up previous contents
Next: III.3.2.3 タイミング解析の対策 Up: III.3.2 タイミング解析 Previous: III.3.2.1 タイミング解析の原理



III.3.2.2 タイミング解析の適用例


III.3.2.2.1 RSA, Diffie-Hellman

Dhem らによって提案された,RSA, Diffie-Hellmanで用いられている べき乗剰余算 $m^d \bmod n$へのタイミング解析の適用を説明する [DK+98]. ここで $n$ は公開鍵,$m$ はメッセージ,$d$ は秘密鍵であり, 攻撃者から見たパラメータの関係は表 III.2 のとおりである.


表 III.2: 攻撃者から見たパラメータ(べき乗剰余算)
  $m$ $n$ $d$
既知/未知 既知 既知 未知
入力パラメータ    
解析対象パラメータ    

べき乗剰余算は通常,バイナリ法を用いて剰余乗算の繰り返しで実現されている. さらに剰余乗算の高速化手法として知られる Montgomery の方法(Montgomery乗算 と呼ぶ)を用いていると仮定する.図III.14にMontgomery乗算$mont(x,y,n)$ の,図III.15にMontgomery乗算を用いたべき乗剰余算のアルゴリズム を示す.この節では図III.15 $x = mont(x, x, n)$ $x = mont(x, m', n)$をそれぞれ単に2乗算,乗算と呼ぶことにする.

図 III.14: Montgomery乗算 mont(x,y,n)
\begin{figure}
\begin{center}
\begin{tabular}{l}
\hline
入力:$x,y,n$\ \\
出力..
...\ (減算A)\\
${\bf return}\ w$\ \\
\hline
\end{tabular}\end{center}\end{figure}

図 III.15: 左バイナリ法+Montgomery乗算によるべき乗剰余算
\begin{figure}
\begin{center}
\begin{tabular}{l}
\hline
入力:$n, m, d\ ( d = (d...
...x,1,n)$\ \\
${\bf return}\ x$\ \\
\hline
\end{tabular}\end{center}\end{figure}

III.14から分かるとおり,Montgomery乗算には条件分岐があり, 減算$w = w - n$ が1回多く行われる場合がある. したがってMontgomery乗算はデータによって処理時間が異なるため, タイミング解析の対象となる. 以後この減算を減算Aと呼ぶことにする.

秘密情報$d$の推定はMSB (Most Significant Bit, 最上位ビット) から 順に1ビットずつ進めていく. $d_{k-1}$ から $d_{k-i+1}$ までの$(i-1)$ビットを知っているときに $d_{k-i}$ の値を推定する方法を述べる.

まず,メッセージ$m$を入力して最初の$(i-2)$回のループを行い,$d_{k-i}$に よる乗算の手前まで計算が進んだ状況を考える.そのときの$x$の値を$x_{temp}$ とする.$d_{k-1}$から$d_{k-i+1}$までの値を知っていると仮定しているので, 攻撃者は$x_{temp}$の値を知ることができる.

次にメッセージ全体の集合を,$d_{k-1}$の値と,Montgomery乗算での 減算Aの有無により4つに分ける.

$d_{k-i} = 1$のとき.次に行われる演算は乗算と2乗算である.

  1. $x = mont(x_{temp}, m', n)$
  2. $x = mont(x, x, n)$

2乗算で減算Aが行われるメッセージ$m$の集合を$M_1$,行われないメッセージの 集合を$M_2$とする.

$d_{k-i} = 0$のとき.乗算は行われずに2乗算 $x = mont(x_{temp}, x_{temp},n)$のみが行われる.この2乗算で減算Aが 行われるメッセージ$m$の集合を $M_3$,行われないメッセージの集合を$M_4$とする.

このとき,$M_1$$M_2$の間の処理時間の差が大きければ$d_{k-i} = 1$であり, $M_3$$M_4$の間の処理時間の差が大きければ$d_{k-i} = 0$であると推定できる.

この方法を実際に適用した結果,128ビットべき乗剰余算では約10,000個の メッセージで,512ビットべき乗剰余算は約350,000個のメッセージで 秘密鍵$d$が完全に復元でき,その復元の速度は,前者が4ビット/秒,後者が 1ビット/分であったと報告されている [DK+98].


III.3.2.2.2 Rijndael

Koeuneらに提案された Rijndaelへのタイミング解析の適用 を説明する [KQ99].

Rijndaelの暗号化アルゴリズムの概要を図III.16に示す [DR98].

図 III.16: Rijndaelの暗号化アルゴリズム
\begin{figure}
\begin{center}
\begin{tabular}{l}
\hline
入力:平文,拡大鍵 \\
..
...\
ShiftRow() \\
AddRoundKey() \\
\hline
\end{tabular}\end{center}\end{figure}

暗号化は1番目の拡大鍵と加算を行った後にラウンド関数に入る. ラウンド関数は,ByteSub, ShiftRow, MixColumn, AddRoundKey と呼ばれる4つの変換部からなる. それぞれバイト単位での変換であり,ByteSubはS-boxによる置換, ShiftRowはある定数によるシフト,AddRoundKeyは 拡大鍵との加算を行うもので,処理時間はデータによらず一定となる. 残りのMixColumnでは,処理の中にGF$(2^8)$上での'02'倍算がある.(ここで, GF$(2^8)$の元を'02'のように表している.) Rijndaelでは, GF$(2^8)$を定義する多項式を $x^8+x^4+x^3+x+1$としているため,'02'倍算を 次のように行うことができる.

  1. 1ビット左シフト
  2. キャリーが発生したら,'1B'と排他的論理和(XOR)をとる

このように実装したとき,キャリーが発生したかどうかでXORが行われるので, 処理時間にデータに依存した差が生じる.これは'02'倍算される バイトの最上位ビットの値に依存している.

タイミング解析により1番目の拡大鍵($R_1$とする,最初のAddRoundKey で平文に加算される拡大鍵)を推定する方法を述べる.

平文を入力し,第1ラウンドのMixColumnでの'02'倍算の手前まで計算が 進んだ状況を考える ('02'倍算は平文のすべてのバイトに対して 行われるが,任意に選んだある1つのバイトに注目する). ByteSub,ShiftRow での変換は暗号化鍵に依存していないので, '02'倍算されるバイトの値は$R_1$が分かれば攻撃者は知ることができる. 逆に'02'倍算されたバイトの値が分かれば$R_1$を知ることができる.

平文のうち,第1ラウンドの'02'倍算に影響するバイトの値が$j$,その他の バイトはランダムであるようなものの集合を $S_j$とする. $S_j$に含まれる平文を多数入力して暗号化時間を計測することで, '02'倍算において'1B'とのXORが行われたかどうか推定できる. つまり'02'倍算されるバイトのMSB,したがって$R_1$のある1ビットの 値を推定できる.$k \not= j$ なる $S_k$ に対して同じことを行い, $R_1$の別の1ビットを推定できる.これを繰り返すことで$R_1$を 完全に推定できる.

$R_1$以外の拡大鍵についても同様であり,すべての拡大鍵を推定する ことができる.

128ビットブロック,128ビット鍵の場合にこの攻撃を適用した結果, 鍵1バイトあたり約3000個の平文で鍵を完全に復元できた,と報告されている [KQ99].


III.3.2.2.3 その他

以下の例はKocherによる攻撃法の原理である[Koc96].しかし,実際に攻撃に成功したという報告はなく,実用的であるか どうかは分かっていない.


III.3.2.2.3.1 中国剰余定理を用いたRSA

中国剰余定理を用いたRSAの処理手順は図III.17のとおりであり, 攻撃者から見たパラメータの関係は表III.3のとおりである.

図 III.17: 中国剰余定理を用いたRSA
\begin{figure}
\begin{center}
\begin{tabular}{l}
\hline
入力:$m, p, q, d_p, d_q...
...((s_q - s_p)A \bmod q)p + s_p$\ \\
\hline
\end{tabular}\end{center}\end{figure}


表 III.3: 攻撃者から見たパラメータ(中国剰余定理を用いたRSA)
  $m$ $p$ $q$ $d_p$ $d_q$ $A$
既知/未知 既知 未知 未知 未知 未知 未知
入力パラメータ          
解析対象パラメータ        

中国剰余定理を用いたRSAの処理でもべき乗剰余算があるが,今回は法が 秘密鍵で攻撃者にとって未知のため,III.3.2.2.1節で述べた方法は使えない.

注目するステップは最初の2ステップである. $m_p = m \bmod p$という 除算の処理時間は$m > p$$m < p$かで処理時間が異なる. 前者のほうが後者より処理時間が大きい.そのため,その処理時間を計ることで $p$の大きさをある程度絞り込むことができる.$q$についても同様である.

III.3.2.2.3.2 DSS

DSS (Digital Signature Standard)の処理手順は図III.18のとおりで あり,攻撃者から見たパラメータの関係は表III.4のとおりである.

図 III.18: DSS
\begin{figure}
\begin{center}
\begin{tabular}{l}
\hline
入力:$m, p, q, g, x$\ \...
...s = k^{-1}(h(m) + xr) \bmod q$\ \\
\hline
\end{tabular}\end{center}\end{figure}


表 III.4: 攻撃者から見たパラメータ(DSS)
  $m$ $p$ $q$ $g$ $x$ $k$
既知/未知 既知 既知 既知 既知 未知 未知
入力パラメータ          
解析対象パラメータ          

秘密鍵データ$x$を推定するために注目するステップは$s$の計算である. $s$の計算は通常, $k^{-1} \bmod q$ $(h(m)+xr) \bmod q$との剰余乗算で 行われるが, $(h(m)+xr) \bmod q$の処理時間のほうに注目する. ここで$h(m)$$m$のハッシュ値であり,攻撃者はその処理時間を計算する ことができる.また,この値は$q$程度であるため, $(h(m)+xr) \bmod q$の 処理時間はほとんど$xr \bmod q$とみなせる.$r$は署名の一部であり攻撃者に とって既知である.したがって,$xr \bmod q$の処理時間から,$xr$の値を ある程度絞ることができる.すると$x$の上位ビットを推定することができる. $x$ の上位ビットが分かると $xr$の上位ビットも分かるため, さらに$x$の次の上位ビットの値を推定していくことが可能である. このように繰り返していくことで,$x$を推定することが可能となる.


next up previous contents
Next: III.3.2.3 タイミング解析の対策 Up: III.3.2 タイミング解析 Previous: III.3.2.1 タイミング解析の原理