【論文紹介】Sliding right into disaster: Left-to-right sliding windows leak【RSA-1024続報】

crypto tech

だいぶ遅れましたが例の「RSA-1024がやられた」の攻撃の詳細を解説したペーパーである「Sliding right into disaster: Left-to-right sliding windows leak」の解説をします。

TL;DR

というよりは「攻撃の詳細な解説はいいから何すればいいんだ」という人向け。

  • RSA暗号、RSA-1024そのものの理論的突破ではない
    • （今回の解説の範囲外だが）そもそもRSA-1024は対称鍵暗号の80ビット相当の安全性しか持たず、政府機関クラスの予算があればbrute forceで突破可能であり、TLSの証明書では既に2048bitへの移行が進んでいる
  • 攻撃が成立する条件は秘密鍵が存在するマシン上での任意コード実行
    • そもそもそんな状況許したらゲームセット、というのはパッチノートの通り
    • ただし、原理的には仮想環境で他のVMから攻撃を仕掛けられる可能性はある。メモリレイアウトを正確に知る必要があるので非常に困難ではあるが…

以下本文。

Windowing in Modular Exponentiation

RSA暗号ではModular exponentiation(冪剰余)の計算が行われるが、その最適化の方法によっては、キャッシュベースのサイドチャネル攻撃で「2乗(squaring)」「乗算(multiplication)」の演算のパターンが漏洩し、その情報を用いてRSAの秘密鍵に相当する冪剰余演算の指数の値を求めることができる。

よく使われる最適化には、巨大な指数の冪乗を一気に計算する代わりに、予め小さい指数の冪乗を計算しておき、本来計算すべき指数を小さい指数の冪乗とsquaringの組み合わせで計算できるようにする「windowing」という方法がある。この方法では、指数dを以下のような形式で表記する：

\displaystyle d = \sum^{n-1}_{i=0} d_{i} 2^{i} \mbox{ where } d_i = 0 \mbox{ or odd number between } 1 \mbox{ and } 2^{w-1}

上記に出てくるwがウィンドウ幅であり、この幅の分だけ指数を予め計算する、ということをする。

windowingにはleast significant bit(LSB)からmost significant bit(MSB)までの順でwindowingを行うRight-to-Left方式とその逆の順で行うLeft-to-Right方式がある。w=3, d=181(10110101)の例では、Right-to-Leftでは10030005、Left-to-Rightでは500501というようにエンコードされる。（ここで0が多く出てくるので必要な乗算演算の数が減っていて、これが最適化のポイント）

LibgcryptではLeft-to-Right方式が採用されており、これがRight-to-Left方式よりも多くのビット情報を漏らしてしまうため攻撃が可能になった、というのがこの論文の主なcontribution。

SquareとMultiplyの列からビット列を再構成

（実際の例は論文本体を参照してください、けっこう長くて転記ミスが怖いｗ）

  • squaringはdの各bitごとに1回
  • multiplicationは指数のいくつかのbitにしか行われない

ことから、ビット列を以下のように表現できる：

\displaystyle s \in \left\{ 0, 1, \underline{1}, x, \underline{x} \right\}^{*}

（0,1 は既知、xは未知、_はmultiplicationが行われる場所）

ここから以下のルールでビット列を再構成する（＊原文中では0〜3）：

  1. windowed formの各桁は奇数なので、multiplicationはsetされているbit(=1であるbit)で起こる
  2. 2つのmultiplicationがwビット以内の距離にあれば、2つ目のmultiplicationにはそれ以上set bitが含まれなかったということになる。よって、2つ目のmultiplicationのbitの右に、「1つ目のmultiplication bitの1つ右からw個目まで」trailing zeroを付与
    • 1xxxxxx11xxxx1 (w=4)の場合、
    • 1xxxxxx11000x1 となる
  3. 2つのmultiplicationが連続したbitで行われていた場合、左のbitの桁を組み立てる際にはtrailing zeroは存在しなかったことがわかる。
    • 1xxxxxx11000x1 (w＝4)の場合、連続する1の左側の1は[1xx1]というウィンドウの一部だったことがわかるので、
    • 1xxx1xx11000x1
    • これがLeft-to-Rightで漏れる追加の情報
  4. それぞれのset bitはwindowed formの0でない桁に含まれているはず。よって、最低でもmultiplicationから左にw-1ビット以内にしか存在しない。よって、wビット以上離れていたら、0しか間に存在し得ない。
    • 1xxx1xx11000x1 (w=4)は
    • 10001xx11000x1 になる

以上を繰り返し適用するともう少し明らかになることがある。

（続く3.2、3.3章はLeft-to-Rightで理論上/実際どれくらいの割合のbitが明らかになるか、という考察だが、ちょっと手に負えなかったのでスキップ）

RSA keyの復元

中国の剰余定理でRSAの計算をする場合、

s = h(m)^{d} \mod N (N = pq)

の代わりに

s_p = h(m)^{d_p} \mod p, s_q = h(m)^{d_q} \mod q

を計算するが、この d_p と d_q についてsquare, multiplyの列が得られたとして、Heninger and Shachamのアルゴリズムの拡張を用いてRSA鍵の復元を行う。

  • d_pとd_qは ed_p = 1 + k_p(p-1), ed_q = 1 + k_q(q-1) (k_p, k_q \lt e) を満たす。ここで、 (k_p - 1)(k_q - 1) = k_pk_qN mod eより、k_p, k_qの組は高々e通り調べればよい。eはだいたいの場合65537。異なる値は即時解なしになるので除外できる。
  • d_pとd_qについていくつかのbitは既知なので、k_p, k_qの候補を用いて、d_p, d_q, p, qの不明bitについて深さ優先探索をする。
    • i bit目までについて、RSAの鍵として成立する条件を満たすかどうかで探索を打ち切る方法(3.4で説明されている方法)では、50%前後のbitがわかっていないと有効な時間で終わらない
    • d_p, d_qのi bit目について、square-and-multiply sequenceを成立させるかどうかで探索を打ち切る深さ優先探索を行うと上記の方法より効率よく探索できる(4章の内容)

実際にsquare-and-multiply sequenceを得るには？

Flush+Reload attackという方法を使う。

  • 共有のメモリ領域を監視する
  • 見張っているメモリ領域をclear。x86のclflush命令など。
  • 待機
  • その後メモリ領域にアクセス。victimがメモリ領域にアクセスしていればキャッシュされているので速い。そうでなければキャッシュミスなので遅い。

これだけではできなかったので以下の工夫が行われた：

  • Libgcryptはsquaringにもmultiplicationと同じコードを使う。なので別々のコードを見張って区別することができない。よって、squareとmultiplyそのものを見張るのではなく、そのoperation間の別のコードを見張った。
  • 時間解像度を得にくかった。なのでamplification attackという方法で全体を遅らせた。
  • probe missを避けるため、実行パス中の2箇所をprobeすることでケア。

実際の攻撃はFR-traceというMastik Toolkitの機能を使って行われた。