この記事について

この記事は，2017年に出版された Sliding right into disaster: Left-to-right sliding windows leak の論文内容をまとめたものになっております．
この論文は出版から2年が経過しており，RSA-1024がすでに危険であるという認識は浸透していると思いますが，一体どういった経緯でRSA-1024が危険であるという指摘がなされているかを説明したいと思います．

Paper Abstract

RSA復号計算にサイドチャネル攻撃を仕掛けると，秘密鍵が復元できてしまうかもよ〜，というお話です(＊注意：RSAの秘密鍵が理論的に解読可能になった，という話ではない)．

Preliminary

RSA暗号とは

RSA暗号は代表的な公開鍵暗号方式の1つであり，「素因数分解困難性」を安全性の根拠としている暗号です．暗号化・復号計算には冪剰余計算を使用しています．平文を$m$, 暗号文を$c$, 公開鍵を$(e, n)$, 秘密鍵を$d$とすると，暗号化・復号は以下の式で実行することができます．通常，$e$は$2^{16} + 1$という値を取ることが多いです．また，$n$は2つの素数$p, q$の積($n = pq$)で表すことができます．

暗号化 or 復号	計算式
暗号化	$c = m^e \bmod n $
復号	$m = c^d \bmod n$

なお実際にRSA暗号を実装する場合には，上記の計算を直接行わず，CRT(中国人の剰余定理)を用いて計算を効率化させます．例えば復号計算をしたい場合，$d_p = d \bmod (p-1)$，$d_q = d \bmod (q-1)$として，$m_p = c^{d_p} \bmod p$，$m_q = c^{d_q} \bmod q$を計算し，$m_q + q(q^{-1}(m_p - m_q) \bmod p)$を計算することによってべき乗計算を実行することができます．

冪剰余計算の高速化手法

ここからは復号計算に焦点を当てて行きます．復号計算で使用する指数$d$は，$n$のビット数と同程度の大きさとなります．したがってRSA-1024の場合，$d$の大きさは約$2^{1024}$程度となります．当然ながら，指数が莫大な数字である場合，$c^d$を計算してから$\bmod n$の剰余計算をしようとすると，計算量がとてつもないことになってしまいます．
そこで冪剰余計算を効率的に行う手法を以下に紹介します．

バイナリ法 (square-and-multiply method)
モンゴメリの冪乗法（Montgomery Powering Ladder）
CRTを用いたモンゴメリの冪乗法 (CRT Montgomery Powering Ladder)
スライディングウィンドウ法 (sliding window Modular Exponentiation)

今回紹介する論文では，スライディングウィンドウ法を用いた場合の秘密鍵復元手法を述べています．そこでスライディングウィンドウについて簡単に説明します．

スライディングウィンドウ法

例えば，$5^{3665} \bmod 24$を計算するとしましょう．
**(1)**まず指数部の3665を2進数に直します．

$3665 = (111001010001)_2$

(2)続いて，この2進数をウィンドウと呼ばれるグループに分けて行きます．デフォルトウィンドウ幅$w$を3だとして，左から順番に3つずつで区切りをつけていきます．ただし，ウィンドウの一番右は必ず1であるようにしなければいけません．仮に一番右が0になってしまう場合，ウィンドウに1が含まれていればそれを末尾ビットとするウィンドウに分けて，ウィンドウに1が含まれていない(全て0)場合は，$w$ビット分ウィンドウを拡張します．もし拡張子しても右端に1がこない場合は，先ほどと同様な操作を行います．

この操作を実行することで，3665は4つのウィンドウに分割することができます．

**(3)**分割したら，以下の操作をウィンドウの個数分だけ行います．
　　(3-1) $a \leftarrow 1$
　　(3-2) 以下をウィンドウ分繰り返す (ウィンドウ幅を$l$，ウィンドウの値を10進数化したものを$z$，基数(例でいう$5^{3665}$の5に対応するもの)を$b$とする)．
　　　　(3-square) $a \leftarrow a ^ {2 ^ l} \bmod n$
　　　　(3-multiply) $a \leftarrow a \cdot b^z \bmod n$
　　(3-3) $a$ を出力

ビット	step 3-square	step 3-multiply
1st	$1^{8} \bmod 24$	$1^{8} \cdot 5^{7} \bmod 24 = 5^{7} \bmod 24$
2nd	$(5^{7})^{8} \bmod 24$	$(5^{7})^{8} \cdot 5^{1} \bmod 24 = 5^{57} \bmod 24$
2nd	$(5^{57})^{4} \bmod 24$	$(5^{57})^{4} \cdot 5^{1} \bmod 24 = 5^{229} \bmod 24$
2nd	$(5^{229})^{16} \bmod 24$	$(5^{229})^{16} \cdot 5^{1} \bmod 24 = 5^{3665} \bmod 24$

以上の**(1) ~ (3)**を実行することで，効率的に冪剰余計算をすることができます
Sliding Window法の擬似コードを以下に示します(論文より引用)．

このように，左から右へウィンドウ分割して冪剰余を計算する手法をLeft-to-Right Sliding Window方式と言います．一方，右から左へウィンドウ分割して冪剰余を計算する手法をRight-to-Left Sliding Window方式と言います．

この論文では，Left-to-Right Sliding Window方式に対する脆弱性を指摘しています．

サイドチャネル攻撃とは

サイドチャネル攻撃とは，復号システムから漏洩する電磁波，電力消費量，実行時間等の情報を分析することによって，復号システムの機密情報(例えば秘密鍵など)を取得しようとする攻撃方法です．

論文の内容

いよいよ論文の内容に入っていきます．論文では，Left-to-Right Sliding Window(以下，単にSliding Window法という)で実装された復号システムにサイドチャネル攻撃を仕掛けるケースを考えています．
また下の例では，ウィンドウ幅$w$は全て4で話を進めています．

ここで仮定として，サイドチャネル情報(実行時間，消費電力など)を分析することによって， Sliding Windowにおける「square(擬似コード14行目)」と「multiply(擬似コード15行目)」が実行されたタイミングを記録することができるとしています．

擬似コードを注意深く参照すると，squareは秘密鍵$d$の各ビット毎に1回必ず行われ，multiplyは秘密鍵$d$のビットが1であるもののうち，特定の1しか実行されないことが分かります．

サイドチャネル攻撃によりsquare(s)とmultiply(m)を観測した列を$S \in \{ s, m \}^{*}$で表すことにします．例えば，$S = smsssssssmsmsssssm$のようにデータを観測することができます．

ここで復元秘密鍵を$d'$とし，$d' \in \{ 0, 1, \underline{1}, x, \underline{x} \}^{*}$とします．$x$は未知ビットとします．またアンダーラインはmultiplyが行われたビットを表します．

擬似コードを注意深く参照するとわかるのですが，データ列において$sm$となっている部分は，秘密鍵$d$を2進数表記した中の，どこかの「1」に対応することがわかります．つまり，$sm → \underline{1}$と置き換えることができます．
観測sm列を$S = smsssssssmsmsssssm$とすると，$d' = \underline{1}xxxxxx\underline{1}\underline{1}xxxx\underline{1}$が得られます．

秘密鍵の復元ルール

ここから秘密鍵を復元するためのいくつかのルールを紹介します．
以下のルールは，擬似コードを注意深く追っかけていくことで得られるルールとなっています．なぜこのルールが成り立つのか一度考えてみてください(いい頭の体操になります！)．

Rule1: $\underline{1}x^{i}\underline{1}x^{w-i-1} → \underline{1}x^{i}\underline{1}0^{w-i-1}$ 　　($w$はウィンドウ幅，$i = 0, ..., w-2$)

Rule2: $xxx\underline{1}\underline{1} → 1xx\underline{1}\underline{1}$

Rule3: $\underline{1}x^ix^{w-1}\underline{1} → \underline{1}0^ix^{w-1}\underline{1} $ 　　($i > 0$)

$d' = \underline{1}xxxxxx\underline{1}\underline{1}xxxx\underline{1}$にRule1~3を適用すると，

Rule1: $d' = \underline{1}xxxxxx\underline{1}\underline{1}000x\underline{1}$
Rule2: $d' = \underline{1}xxx1xx\underline{1}\underline{1}000x\underline{1}$
Rule3: $d' = \underline{1}0001xx\underline{1}\underline{1}000x\underline{1}$

このように，Rule1~3を適用することによって，秘密鍵のビットを順次復元することができます．

演習問題 (さらに大きい秘密鍵を復元してみる．)

秘密鍵$d$を$d = 0100001111100101001100110101001100001100011111100011100100001001$とします．

この秘密鍵を使用すると，サイドチャネル攻撃により以下のようなsm列を取得することができます(これは決定的に決まるものです)．

$S = ssmssssssssmssssmsssssmssssmsssmsssssmsmssssssmsssssssmssmssssssmsssmssssssssm$となります．

ここから秘密鍵を復元します．まず$sm → 1$を適用します．
$d' = x\underline{1}xxxxxxx\underline{1}xxx\underline{1}xxxx\underline{1}xxx\underline{1}xx\underline{1}xxxx\underline{1}\underline{1}xxxxx\underline{1}xxxxxx\underline{1}x\underline{1}xxxxx\underline{1}xx\underline{1}xxxxxxx\underline{1}$

ここからRule1~3を適用し，秘密鍵を出来るだけ復元してみてください！

(解答は論文のp8に掲載されています．)

秘密鍵を完全に復元する

Preliminaryでも説明した通り，実際の復号システムはCRTを用いて実装されており，$c^{d_p} \bmod p$と$c^{d_q} \bmod q$を計算する必要があります．先ほどと同様のアプローチで$d_p$と$d_q$に関する部分的なビットを復元することができます．

ここから秘密鍵$d_p$と$d_q$を完全に復元する手法を紹介します．

$d_p$と$d_q$は，以下の関係式を満たします($k_p, k_q < e$)．

$ed_p \equiv 1 + k_p(p-1)$
$ed_q \equiv 1 + k_q(q-1)$

さらに，$k_p, k_q$は以下の関係式を満たします($n = pq$)．

$(k_p-1)(k_q-1) \equiv k_pk_qn \bmod e$

このような$(k_p, k_q)$の組み合わせは高々$e$通りです($e$は$2^{16}+1$がよく使われる)．
全ての$(k_p, k_q)$の候補ついて，$d_p, d_q, p, q$の不明ビットを深さ優先探索によって復元します．

以上のプロセスを利用し，論文ではLibgcryptで実装されたRSA-1024に対して攻撃を行うことで秘密鍵が復元できてしまう可能性があることを指摘しています．