Fireblocks 团队披露了 GG18、GG20 、Lindel 17 MPC 协议中的 0-day 漏洞 CVE-2023-33241，允许某个恶意参与者造特殊的 Paillier 密钥，通过多次签名，提取其它参与者的私钥分片，进而最终合成公共私钥。

对于 MPC 钱包，私钥分散在多个参与方间，攻击者需要攻破所有的参与方才能合成公共私钥，但是该漏洞允许攻击者只需要控制一个参与方便可获取到公共私钥，大大降低了攻击难度。

攻击原理

MtA 协议的作用是将乘法转为加法，在签名时用到，协议描述如下：

输入：Alice 输入保密数据 $k_A$，Bob 输入保密数据 $x_B$
输出：Alice 获得保密数据 $\alpha$，Bob 获得保密数据 $\beta$
功能：Alice 和 Bob 互相不知道对方的保密数据，但是保密数据满足关系 $k_Ax_B = \alpha + \beta$

过程如下：

Alice：自己的 Paillier 公钥为 $N_A$，选择随机数 $k_A \in Z_{n}$，计算密文 $c_1 = Enc_{N_A}(k_a)$，将 $c_1$ 和范围证明 $RangeProof \left\{k_A < q^3\right\}$ 发送给 Bob
其中，$q$ 为椭圆曲线的阶，位数一般为 256，而 $N_A$ 的位数一般为 2048，所以 $q^3 < n$，所以 $k_A$ 的取值空间更小
Bob：校验范围证明。自己的秘密为 $x_B$，选择随机数 $\beta' \in Z_n$，同态计算密文 $c_2=(c_1 \bigotimes x_b) \bigoplus Enc_{N_A}(\beta')=Enc_{N_A}(k_ax_b + \beta')$，获得加性份额 $\beta = -\beta' \space mod \space n$，向 Alice 发送 $c_2$，$B=g^{x_b}$ 和范围证明 $RangeProof \left\{x_B < q^3, \beta' < q^7\right\}$
Alice：校验范围证明。使用自己的 Paillier 私钥解密 $c_2$ 获得 $\alpha = k_Ax_B + \beta'$
结果：Alice 和 Bob 互相不知道对方的保密数据，但是保密数据满足关系 $\alpha + \beta = (k_Ax_B + \beta') + (-\beta')=k_Ax_B$

实施攻击有两个关键点：

攻击关键点 1：MtA 协议中，Alice 使用更大的 $k_A$，让 $\beta'$ 不再起到 mask 作用，从而导致 Bob 的秘密 $x_B$ 被泄露。
攻击关键点 2：Alice 伪造 $k_A$ 的 range proof。MtA 协议中，Alice 需要提供 $k_A < q^3$ 的 range proof，但是 $k_A$ 变大后无法提供正常的 range proof，需要伪造。

下面介绍第一个攻击关键点原理。

$k_A$ 取正常值时，$\beta'$ 可起到隐藏 $x_B$ 的作用：

$$ \begin{align} x_B &= 0x1337 \\ \beta'(mask) &= 0x4242424242 \\ k_A &= 0x6789 \\ x_Bk_A &= 0x7c5696f \\ x_Bk_A + \beta'&=0x424a0xabb1 \end{align} $$

而 $k_A$ 取值较大时，$\beta'$ 将失去 mask 的作用，导致 $x_B$ 泄露（前提是 $\beta'$ 不能太大，否则继续起到 mask 作用）：

$$ \begin{align} x_B &= 0x1337 \\ \beta'(mask) &= 0x4242424242 \\ k_A &= 0x100000000000 \\ x_Bk_A &= 0x133700000000000 \\ x_Bk_A + \beta'&=0x133704242424242 \end{align} $$

可以看到，$x_Bk_A + \beta'$ 计算结果的高位泄露了 $x_B$

但是对于 MtA 协议，求的是

$$ \begin{align} N &= 0x1000000000000 = pq\\ (x_Bk_A + \beta') \space \% \space N &= 0x704242424242 \\ \end{align} $$

只有 $x_B$ 的最低位被泄露了，相当于我们只能得到 $x_B \space \% \space p$ 的值，其中 $p$ 是 $N$ 的一个素因子。假设 $N=p_1 \cdot p_2 \cdot ... \cdot p_{16} \cdot q$，其中 $p_i$ 是一个 16-bit 的小素数，每次签名时令 $k_A = N / p_i$，签名 16 次就可以得到 16 个 $x_B \space \% \space p_i$。再利用中国剩余定理，就可以得到 $x_B \space \% \space (p_1 \cdot p_2 \cdot ... \cdot p_{16})$，从而得到完整的 256-bit 的 $x_B$

但是 Alice 还需要证明 $k_A < q^3$，而 $k_A$ 太大时并不满足，所以还需要伪造 range proof

攻击细节

以 (2, n) 两方门限为例，假设参与者是 Alice 和 Bob，其中 Alice 是恶意攻击者。

DKG 阶段，Alice 构造一个非法的 Paillier 公钥 $N=p_1p_2...p_{16} \cdot z$，其中 $p_1,p_2,...p_{16}$ 是随机选择的 16 个比特长的小素数，最后再随机选择一个大素数 $z$，使得 $N$ 长度为 2048 比特
Bob 的私钥分片（Addtive Share）为 $x_B$，长度为 256 比特。在每次 MPC 签名中，Alice 都可以获得 $x_B \space mod \space p_i = \frac{\alpha - (\alpha \space mod \space (N/p_i))}{N/p_i}$，进行 16 次签名后，就可以得到 16 个式子
$$ \begin{align} &x_B \space mod \space p_1 = \frac{\alpha - (\alpha \space mod \space (N/p_1))}{N/p_1}\\ &x_B \space mod \space p_2 = \frac{\alpha - (\alpha \space mod \space (N/p_2))}{N/p_2}\\ &...\\ &x_B \space mod \space p_{16} = \frac{\alpha - (\alpha \space mod \space (N/p_{16}))}{N/p_{16}} \end{align} $$

根据中国剩余定理可求解 $x_B \space mod \space (p_1p_2...p_{16})$，由于 $p_i$ 是 16 比特位，所以乘积 $p_1p_2...p_{16}$ 是 256 比特位，所以可以求出 256 比特位的 $x_B$。下面介绍式子 $x_B \space mod \space p_i = \frac{\alpha - (\alpha \space mod \space (N/p_i))}{N/p_i}$ 是如何来的。

正常情况下，MtA 结束后，Alice 得到 $\alpha=(k_Ax_B + \beta')\space mod \space N$。但攻击时，Alice 并不在 $Z_{q^3}$ 中随机产生 $k_A$，而是使用更大的值 $k_A=\frac{N}{p_i}$，这样 MtA 结束后，Alice 得到

$$ \alpha=(\frac{N}{p_i}x_B + \beta')\space mod \space N $$

因为 $\beta' < q^5$，$q$ 是 256 比特位，所以 $\beta'$ 最多为 $256 \times 5 = 1280$ 位，因为 $N$ 是 2048 位，$p_i$ 是 16 比特位，所以有

$$ \beta' < \frac{N}{p_i} $$

因为 $\frac{N}{p_i}$ 是 $N$ 的因子，利用同余性质 $a = b \space (mod \space cn) \rightarrow a = b \space (mod \space n)$，所以

$$ \begin{align} \alpha \space mod \space \frac{N}{p_i} &=(\frac{N}{p_i}x_B + \beta')\space mod \space \frac{N}{p_i} \\ & =0 + \beta' \space mod \space \frac{N}{p_i} \\ &=\beta' \space mod \space \frac{N}{p_i} \\ &=\beta' \end{align} $$

所以分子

$$ \begin{align} \alpha - (\alpha \space mod \space \frac{N}{p_i}) &= \alpha - \beta' \\ &=((x_B\frac{N}{p_i} + \beta')) \space mod \space N) - \beta' \\ &=(x_B\frac{N}{p_i}\space mod \space N) + (\beta' \space mod \space N) - \beta' \\ &=(x_B\frac{N}{p_i} \space mod \space N) + \beta' - \beta' \\ &=x_B \frac{N}{p_i} \space mod \space N \\ &=\frac{N}{p_i}(x_B \space mod \space p_i)\\ \end{align} $$

所以有 $x_B \space mod \space p_i = \frac{\alpha - (\alpha \space mod \space (N/p_i))}{N/p_i}$ 。上式中最后一步成立的原因是

$$ x_B=\frac{x_B}{p_i}p_i + (x_B \space mod \space p_i) $$

对上式两边乘以 $N/p_i$，有

$$ x_B\frac{N}{p_i}=\frac{x_B}{p_i}p_i\frac{N}{p_i} + (x_B \space mod \space p_i)\frac{N}{p_i} $$

两边取 mod $N$，有

$$ x_B\frac{N}{p_i} \space mod \space N = 0 + (x_B \space mod \space p_i)\frac{N}{p_i} \space mod \space N = (x_B \space mod \space p_i)\frac{N}{p_i} $$

伪造 range proof

range proof 过程如下：

Alice 构造 $s_1$ 和 $k_A$ 的密文 $c$ 等发送给 Bob

$$ \begin{align} &c=Enc(k_A)=\Gamma^{k_A}r^N \space mod \space N^2=(1+N)^{k_A}r^N \space mod \space N^2\\ &s_1=ek_A + \alpha = Hash(N, \Gamma, c, z, u,w)k_A + \alpha\\ \end{align} $$

Bob 验证如下式子是否成立：

$$ \begin{align} & s_1 \le q^3 \\ & uc^e = \Gamma^{s_1}s^N \space mod \space N^2\\ &h_1^{s_1}h_2^{s_2}z^{-e}=w \space mod \space \hat{N} \end{align} $$

如果都成立，则 Bob 认为 Alice 发给他的 Paillier 密文 $c$ 对应的明文 $k_A$ 满足 $k_A \in [-q^3, q^3]$

因为 $k_A=\frac{N}{p_i}$ 有 2032 个比特位，所以 Bob 会发现 $s_1 \le q^3$ 不成立，怎么办？如果 Alice 把 $s_1$ 中的 $k_A$ 替换为 0，那么 $s_1 \le q^3$ 就可以成立了。

但是这会导致第二个式子校验不通过，因为 $c$ 是 $k_A$ 的密文，并不是 0 的密文。Alice 的办法是通过修改产生的随机数的值来操作 $e$，直到 $e \space mod \space p_i=0$，这样就会有 $Enc(\frac{N}{p_i})^e=Enc(0)^e \space mod \space N^2$ 成立。因为 $p_i$ 只有 16 个比特位，所以暴力搜索即可找到符合条件的 $e$。令 $e=ap_i$，证明如下：

$$ \begin{align} Enc(\frac{N}{p_i})^e \space mod \space N^2 &= ((1+N)^{\frac{N}{p_i}}r^N \space mod \space N^2)^e \space mod \space N^2 \\ &= (1+N)^{\frac{N}{p_i}ap_i}r^{Ne} \space mod \space N^2\\ &=((1+N)^{Na} r^{Ne} \space mod \space N^2 \\ &=((1+NNa) \space mod \space N^2)(r^{N} \space mod \space N^2)^e \space mod \space N^2 \\ &=1 \times (r^{N} \space mod \space N^2)^e \space mod \space N^2 \\ &=((1 + N)^0r^N \space mod \space N^2)^e \space mod \space N^2\\ &=Enc(0)^e \space mod \space N^2 \end{align} $$

上式中用到了结论 $(1+N)^x \space mod \space N^2=(1+Nx) \space mod \space N^2$，参考：https://en.wikipedia.org/wiki/Paillier_cryptosystem#Background

修复

参与者公布 Paillier 公钥 $N_i$ 时，需证明 $N_i$ 确实是两个安全素数 $p_i, q_i$ 的乘积，且满足 Paillier 私钥要求，即 $p_iq_i$ 和 $(p_i-1)(q_i-1)$ 互素，可参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 4.3 节 Paillier-Blum Modulus ZK
证明 $N_i$ 没有小因子，即 $p_i,q_i$ 都是大素数，可参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 B.4 节 No Small Factor Proof