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 共同创建和使用,每一方分别管理各自的私钥分片 $$x_A$$ 、$$x_B$$ 和 $$x_C$$。利用该漏洞,Party A 可以攻击 Party B 和 Party C 以获取对方的私钥分片。本节我们以「Party A 试图攻击 Party B」为例,介绍如何提取 Party B 的私钥分片 $$x_B$$。(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 构造同态密钥的过程如下:
- 随机选择素数 $$(p_1, p_2, ..., p_{16}, q)$$,其中 $$p_i$$ 是互不相同的小素数,而 $$q$$ 是大素数
- 计算
- $$ N_A = \Pi_i{p_i} * q$$,$$N_A$$ 的长度为 2048 bit
- $$\lambda_A = \Pi_i(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(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B$$
- $$ MtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B$$
正常的计算过程如下:
- 随机选择 $$k_A \in Zq$$
- 计算 $$Enc(k_A)$$
- 执行 $$MtA$$ 协议
- $$ MtA(k_A, \gamma_B) : \alpha_A + \beta_B \leftarrow k_A * \gamma_B$$
- $$ MtA(k_A, x_B) : \mu_A + \nu_B \leftarrow k_A * x_B$$
- 生成关于随机数 $$k_A$$ 的密文 $$Enc(k_A)$$ 的零知识证明。参考 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 子协议中,采用如下方式构造 $$k_A$$。
$$ k_A = N_A / p_i $$
注意,该特殊构造的 $$k_A \gg q^3$$,正常情况下已经无法通过预期零知识证明。其中 $$q$$ 为椭圆曲线的阶。
构造零知识证明
GG18 协议要求攻击者在 $$MtA$$ 运行阶段提供有效的零知识证明,参考 GG18 (https://eprint.iacr.org/2019/114.pdf) A.1 节 Range Proof。该零知识证明能证明:
- Witness: $k_A' = 0 \ne k_A$,其它随机数
- Statement: $Enc_{N_A}(k_A)$ 对 $$k_A'$$ 的加密密文,且满足 $$k_A \in (-q^3, q^3) $$
注意,以上是一个非法的 Statement,因为:
-$$Enc_{N_A}(k_A)$$ 不是 $$k_A'=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 {p_i} = 0$$
由于 $$c = (1+N_A)^k_A * \rho^N_A \mod (N_A^2)$$, $$k_A = N_A/p_i$$
$$\begin{align*}
c^e &= ((1+N_A)^k_A * \rho^N_A)^e &\mod (N_A^2) \\
&= (1+N_A)^{ek_A} * \rho^{eN_A} &\mod (N_A^2) \\
&= (1+N_A)^{bp_i * N_A/p_i} * \rho^{eN_A} &\mod (N_A^2) \\
&= \rho^{e_AN} &\mod (N_A^2) \\
&= Enc_{N_A}(0)^e &\mod (N_A^2) \\
\end{align*}$$
这里将 $$c$$ 「变换」成了 $$k_A'=0$$ 的密文,从而成功构造了零知识证明。
注意,这里可以通过在构造过程中暴力迭代 $$\gamma$$ ,不断加 1,并更新 $$w$$,从而满足$$e \pmod {p_i} = 0$$ 。由于模数 $p_i$ 为小素数,因此完全可以暴力迭代成功。
计算 Party B 私钥分片的模 $$p_i$$ 剩余
攻击方与被攻击者完成 Sign 子协议,并额外记录下 $$MtA$$ 协议中的 $$\mu_A$$ 值。
$$ \mu_A = k_A * x_B + \nu_B \pmod {N_A}$$
考虑最新版的 GG18 论文,已知 $$\nu_B \le q^5$$,
$$ \mu_A = Dec_{N_A}(Enc_{N_A}(k_A * x_B + v_B))$$
$$\begin{align*}
\mu_A - (\mu_A \mod (N_A/p_i)) =& Dec_{N_A}(Enc_{N_A}(k_A * x_B + \nu_B)) - (Dec_{N_A}(Enc_{N_A}(k_A * x_B + \nu_B)) \mod (N_A/p_i))\\
=& (x_B \mod p_i) * (N_A/p_i) + \nu_B - \nu_B \\
=& (x_B \mod p_i) * (N_A/p_i)
\end{align*}$$
可知:
$$x_B \pmod {p_i} = (\mu_A - (\mu_A \mod (N_A/p_i)))/(N_A/p_i) $$
记 $$a_i = (\mu_A - (\mu_A \mod (N_A/p_i)))/(N_A/p_i) $$
注意到等式右边全都是攻击方已知的参数,因此攻击方可以计算出 $$a_i$$
从而得到:$$x_B = a_i \pmod {p_i}$$
4.3 收尾阶段:计算出被攻击方的私钥分片
在运行 16 次成功的 MPC Sign 子协议以后,得到
$$ x_B = a_1 \pmod {p_1}$$
$$ x_B = a_2 \pmod {p_2}$$
$$ ... $$
$$ x_B = a_{16} \pmod {p_{16}}$$
由于 $$p_1 * p_2 *... * p_{16} > q$$,根据中国剩余定理,攻击方 Party A 可以计算出 Party B 的私钥分片 $$x_B$$。攻击成功。
4.4 攻击效果
GG18论文有两个实现版本,修正版和老版,针对不同版本的攻击效果有所区别。
-修正版论文中 $$MtA$$ 协议使用的 $$\beta_B < q^5$$(对应前文的 $$\nu_B$$),采用上述攻击方法,需要 16 次签名,攻击方就可以解析出被攻击方的私钥分片。
-老版论文中 $$MtA$$ 协议使用的 $$\beta_B < N_A$$(对应前文的 $$\nu_B$$),需要采用上述攻击方法的变型来实施攻击,此处不做额外说明。因为需要大量的猜测运行,需要进行大量的签名,至少需要进行 10^6 量级的签名尝试,攻击方才可能解析出被攻击方的私钥分片。更准确的说,为了以概率 $$\tau^l$$成功提取对方私钥分片所需签名次数是: $$\sum_{i=1}^nf_\tau(p_i)$$ 次。
其中,$$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 私钥分片 $$x_A$$
(2)模拟 App 使用该钱包正常发起交易签名 16 次(对应 Sign 子协议),并且每次构造 MPC 协议中恶意的 $$k_A$$ 和恶意的零知识证明,完成 16 次签名并收集每次签名中的 $$\mu$$
完成上述操作后,攻击者就可以获取所创建钱包对应的云端 Party B 的私钥分片 $$x_B$$。因为签名门限为 2/2,攻击者从本地获取了私钥分片 $$x_A$$,同时又攻击协议获得了云端私钥分片 $$x_B$$,至此攻击者可以通过 $$x_A$$ 和 $$x_B$$ 得到钱包对应的真实私钥 $$x$$。
在上述攻击场景中,如果要攻击该钱包必须在创建钱包时就已经启动了攻击,并且通过使用该钱包签名多次完成攻击,最终获得该钱包的私钥。
漏洞修复
通观整个攻击过程,我们发现所有的攻击都起源于攻击准备阶段,在该阶段攻击方 Party A 构造了不安全的同态密钥 $$N_A$$,其中包含了大量的小因子,这些都促成了后续的攻击达成 。
漏洞修复也正是针对这一点, 在 GG18/GG20 协议中,添加额外的零知识证明,避免同态公钥 $$N_A$$ 中小因子的出现,从根源上阻止了攻击。从整个 GG18/GG20 协议来说,打完该补丁以后,安全假设就不存在安全问题了,因此协议仍然是安全的。
修复漏洞需要添加两个零知识证明:
-第一个零知识证明是 Paillier 的 Blum 模数证明,它保证了同态公钥 $$N_A$$ 最多只有两个素因子,且每个素因子满足特定特性。
-第二个零知识证明是无小因子证明,保证了同态公钥 $$N_A$$ 中没有小的素因子。
这两个零知识证明实现可以参考 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)