GG18/GG20 协议安全漏洞分析

2023-08-14

By Max

1 背景

近期，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 中的相关零知识证明，因此不受该漏洞影响。

2 漏洞影响范围

本文重点关注漏洞针对 GG18 和 GG20 的影响。针对 GG18/GG20 协议，攻击方通过构造特殊的 Paillier 密钥，从而在 MPC 签名阶段完成攻击，通过有限次的签名，攻击方可以解析出其它各参与方的私钥分片。

此次漏洞的影响范围比较广泛，由于影响到了 MPC 协议的安全假设，因此几乎所有主流的开源 GG18/GG20 协议实现都受到该漏洞的影响。

3 漏洞原理

如何攻击 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 子协议，基于中国剩余定理计算出对方私钥分片。

4 漏洞攻击方法

本节我们详细介绍攻击的细节。在通用的 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 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 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 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$ 论文，已知 $u_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$ （对应前文的 $u_B$ ），采用上述攻击方法，需要 16 次签名，攻击方就可以解析出被攻击方的私钥分片。
老版论文中 $MtA$ 协议使用的 $\beta_B < N_A$ （对应前文的 $u_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 协议时应基于修正版实现。

5 真实场景攻击示例

上述章节描述了该漏洞的原理和算法层面的攻击方式，那么针对真实的基于 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$ 。

在上述攻击场景中，如果要攻击该钱包必须在创建钱包时就已经启动了攻击，并且通过使用该钱包签名多次完成攻击，最终获得该钱包的私钥。

6 漏洞修复

通观整个攻击过程，我们发现所有的攻击都起源于攻击准备阶段，在该阶段攻击方 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 已经修复了开源算法中的该漏洞，具体修复方式可参考：

Import no small factor proof into GG18/GG20 by sword03 · Pull Request #7 · Safeheron/multi-party-ecdsa-cppGitHub

nsf proof and paillier blum modulus proof by sword03 · Pull Request #10 · Safeheron/multi-party-ecdsa-cppGitHub

7 检测攻击

在完成 MPC 协议安全升级之后，为了安全起见，可以检测历史数据进行验证是否曾经受到针对该漏洞的攻击。由于该漏洞的利用依赖于构造不安全的 Paillier 密钥，如果曾经受到过此类攻击，在攻击方的 Paillier 公钥 $N$ 中一定存在小因子，因此我们可以通过分析 MPC 参与方的 Paillier 公钥 $N$ 中是否存在小因子来检测是否存在过攻击。