シミュレーションによる FIA 4
前回までは認証の条件分岐を潰して無理やり通す攻撃を見てきました． 今回は，暗号そのものを狙います． RSA の証明計算に 1 回だけ故障を起こすと，故障の値も位置も分からないのに秘密鍵が復元できます． これは Bellcore 攻撃 と呼ばれ，スマートカードへの FIA の端緒となったものです．
今回は CTF 形式です． 配布されたデータから秘密鍵を復元し，FLAG{} という形式のフラグを入手してください．
RSA
RSA の基本的な動作
鍵生成は以下のような方法で進みます．
- 異なる二つの大きな素数 \(p ,q\) を選ぶ
- \(n=pq\) とする
- \(φ(n) = (p−1)(q−1)\) を計算する
- \(gcd(e, φ(n)) = 1\) となる \(e\) を選ぶ (ほとんどの場合 \(e=65537\))
- \(e·d ≡ 1 (\mod φ(n))\) となる \(d\) を求める
このとき，公開鍵は \(n, e\) であり，秘密鍵は \(d\) となります．
また，暗号化，復号は以下のように進みます
- 暗号化：\(c = m^e \mod n\)
- 復号：\(m = c^d \mod n\)
署名は以下のように計算されます
- 署名：\(s = m^d \mod n\)
- 検証：\(s^e ≡ m \mod n\)
このとき，攻撃者は \(e\) と \(n\) を知っています．
復号，検証も，以下のように成立することが分かります．
\(ed ≡ 1 (\mod φ(n))\) ですので，ある整数 \(k\) について， \(ed = 1 + k·φ(n)\) です． ここで，オイラーの定理 (\(m^φ(n) ≡ 1 \mod n\)) を使うと以下のようになります
\(s^e = (m^d)^e = m^{ed} = m^{1 + k·φ(n)} = m · (m^φ(n))^k = m · 1^k = m \mod n\)
\(d\) を求めるには，\(φ(n) = (p−1)(q−1)\) が必要であり，そのためには \(n\) を \(p, q\) に素因数分解しなければなりません． これが困難であることが RSA の安全性を保証しています．
CRT による高速化
RSA-2028 では \(d\) も約 2048 bit になります． 愚直にバイナリ法で \(m^d \mod n\) を実装すると，約 2048 回の 2048 bit 乗算が必要になり，計算時間がかかります．
\(p, q\) が互いに素な場合，任意の \(a, b\) に対して， 以下を満たす \(0 ≤ x < pq\) が一つだけ存在します．
- \(x ≡ a \mod p\)
- \(x ≡ b \mod q\)
雑に言い換えると，「mod n の 1 個の値」と「(mod p の値，mod q の値) のペア」は一対一で対応するといえます． そうすると，大きい方で計算せず，小さい 2 つに分けて計算して後から戻せばよいと分かります．
さらに，フェルマーの小定理より， p が素数で a が p の倍数でないとき a^{p−1} ≡ 1 (mod p) ですので， dp = d mod (p−1) とおくと d = dp + k(p−1) であることから，
\(m^d = m^{dp} · (m^{p−1})^k ≡ m^{dp} · 1^k = m^{dp}\mod p\)
と指数まで半分にすることができます． 同様に，dq = d mod (q−1) となります．
このうえで，RSA-CRT は以下のように計算されます．
- dp = d mod (p−1)
- dq = d mod (q−1)
- qinv = q^{-1} mod p
- Sp = m^{dp} mod p
- Sq = m^{dq} mod q
次に，Garner のアルゴリズムで合成すると，以下のようになります．
- h = (Sp − Sq) · qinv mod p
- s = Sq + h · q
このとき，q を法としてみると， \(s = Sq + h·q ≡ Sq + 0 = Sq \mod q\) h·q の項は q の倍数なので 問答無用で消え，s mod q は Sq がそのまま出てきます．
また，p を法としてみると， \(s = Sq + ((Sp − Sq)·qinv mod p)·q ≡ Sq + (Sp − Sq)·qinv·q (mod p)\) qinv·q ≡ 1 (mod p) なので， \(≡ Sq + (Sp − Sq) = Sp (mod p)\)
以上より，
- s mod p：Sp に依存
- s mod q：Sq に依存
Bellcore Attack
例えば Sp に計算中に Fault が入り，Sp が誤った値になったとします． (S’p ≠ Sp ) このとき，以下のような合成が行われます．
- h’ = (Ŝp − Sq)·qinv mod p
- s’ = Sq + h’·q
先ほどと同じような手順で考えてみます． まず q を法とすると，h’·q は何であれ q の倍数なので消えます． \(s’ ≡ Sq ≡ m^d mod q\)
次に，p を法とすると，s’ ≡ S’p となりますが， \(s’ ≡ S’p ≢ m^d mod p\)
となり，さらにこれを検証の式に入れてみると，
- s’^e ≡ m mod q
- s’^e ≢ m mod p
というふうに， p は壊れていることになります．
素因数分解
このあとどのように素因数分解するかは何パターンがありますが，Lenstra のものを確認すればよいと思います．
x = s’^e − m とします． すると，以下のようになります
- x ≡ 0 (mod q) → x は q の倍数
- x ≢ 0 (mod p) → x は p の倍数ではない
すると，
\(q = gcd(s’^e − m, n)\) \(p = n / q\)
となり，d が復元できることになります． Plundervoltが分かりやすい例ではないかと思います．
参考文献
Cracking RSA: Fault Analysis
Bellcore attack in practice
CTF1
ではここまでの内容を応用して RSA に対する FIA を簡易的に体験してみましょう． 以下に問題スクリプトを記載します． ここでは既に壊れた署名が入手出来ていると仮定しています．
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import hashlib, sys
n = 129688986003962035617176676053850078147109703345024330577903358916435116332261799565471470176576903770357855981199569715735704568908663731704007577343780008078384339475510949167830865606919772609594326838640384499996367727210557344270493664757443757974880394222364869338698510749419762789441620294165763430221
e = 65537
m = 401262981676955106715366262003747230210822399845
s_good = 57622999706558380123473009322643018303967472264261743384282210025911103205086247343149531013917438827440136181406096515096125478543188202081129018271884691259021064371275488731687663961279354662661999537125971910510364845663068753193187055367445073815932675489698263046854439214078151540126079755124043907202
s_bad = 38487883162272451662896701951497262940253980603870385132711127666377454690722728113957458927097860007437185204972286869149351801679427087023013416691210932816657495579116420430560624153241100131938889071668327577097510665181783736002753484380203914901689006829491185822790094922959494404119657273518372846935
c_flag = 69226317376315456555562217513966769503396243880041204479751754130924332415167096275383309560024094311772906910523199672677622758774958885053512619591206088780500174023437754127168447576046994079695982832152304851640629749017090894372617326430968659848983310065995348502519651989806337603869163189796774877769
FLAG_SHA256 = "641b64442c6e6dfbbf66f7298fed9d6bd6bb02be17e826260037cb73bf3bbd7f"
if __name__ == "__main__":
print("n =", n); print("e =", e); print("m =", m)
print("s_good =", s_good); print("s_bad =", s_bad); print("c_flag =", c_flag)
if len(sys.argv) > 1:
ok = hashlib.sha256(sys.argv[1].encode()).hexdigest() == FLAG_SHA256
print("Correct!" if ok else "Wrong...")
引数を与えて実行すると，そのフラグが正しいかを判定してくれます．
u@u-VirtualBox:~/FIA$ python3 ctf1.py FLAG{hoge}
n = 129688986003962035617176676053850078147109703345024330577903358916435116332261799565471470176576903770357855981199569715735704568908663731704007577343780008078384339475510949167830865606919772609594326838640384499996367727210557344270493664757443757974880394222364869338698510749419762789441620294165763430221
~~ snip ~~
c_flag = 69226317376315456555562217513966769503396243880041204479751754130924332415167096275383309560024094311772906910523199672677622758774958885053512619591206088780500174023437754127168447576046994079695982832152304851640629749017090894372617326430968659848983310065995348502519651989806337603869163189796774877769
Wrong...
u@u-VirtualBox:~/FIA$ python3 ctf1.py FLAG{...}
n = 129688986003962035617176676053850078147109703345024330577903358916435116332261799565471470176576903770357855981199569715735704568908663731704007577343780008078384339475510949167830865606919772609594326838640384499996367727210557344270493664757443757974880394222364869338698510749419762789441620294165763430221
~~ snip ~~
c_flag = 69226317376315456555562217513966769503396243880041204479751754130924332415167096275383309560024094311772906910523199672677622758774958885053512619591206088780500174023437754127168447576046994079695982832152304851640629749017090894372617326430968659848983310065995348502519651989806337603869163189796774877769
Correct!
追加課題
この攻撃を対策するにはどうしたらよいでしょうか？ 攻撃者が何を入手できてしまったことが問題なのかを考え，コードを書く側の立場からどのような機能を追加するべきか考えてみてください．