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 タイミング解析の原理