GG18/GG20 プロトコルのセキュリティ脆弱性分析

著者：Max ，Safeheron

背景

最近、Fireblocks チームは GG18、GG20、Lindel 17 MPC プロトコルにおける 0-day 脆弱性を公表しました。この脆弱性により、攻撃者は一組の MPC 秘密鍵の断片の背後にある真の鍵を抽出することができます。

この問題が公表される前に、Fireblocks チームは Safeheron と連絡を取り、積極的なコミュニケーションを行いました。Safeheron がオープンソースの GG18/GG20 MPC プロトコルを厳密に論文の内容に従って実装しているため、このバージョンのオープンソースアルゴリズムを使用すると、同様の攻撃を受ける可能性があります。脆弱性が公表される前に、Safeheron はオープンソースプロジェクト内の脆弱性を修正しており、Fireblocks チームもパッチの有効性を確認するのを支援しました。

Fireblocks チームは、Safeheron の C++ ベースのオープンソース GG18/GG20 プロトコルを使用して POC を構築し、脆弱性を示し、コミュニティが理解できるようにしました。

Safeheron の商業版サービスにおける GG18/GG20 MPC プロトコルは、CMP20/CGGMP21 における関連するゼロ知識証明を追加しているため、この脆弱性の影響を受けません。

脆弱性の影響範囲

この記事では、脆弱性が GG18 と GG20 に与える影響に重点を置いています。GG18/GG20 プロトコルに対して、攻撃者は特別な Paillier 鍵を構築することにより、MPC 署名段階で攻撃を完了させます。有限回の署名を通じて、攻撃者は他の参加者の秘密鍵の断片を解読することができます。

この脆弱性の影響範囲は広範囲にわたります。MPC プロトコルの安全性の仮定に影響を与えるため、ほぼすべての主流のオープンソース GG18/GG20 プロトコルの実装がこの脆弱性の影響を受けています。

脆弱性の原理

MPC プロトコルをどのように攻撃するのでしょうか？一般的な MPC プロトコルは、安全性の仮定の下で証明可能な安全性を持つため、MPC プロトコルに対する攻撃は通常、プロトコルが依存する安全性の仮定に焦点を当てます。安全性の仮定は、MPC プロトコルの基礎のようなものであり、安全性の仮定が成立しなければ、MPC プロトコル全体に影響を与えることになります。

GG18/GG20 を例にとると、この MPC プロトコルは Paillier 同型暗号アルゴリズムの安全性に依存しています。Paillier 同型暗号アルゴリズムは、複合剰余類の困難な問題に基づいて設計されており、加算演算を満たす広く使用されている同型暗号アルゴリズムです。今回の脆弱性は、Paillier 同型鍵の構築に着目し、段階的に攻撃を進め、$$MtA$$ プロトコルと関連するゼロ知識証明プロトコルを攻撃し、最終的に有効な攻撃を形成しました。

攻撃の核心的な論理は次のとおりです：

（1）KeyGen サブプロトコル段階で、攻撃者は安全でない同型鍵を構築します。
（2）Sign サブプロトコル段階：
（a）二者間で実行される $$MTA$$ プロトコルにおいて、例えば $$MtA(k,x)$$ と $$MtA(k,\gamma)$$ プロトコルの中で、攻撃者は自身の安全でない同型鍵に基づいて不正な $$k$$ 値を構築します；
（b）安全でない同型鍵の特性を利用して、悪意のあるゼロ知識証明を構築し、他の参加者を欺くことに成功します；
（c）攻撃者は被攻撃者と署名を完了し、プロセス中の $$\mu$$ を記録します。
（3）複数回 Sign サブプロトコルを繰り返し、中国剰余定理に基づいて相手の秘密鍵の断片を計算します。

脆弱性の攻撃方法

このセクションでは、攻撃の詳細を詳しく説明します。一般的な MPC 門限多重署名シナリオには複数の参加者が存在し、これらの参加者は二者間で攻撃を開始でき、攻撃方法は完全に同じです。

攻撃方法を説明するために、ここでは MPC ウォレットが三者 Party A、Party B、Party C によって共同で作成および使用されると仮定します。各参加者はそれぞれの秘密鍵の断片 $$xA$$、$$xB$$、$$xC$$ を管理します。この脆弱性を利用して、Party A は Party B と Party C を攻撃して相手の秘密鍵の断片を取得できます。このセクションでは「Party A が Party B を攻撃しようとする」例を挙げて、Party B の秘密鍵の断片 $$xB$$ を抽出する方法を紹介します。（Party A は同様の方法で Party C の秘密鍵の断片 $$x_C$$ を抽出できますが、ここでは繰り返しません。）

4.1 準備段階------安全でない同型鍵の構築

最初の攻撃は KeyGen サブプロトコルの実行中に発生し、これを攻撃準備段階と呼ぶことができます。攻撃者 Party A は、安全でない Paillier 同型鍵を成功裏に構築しました。

正常な同型鍵の構築プロセスは次のとおりです：

• 安全な素数 $$p, q \in \{0,1\}\^{1024}$$ をランダムに選択します。
• 計算します。
• $$ N_A = p * q$$
• $$\lambda_A = (p-1)*(q-1)$$

攻撃者 Party A の同型鍵の構築プロセスは次のとおりです：

• 素数 $$(p1, p2, …, p{16}, q)$$ をランダムに選択します。ここで $$pi$$ は互いに異なる小素数であり、$$q$$ は大素数です。
• 計算します。
• $$ NA = \Pii{pi} * q$$、$$NA$$ の長さは 2048 ビットです。
• $$\lambdaA = \Pii(p_i-1)*(q-1)$$

攻撃者 Party A が構築した Paillier 公開鍵 $$N_A$$ には大量の小因子が含まれていることがわかります。攻撃者 Party A が構築した不正な Paillier 鍵は Party B を欺くことができるのでしょうか？結局、ここでは Party B が検証するためのゼロ知識証明を構築する必要があります。

上の図に示されている GG18/GG20 の $$KeyGen$$ プロトコルを注意深く観察すると、ここでは $$ Square-Free $$ ゼロ知識証明を提供するだけで済むことがわかります。攻撃者が構築した Paillier 同型公開鍵 $$N_A $$ には互いに異なる素因子しか含まれていないため、この構築方法は明らかに $$ Square-Free $$ ゼロ知識証明を通過することができます。

4.2 攻撃段階：Sign サブプロトコル

注意してください。攻撃は 16 回の Sign サブプロトコルを成功裏に実行する必要があります。現在は第 $i$ 回の Sign サブプロトコルを実行していると仮定します。
Sign サブプロトコルでは、最初の数ラウンドで $$MtA$$ プロトコルを実行する必要があります。GG18 (https://eprint.iacr.org/2019/114.pdf) の 4.2 節を参照してください。

• $$ MtA(kA, \gammaB) : \alphaA + \betaB \leftarrow kA * \gammaB$$
• $$ MtA(kA, xB) : \muA + \nuB \leftarrow kA * xB$$

正常な計算プロセスは次のとおりです：

• ランダムに $$k_A \in Zq$$ を選択します。
• $$Enc(k_A)$$ を計算します。
• $$MtA$$ プロトコルを実行します。
• $$ MtA(kA, \gammaB) : \alphaA + \betaB \leftarrow kA * \gammaB$$
• $$ MtA(kA, xB) : \muA + \nuB \leftarrow kA * xB$$
• ランダム数 $$kA$$ の暗号文 $$Enc(kA)$$ に関するゼロ知識証明を生成します。GG18 (https://eprint.iacr.org/2019/114.pdf) の A.1 節 Range Proof を参照してください。
• その後、正常に MPC Sign サブプロトコルを完了します。

攻撃者の計算プロセスは次のとおりです：

• 特殊な $$k_A$$ 値を構築します。
• 特殊に構築された $$k_A$$ 値を使用して、正常に $$MtA$$ プロトコルを実行します。
• 悪意のあるゼロ知識証明を構築し、欺瞞を実施します。
• その後、正常に MPC Sign サブプロトコルを完了します。

次に、その具体的な操作方法を紹介します。

特殊な $$k_A$$ 値の構築

攻撃者はランダム値を使用せず、第 $i$ 回の MPC Sign サブプロトコルで次のように $$kA$$ を構築します。 ​$$ kA = NA / pi $$
注意してください。この特殊に構築された $$k_A \gg q\^3$$ は、正常な場合には期待されるゼロ知識証明を通過できなくなります。ここで $$q$$ は楕円曲線の階です。

ゼロ知識証明の構築

GG18 プロトコルは、攻撃者が $$MtA$$ 実行段階で有効なゼロ知識証明を提供することを要求します。GG18 (https://eprint.iacr.org/2019/114.pdf) の A.1 節 Range Proof を参照してください。このゼロ知識証明は次のことを証明できます：

• Witness: $kA' = 0 \ne kA$、その他のランダム数
• Statement： $Enc{NA}(kA)$ は $$kA'$$ の暗号化された暗号文であり、$$k_A \in (-q\^3, q\^3) $$ を満たします。

注意してください。上記は不正な Statement です。なぜなら：
-$$Enc{NA}(kA)$$ は $$kA'=0$$ の暗号化された暗号文ではありません。
-$$k_A \gg q\^3$$ です。

正常な場合、GG18 プロトコルにおけるこの Range Proof は完全に有効であり、攻撃者はこの Statement を検証に通過させるゼロ知識証明を構築することが困難です。

では、攻撃者 Party A はどのように障害を突破するのでしょうか？この時、攻撃者 Party A が KeyGen プロトコル段階で構築した安全でない Paillier 鍵 $$N_A$$ を利用する必要があります。安全でない Paillier 鍵があるため、悪意のあるゼロ知識証明を構築する機会が得られます。

GG18/GG20 プロトコルにおけるゼロ知識証明プロトコルの説明は次のとおりです：

Verfier の検証プロセスにおいて、最も重要なのは暗号文の制約に対する恒等式（赤枠部分）を満たすことです：

$$ u = \Gamma\^s s\^N c\^{-e} \pmod {N\^2} $$
攻撃のテクニックは、合理的な挑戦値 $$e = Hash(…, w, )$$ を構築し、次の条件を満たすことです：$$e \pmod {pi} = 0$$ $$c = (1+NA)\^kA * \rho\^NA \mod (NA\^2)$$, $$kA = NA/pi$$
$$\begin{align*}
c\^e \&= ((1+NA)\^kA * \rho\^NA)\^e \&\mod (NA\^2) \\
\&= (1+NA)\^{ekA} * \rho\^{eNA} \&\mod (NA\^2) \\
\&= (1+NA)\^{bpi * NA/pi} * \rho\^{eNA} \&\mod (NA\^2) \\
\&= \rho\^{eAN} \&\mod (NA\^2) \\
\&= Enc{NA}(0)\^e \&\mod (N_A\^2) \\
\end{align*}$$

ここで $$c$$ を $$k_A'=0$$ の暗号文に「変換」することにより、ゼロ知識証明を成功裏に構築しました。

注意してください。ここでは構築プロセス中に $$\gamma$$ を暴力的に反復し、1 を加え続け、$$w$$ を更新することで、$$e \pmod {pi} = 0$$ を満たすことができます。モジュラス $$pi$$ は小素数であるため、完全に暴力的に反復して成功することができます。

Party B の秘密鍵の断片のモジュラス $$p_i$$ 残余の計算

攻撃者は被攻撃者と Sign サブプロトコルを完了し、さらに $$MtA$$ プロトコルの $$\muA$$ 値を記録します。 $$ \muA = kA * xB + \nuB \pmod {NA}$$
最新版の GG18 論文を考慮すると、$$\nuB \le q\^5$$、 $$ \muA = Dec{NA}(Enc{NA}(kA * xB + vB))$$ $$\begin{align*} \muA - (\muA \mod (NA/pi)) =\& Dec{NA}(Enc{NA}(kA * xB + \nuB)) - (Dec{NA}(Enc{NA}(kA * xB + \nuB)) \mod (NA/pi))\\ =\& (xB \mod pi) * (NA/pi) + \nuB - \nuB \\ =\& (xB \mod pi) * (NA/p_i)
\end{align*}$$

これにより：

$$xB \pmod {pi} = (\muA - (\muA \mod (NA/pi)))/(NA/pi) $$
$$ai = (\muA - (\muA \mod (NA/pi)))/(NA/p_i) $$

等式の右側はすべて攻撃者が既知のパラメータであるため、攻撃者は $$ai$$ を計算できます。 したがって、$$xB = ai \pmod {pi}$$ を得ることができます。

4.3 収束段階：被攻撃者の秘密鍵の断片を計算する

16 回の成功した MPC Sign サブプロトコルを実行した後、次のようになります。

$$ xB = a1 \pmod {p1}$$ $$ xB = a2 \pmod {p2}$$
$$ … $$
$$ xB = a{16} \pmod {p_{16}}$$

$$p1 * p2 *… * p{16} > q$$ であるため、中国剰余定理に基づいて、攻撃者 Party A は Party B の秘密鍵の断片 $$xB$$ を計算できます。攻撃成功。

4.4 攻撃の効果

GG18 論文には 2 つの実装バージョンがあり、修正版と旧版があり、異なるバージョンに対する攻撃の効果は異なります。

• 修正版論文では、$$MtA$$ プロトコルで使用される $$\betaB \< q\^5$$（前述の $$\nuB$$ に対応）を使用し、上記の攻撃方法を採用することで、16 回の署名で攻撃者は被攻撃者の秘密鍵の断片を解読できます。
• 旧版論文では、$$MtA$$ プロトコルで使用される $$\betaB \< NA$$（前述の $$\nuB$$ に対応）を使用し、上記の攻撃方法の変種を採用して攻撃を実施する必要があります。ここでは追加の説明は行いません。大量の推測実行が必要であり、少なくとも 10\^6 回の署名試行が必要です。攻撃者が被攻撃者の秘密鍵の断片を解読する可能性があります。より正確には、$$\tau\^l$$ の確率で相手の秘密鍵の断片を成功裏に抽出するために必要な署名回数は： $$\sum{i=1}\^nf\tau(pi)$$ 回です。

ここで、$$f_{\tau} (p) = log(1-\tau) / log(1-1/p\^2)$$。Fireblocks の論文における対応する公式には書き間違いがあり、ここで修正しました。

注意：GG18 修正版論文では、著者が多くの安全な修正提案を提供しているため、この MPC プロトコルを実装する際は修正版に基づいて実装するべきです。

実際のシナリオ攻撃の例

上記の章では、この脆弱性の原理とアルゴリズムレベルの攻撃方法を説明しましたが、MPC に基づく自己管理型ウォレットの実際のアプリケーションシナリオにおいて、使用される MPC プロトコルにこの脆弱性が存在する場合、攻撃をどのように完了するのでしょうか？

この脆弱性は t/n 門限に影響を与えます。理解を容易にするために、MPC ウォレットの参加者を 2 人の Party A と Party B と仮定し、署名の門限を 2/2 とします。ここで、Party A に対応する秘密鍵の断片はユーザーが保持し、ウォレット提供者が提供するモバイルアプリで管理および使用します。Party B に対応する秘密鍵の断片はウォレット提供者が保持し、クラウドに保存および使用されます。

攻撃を完了するために、攻撃者は以下の能力を持つ必要があります：

（1）ウォレット提供者がウォレットを作成し、取引を開始する実装ロジックとメカニズムを把握すること。
（2）ウォレット提供者のアプリを模倣し、MPC プロトコルを使用してウォレットを作成し、取引に署名することができること。

これにより、攻撃者は攻撃を開始できます：

（1）アプリを模倣してウォレットを作成し、ウォレットを作成する際に（KeyGen サブプロトコルに対応）、ローカル Party A MPC プロトコルで安全でない同型鍵を構築し、その同型鍵を使用してウォレットを作成し、ローカル Party A の秘密鍵の断片 $$xA$$ を取得します。 （2）アプリを模倣してそのウォレットを使用し、16 回の取引署名を正常に開始します（Sign サブプロトコルに対応）。その際、毎回 MPC プロトコルで悪意のある $$kA$$ と悪意のあるゼロ知識証明を構築し、16 回の署名を完了し、各署名の $$\mu$$ を収集します。

上記の操作を完了した後、攻撃者は作成したウォレットに対応するクラウド上の Party B の秘密鍵の断片 $$xB$$ を取得できます。署名の門限が 2/2 であるため、攻撃者はローカルで秘密鍵の断片 $$xA$$ を取得し、同時に攻撃プロトコルを通じてクラウドの秘密鍵の断片 $$xB$$ を取得しました。これにより、攻撃者は $$xA$$ と $$x_B$$ を使用してウォレットに対応する真の秘密鍵 $$x$$ を得ることができます。

上記の攻撃シナリオでは、ウォレットを攻撃するには、ウォレットを作成する際に攻撃を開始し、その後、そのウォレットを使用して複数回署名を行う必要があります。最終的にウォレットの秘密鍵を取得します。

脆弱性の修正

攻撃プロセス全体を通じて、すべての攻撃は攻撃準備段階から始まることがわかります。この段階で攻撃者 Party A は安全でない同型鍵 $$N_A$$ を構築し、その中には大量の小因子が含まれており、これが後続の攻撃の達成を促進しました。

脆弱性の修正はまさにこの点に対処しており、GG18/GG20 プロトコルにおいて、同型公開鍵 $$N_A$$ に小因子が現れないように追加のゼロ知識証明を追加し、根本的に攻撃を防止します。GG18/GG20 プロトコル全体として、パッチを適用した後、安全性の仮定に安全性の問題は存在しないため、プロトコルは依然として安全です。

脆弱性を修正するには、2 つのゼロ知識証明を追加する必要があります：

• 最初のゼロ知識証明は Paillier の Blum モジュラス証明であり、同型公開鍵 $$N_A$$ に最大 2 つの素因子しか存在せず、各素因子が特定の特性を満たすことを保証します。
• 2 番目のゼロ知識証明は小因子が存在しないことを保証し、同型公開鍵 $$N_A$$ に小さな素因子が存在しないことを確認します。

これらの 2 つのゼロ知識証明の実装は、CMP20 および CGGMP21（6.3 節および C.5 節）を参照できます。この証明は、Paillier 公開鍵 $$N$$ に小さな因子が存在しないことを保証します。

Safeheron はオープンソースアルゴリズム内のこの脆弱性を修正しており、具体的な修正方法は次のとおりです：

https://github.com/Safeheron/multi-party-ecdsa-cpp/pull/7/commits/ee78a86b53f341196623bd65a5ae1ee20bcc2853

https://github.com/Safeheron/multi-party-ecdsa-cpp/pull/10/commits/fbc3474f9b05b1a9e6cfd58647e6ebfc4d4fcbca

攻撃の検出

MPC プロトコルの安全性のアップグレードを完了した後、安全のために、過去のデータを検証してこの脆弱性に対する攻撃を受けたかどうかを確認できます。この脆弱性の利用は、安全でない Paillier 鍵の構築に依存しているため、過去にこのような攻撃を受けた場合、攻撃者の Paillier 公開鍵 $$N$$ には必ず小因子が存在します。したがって、MPC 参加者の Paillier 公開鍵 $$N$$ に小因子が存在するかどうかを分析することで、攻撃が存在したかどうかを検出できます。

具体的な検出方法は、成熟した大整数分解アルゴリズムツールを利用して、Paillier モジュラス $$N$$ に小因子が存在するかどうかを確認することです。小因子が存在する場合、攻撃の可能性があるため、資産をできるだけ早く移動し、新しい MPC ウォレットを作成することをお勧めします。

Safeheron は大整数分解ツール（https://github.com/Safeheron/integer-factorization）を提供しており、迅速にバッチ検出を行うことができます。大整数分解に関連するアルゴリズムの原理については、大整数分解アルゴリズムと実践（https://mp.weixin.qq.com/s/5FcA0qGXDKFeb_nMatFeWQ）を参照してください。

まとめ

この脆弱性の原理と攻撃方法を整理すると、この脆弱性の利用のハードルは比較的高いことがわかりますが、安全業界に身を置く私たちは、未知と挑戦に満ちた黒い森に直面しているため、常に安全に対して畏敬の念を持つ必要があります。

Fireblocks チームの責任ある安全な開示は「安全は決して孤軍奮闘ではない」ことを示しています。Safeheron もまた、オープンソースの透明性と技術重視を貫いており、今回の安全な開示に参加できたことを光栄に思います。Safeheron は今後、安全なパートナーである SlowMist と連携し、業界内の他の企業がこの脆弱性を修正できるよう支援し、ユーザーの資産の安全を確保します。

業界の安全を実現するには、すべての企業、すべてのセキュリティ専門家、すべてのユーザーの関心と努力が必要です。業界と共に励まし合っていきたいと思います。

参考文献
[1] Fireblocks: Practical Key-Extraction Attacks in Leading MPC Wallets (https://github.com/fireblocks-labs/mpc-ecdsa-attacks-23/blob/main/WhitePaper.pdf)
[2] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup (https://eprint.iacr.org/2019/114.pdf)
[3] GG20: One Round Threshold ECDSA with Identifiable Abort (https://eprint.iacr.org/2020/540.pdf)
[4] CGGMP21: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts (https://eprint.iacr.org/2021/060.pdf)