Intmax Anti-AGI Cryptographers CTF: 5問中、2問を解きました

こんにちは！弐号です。

友人が運営しているEthereumのL2 zk-Rollupソリューション開発のIntmaxさんがCTF (Capture the Flag; ハッキング大会みたいなもの) を開催するとのことで参加したレポートです。

問題は以下のURLからアクセスすることができます。

https://medium.com/@intmax/anti-agi-cryptographers-ctf-4b5e5c25c1bc

この記事では、僕が正解した Problem 1 および Problem 2 について、問題文の解説および解答の考え方を紹介します。

Problem 1

問題文の解説

準同型暗号 (Homomorphic Encryption; HE) を用いた2パーティ (Alice, Bob) のECDSA署名システムにおいて、Bob の署名用サーバ (任意のメッセージに対して署名を行うオラクルとして動作する) が与えられたときに、不正な値を Bob のサーバに送信することで Bob の秘密鍵を窃取せよ、というのが問題になります。

まずECDSA署名について復習しましょう。

ECDSAにおいては G を利用する楕円曲線のベースポイントとし、dを秘密鍵、mをメッセージとすると

k \leftarrow^R \mathbb{Z} \\
r := (kG)_x \\
s := k^{-1} (m + rd)

としたときの (r, s) の値が署名となる、というものです。

これを2パーティ間でのマルチシグとする場合には、AliceとBobがそれぞれkの値をランダムに選出し

r := ((k_a k_b) G)_x \\
s := (k_a k_b)^{-1} (m + r d_a d_b)

と計算すればOKですね。

この式をAliceとBobが互いに相手の秘密情報を知ることなく計算することは普通にやると不可能なのですが、準同型暗号を用いると計算することができます。

ここで \text{enc}_a, \text{enc}_b をそれぞれAliceとBobの準同型暗号による暗号化関数とすると

  1. Bobがk_bGをAliceに送信
  2. AliceはBobからもらった値をもとに\text{enc}_a(k_a^{-1} (m + rd_a)), \text{enc}_a(k_a^{-1} m)を計算しBobへ送信する
  3. Bobは\text{enc}_a(k_a^{-1} (m + rd_a)) \times k_b^{-1} d_b + \text{enc}_a(k_a^{-1} m) \times k_b^{-1} (1 - d_b)を計算しAliceへ返却する
  4. AliceはBobから帰ってきた暗号文を復号し目的の署名を得る

というプロトコルを実装することで、2パーティのECDSA署名が完成します。

問題では、Bobの処理がオラクルとしてサーバ側に実装されているので、Bobに対して何らかの不正な値を送信することでBobの秘密鍵を窃取すればよいです。

考え方

この問題の解法を考えるにあたって、まずはサーバ側の実装 (秘密鍵は公開されていませんが、サーバ側の実装は公開されています) を読み込んでみましょう。

すると、APIとして

  1. Bobの公開鍵を取得 (/bob-key)
  2. Bobがランダムに生成するkの値を準同型暗号で暗号化したものを返す (/bob-k-value)
  3. 準同型暗号の計算をして返却する (/step2)

が存在することに気づきます。

メインの処理は /step2 であり、それ以外のAPIは補助的なものとなります。

Bobが何らかの計算処理を行うのは主に/step2ですので、このstep2に脆弱性がありそうです。

しかし、メイン処理となるstep2はかなり複雑な計算式となっており、このままだとこんがらがってしまいます。

そこでもっと単純化して考えてみましょう。

すると入力として

  • \text{enc}_b(k_b)
  • \text{enc}_a(\alpha)
  • \text{enc}_a(\beta)

をとり、

\text{enc}_a((\alpha d_b + \beta (1 - d_b)) k_b^{-1})

を返す、ということが分かります。

この暗号文の復号鍵はAliceが持っていますので、実質的にこの値が手に入ります。

全体に k_b^{-1} がかかっているのがちょっと邪魔ですね。

ところがここでミソになるのが、/step2というAPIでは\text{enc}_b(k_b) を Bob に直接渡しているというところです。

ですので、Aliceが例えば \text{enc}_b(1) という値を渡してしまえば、この邪魔な k_b は勝手に消えてくれます。

そうすると、さらに \alpha = 1, \beta = 0 とすることで、Bobの返却する値は

\text{enc}_a(d_b)

となり、直接的にBobの秘密鍵が手に入りますね！

解答

ここまで分かればあとは簡単で、ソースコードを見ながら適切に不正な値を/step2のAPIに送るだけです。

実際に僕が作成したコードのURLを以下に貼っておきます。

https://github.com/leohio/anti-agi-cryptographers-ctf/pull/3/files#diff-df11d6f882f858ad3c1517814e3b5b0105300cb57318040f67741e8a924b040c

想定解答

以上が僕の解答なのですが、この解答を送ったところ問題の作者より「実装が間に合わず k_b の値を指定できていまっていたが、想定解答は k_b の値を指定できない場合のものである」との指摘を受けました。

プロトコル上 k_b の値をAliceとBobの間で送り合う必要があるので、このような実装に意図せずなってしまったようです。

この攻撃ベクトルについては、k_b の値に紐付いたセッションIDを作成して別途保存したり、enc_b の暗号鍵 (今回の実装では ECDSA署名用の鍵と共通) を変えてAliceに分からないようにすれば塞ぐことができます。

では、もし実装上 k_b の値を勝手に指定できないようになっていたらどのように攻撃すればいいでしょうか？

Bobの返却する暗号文を復号したものに対して \text{mod} \alpha, \beta を考えると

  • \beta (1-d_b) k_b^{-1} \mod \alpha
  • \alpha d k_b^{-1} \mod \beta

という値が手に入ります。

法が異なるので少々工夫が必要ですが、\alpha, \beta として異なる大きな素数を送ってあげれば、この２つの値から k_b および d_b の値を復元することができます。

Problem 2

問題文の解説

こちらの問題はAlice, Bobによる2パーティのBLS署名プロトコルに対して、与えられたメッセージに対して有効な署名を、Aliceの秘密鍵を知ることなく作成せよ、という問題です。

正解の秘密鍵は、サーバ側でBLS署名のチェック処理に成功した場合に返却されるようになっています。

ここでBLS署名の復習をしておくと、e をペアリング、Mをメッセージ (に対応する楕円曲線上の点) としたとき、署名は

s := dM

であり、

e(s, G) = e(M, dG)

という等式が成り立てば正しい署名である、というものです。

これのマルチパーティバージョンとして、問題の実装ではAliceとBobの公開鍵をそれぞれP_a, P_bとしたときに

w(P) := P_x \% 19 + 7

という重み付けをした合成公開鍵

P := w(P_a) P_a + w(P_b) P_b

を公開鍵として検証するというものです。

重み付け関数 w(P) の中身はソースコードを読むと上記のようになるのですが、問題の解答にこの関数の中身は関係ありませんので、ともかくそのような適当な重み付けをして合成した鍵を公開鍵にする、と認識してください。

考え方

この問題の解法のミソは、Bobの公開鍵を任意に指定できるという点です。

実はこのような単純なマルチパーティ署名モデルにおいては、Bobが公開鍵を任意に指定できるとすると「Rogue key attack」と呼ばれる攻撃が実行できてしまうことが知られています。

具体的には、Bobの公開鍵として例えばG-P_aを指定すると、重み付け関数がなければ合成公開鍵はただのGになってしまいますので、秘密鍵が自明 (1) になってしまいます。

今回の問題では重み付け関数を導入することでこの攻撃を緩和させているようですが、重みが19通りしかありませんので、Aliceの公開鍵がBobの公開鍵の重みと同じ重みを持つような鍵を適当に作ってあげればいいだけです。

そのためにはkを適当な整数としてBobの公開鍵としてkG-P_aとして、kをランダムに変えながら同じ重みになるkを探すだけです。

この問題のパラメータの場合にはk=1で重みが一緒になりますので、結局Bobの公開鍵としてG-P_aを指定することで、Aliceの秘密鍵を知ることなくマルチパーティBLS署名を正しく作成することができてしまいます。

解答

以上を踏まえると、以下のようなコードが正解となります。

https://github.com/leohio/anti-agi-cryptographers-ctf/pull/2/files

今回の攻撃を防ぐためには、重み付け関数の値域を十分に大きく取り、衝突しないようにしてあげる必要があります。

DeFIREでは既にこのアルゴリズムを公開しておりますので、以下の記事も合わせてご覧ください。

BLS署名の集約署名

DeFIREの記事をちゃんと読んでいれば、誰でも正解できる問題だったと思います。

問題文を読んだ瞬間に「rogue key attack かな……？」と思いましたので、コードを書く時間も含めて30分くらいで正解を当てることができました。

なのでこれは一番簡単な問題だったと思います。

まとめ

Problem 1 は ECDSA、Problem 2 は BLS 署名という比較的原始的な暗号プリミティブの知識だけで正解できる問題でしたので、すぐに解くことができました。

それ以外の問題については残念ながら使われている暗号プリミティブにあまり詳しくないため、未だに理解できていませんが、全問正解できるくらいの知識を蓄えていきたいと思っています。

最後に、このような面白いCTF大会を開催していただいたIntmaxさん (極度妄想さん) に感謝です。

今後も定期的に開催するようなので、時間があればまた挑戦させていただきたいと思います。 (次は全問正解するぞ！！！)

ではでは！

関連記事