だいぶ遅れましたが例の「RSA-1024がやられた」の攻撃の詳細を解説したペーパーである「Sliding right into disaster: Left-to-right sliding windows leak」の解説をします。
TL;DR
というよりは「攻撃の詳細な解説はいいから何すればいいんだ」という人向け。
以下本文。
Windowing in Modular Exponentiation
RSA暗号ではModular exponentiation(冪剰余)の計算が行われるが、その最適化の方法によっては、キャッシュベースのサイドチャネル攻撃で「2乗(squaring)」「乗算(multiplication)」の演算のパターンが漏洩し、その情報を用いてRSAの秘密鍵に相当する冪剰余演算の指数の値を求めることができる。
よく使われる最適化には、巨大な指数の冪乗を一気に計算する代わりに、予め小さい指数の冪乗を計算しておき、本来計算すべき指数を小さい指数の冪乗とsquaringの組み合わせで計算できるようにする「windowing」という方法がある。この方法では、指数dを以下のような形式で表記する:
上記に出てくる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の列からビット列を再構成
(実際の例は論文本体を参照してください、けっこう長くて転記ミスが怖いw)
- squaringはdの各bitごとに1回
- multiplicationは指数のいくつかのbitにしか行われない
ことから、ビット列を以下のように表現できる:
(0,1 は既知、xは未知、_はmultiplicationが行われる場所)
ここから以下のルールでビット列を再構成する(*原文中では0〜3):
- windowed formの各桁は奇数なので、multiplicationはsetされているbit(=1であるbit)で起こる
- 2つのmultiplicationがwビット以内の距離にあれば、2つ目のmultiplicationにはそれ以上set bitが含まれなかったということになる。よって、2つ目のmultiplicationのbitの右に、「1つ目のmultiplication bitの1つ右からw個目まで」trailing zeroを付与
- 1xxxxxx11xxxx1 (w=4)の場合、
- 1xxxxxx11000x1 となる
- 2つのmultiplicationが連続したbitで行われていた場合、左のbitの桁を組み立てる際にはtrailing zeroは存在しなかったことがわかる。
- 1xxxxxx11000x1 (w=4)の場合、連続する1の左側の1は[1xx1]というウィンドウの一部だったことがわかるので、
- 1xxx1xx11000x1
- これがLeft-to-Rightで漏れる追加の情報
- それぞれの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の計算をする場合、
の代わりに
を計算するが、この d_p と d_q についてsquare, multiplyの列が得られたとして、Heninger and Shachamのアルゴリズムの拡張を用いてRSA鍵の復元を行う。
- d_pとd_qは
を満たす。ここで、
より、k_p, k_qの組は高々e通り調べればよい。eはだいたいの場合65537。異なる値は即時解なしになるので除外できる。
- d_pとd_qについていくつかのbitは既知なので、k_p, k_qの候補を用いて、d_p, d_q, p, qの不明bitについて深さ優先探索をする。
実際に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の機能を使って行われた。