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 bit
• $$\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論文有兩個實現版本，修正版和舊版，針對不同版本的攻擊效果有所區別。

-修正版論文中 $$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 Wallet 的參與方為 2 方 Party A 和 Party B，簽名的門檻為 2/2，其中 Party A 對應的私鑰分片由用戶持有，通過錢包提供方提供的手機 App 管理和使用；Party B 對應的私鑰分片由錢包提供方持有，並且在雲端存儲和使用。

如果要完成攻擊，攻擊者必須具備以下能力：

（1）掌握錢包提供方創建錢包和發起交易的實現邏輯和機制
（2）能夠模擬錢包提供方 App 使用 MPC 協議完成創建錢包以及簽名交易

那麼攻擊者便可以發起攻擊：

（1）模擬 App 創建錢包，在創建錢包時（對應 KeyGen 子協議），構造本地 Party A MPC 協議中不安全的同態密鑰，然後使用該同態密鑰完成錢包創建，同時獲取本地 Party A 私鑰分片 $$xA$$ （2）模擬 App 使用該錢包正常發起交易簽名 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 協議來說，打完該補丁以後，安全假設就不存在安全問題了，因此協議仍然是安全的。

修復漏洞需要添加兩個零知識證明：

-第一個零知識證明是 Paillier 的 Blum 模數證明，它保證了同態公鑰 $$NA$$ 最多只有兩個素因子，且每個素因子滿足特定特性。 -第二個零知識證明是無小因子證明，保證了同態公鑰 $$NA$$ 中沒有小的素因子。

這兩個零知識證明實現可以參考 CMP20 和 CGGMP21（6.3 節 和 C.5 節)，該證明可保證Paillier 公鑰 $$N$$ 不存在小於 $$2\^{256}$$ 的因子。

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)