DKG 协议的门限提升漏洞分析

背景

Trail of Bits 近期披露了 MPC 门限签名协议的一个漏洞，可用于攻击 MPC 门限签名方案中的 DKG（Distributed Key Generation）协议。利用该漏洞可恶意提升私钥分片的门限，导致意料之外的分片结果；在极端情况下，甚至可能导致私钥无法重建。

举例来说，假设执行 DKG 协议的预期是 $\{2,3\}$ ，一共生成3个分片，任意两方可以执行 MPC 签名或者私钥重建。那么利用该漏洞，可能生成 $\{3, 3\}$ 的分片，一共生成三个分片，任意两方无法执行 MPC 签名或者私钥重建，需要三方都参与，才能执行 MPC 签名或者私钥重建。极端情况下，如果 DKG 协议实现中缺少完整的检测，甚至会生成 $\{3, 4\}$ 的分片，因为实际上仅保存三个分片，所以永远无法执行 MPC 签名或者私钥重建，这将直接导致资产损失。

Safeheron 的 SaaS 产品不受此漏洞影响。

DKG（Distributed Key Generation）协议

在安全多方计算的场景中，不存在可信的第三方 Dealer，秘密是由多方共同生成的。任何时候，任何地点，都不曾有完整的秘密出现。为了实现这个目标，1991 年提出了[5]一种分布式的私钥生成协议（DKG，Distributed Key Generation），该协议基于 Shamir 的门限分享方案[1] [2] [3] [4] 进行了扩展。协议实现了如下目的：

参与者 $P_1, P_2, \dots , P_n$ 共同生成了 $\{t, n\}$ 门限模式下的一组私钥分片，但是任意少于 $t$ 方不知道真正的私钥的任何信息。

典型的 MPC 多签协议，如 GG18[6]、GG20[7]、基于门限方案的 CMP[8]、Frost[10]、DMZ21[9] 等，都定义了分布式的私钥生成子协议，即 DKG（Distributed Key Generation）协议，其分片生成的原理都类似，我们介绍一下核心思想。

给定椭圆曲线群 $\mathbb{G} = (g, q)$ ，每个参与者( $P_i$ )都执行如下算法：

1. $P_i$ 随机生成一个密钥 $u_i \in Z_q$
2. $P_i$ 随机选择一个度数为 $t-1$ 的多项式；
   • 选择 $t-1$ 个随机数 $a_1 \in Z_q$ ；
   • 构造多项式 $f_i(\nu) = u_i + a_1\nu + … + a_{t-1}\nu^{t-1} \pmod q$ ，注意 $u_i$ 是秘密值。
   • 计算 VSSS（Verifiable Secret Sharing Scheme）的 Commitment： $c_i = (g^{u_i}, g^{a_1}, \dots, g^{a^{t-1}})$
3. $P_i$  将分片 $f_i(1), f_i(2), … , f_i(n)$  对应分发给参与者 $P_1, P_2, \dots , P_n$ ，并广播发送 $c_i$ 。

4. $P_i$ 在收到其他人发送的 $f_j(i)$ 后

   • 验证分片的合法性。如果以下等式成立，表示分片合法，否则表示分片不合法：

   $g^{f_j(i)} = \prod_k {c_{i, k}{i^k}}$

   • 计算自己的分片:

   $x_i = \sum_{j \ne i} f_j(i) \pmod q$

以 $\{2, 3\}$ 为例， $P_1, P_2, P_3$ 执行 DKG 协议，生成了各自的分片 $x_1, x_2, x_3$ ，如下图所示：

存在私钥 $x$ （此即为真正的私钥)，能以门限 2 恢复出来，不仅满足
$x \equiv x_1 \cdot \lambda_1 + x_2 \cdot \lambda_2 + x_3 \cdot \lambda_3 \pmod q$
还满足下列等式，即任意两个私钥分片均可重建私钥。
$x \equiv x_1 \cdot \lambda_1′ + x_2 \cdot \lambda_2′ \pmod q$
$x \equiv x_1 \cdot \lambda_1” + x_3 \cdot \lambda_3” \pmod q$
$x \equiv x_2 \cdot \lambda_2”’+ x_3 \cdot \lambda_3”’ \pmod q$
其中各个 $\lambda$ 指拉格朗日插值系数，注意它是公开的，因为它可以从公开的 Index 数据计算出来，如下所示：
$\lambda_i = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i – j}} \pmod q$ ， $i \in SubSet$ , $SubSet = \{1,2,3\}$
$\lambda_i’ = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i – j}} \pmod q$ ， $i \in SubSet$ , $SubSet = \{1,2\}$
$\lambda_i” = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i – j}} \pmod q$ ， $i \in SubSet$ , $SubSet = \{1,3\}$
$\lambda_i”’ = \Pi_{j \in SubSet, j \ne i}{\frac{i}{i – j}} \pmod q$ ， $i \in SubSet$ , $SubSet = \{2,3\}$

注意，对于典型的 MPC 多签协议，MPC 多签门限和私钥重建的门限是一样的，这里为了叙述简便，仅提到了私钥重建。一般来说，只要能重建私钥，就可以完成 MPC 多签；如果不能重建私钥，就不能完成 MPC 多签。最后再强调一下，MPC 多签时并不会重建私钥，也不会泄漏彼此私钥分片的任何信息。

漏洞攻击原理

在 DKG 协议的具体实现中，如果在验证 VSSS（Verifiable Secret Sharing Scheme） 的 Commitment 时，只验证了分片的正确性，但是没有验证随机多项式的度数，那么就可以采用如下方式攻击：

单个恶意参与者( $P_i$ )，为了修改最终分片的门限，从 $t$ 修改为 $t’$ ， $t’ > t$ , 执行如下恶意协议：

1. $P_i$ 随机生成一个密钥 $u_i \in Z_q$ ；
2. $P_i$ 随机选择一个度数为 $t’-1$ 的多项式，注意此处的 $t’$ 有别于期望中的 $t$ ， $t’ > t$ ；
   • 选择 $t’-1$ 个随机数 $a_1 \in Z_q$ ；
   • 构造多项式 $f_i(\nu) = u_i + a_1\nu + … + a_{t-1}\nu^{t’-1}$ ， $u_i$ 是秘密值。
   • 计算VSSS（Verifiable Secret Sharing Scheme）的 Commitment： $c_i = (g^{u_i}, g^{a_1}, \dots, g^{a^{t’-1}})$
3. $P_i$  将分片 $f_i(1), f_i(2), … , f_i(n)$  分发给参与者 $P_1, P_2, \dots , P_n$ ，并广播发送 $c_i$ 给所有人。

4. $P_i$ 在收到其他人发送的 $f_j(i)$ 后

   • 验证分片的合法性，如果以下等式成立，表示分片合法，否则表示分片不合法：

   $g^{f_j(i)} = \prod_k {c_{i, k}{i^k}}$

   • 计算自己的分片:

   $x_i = \sum_{j \ne i} f_j(i) \pmod q$

如此，当 DKG 协议结束以后，最终的分片 $x_1, x_2, \dots, x_3$ 的门限就变成了恶意参与方所修改的门限 $t’$ ，实际门限要比预期门限 $t$ 更大。

以 $\{2, 3\}$ 为例， $P_1$ 为恶意方， $P_1, P_2, P_3$ 执行 DKG 协议，生成了各自的分片 $x_1, x_2, x_3$ ，如下图所示：

注意， $x_1, x_2, x_3$ 的门限被恶意修改为 3，而不是预期中的 2。也就是说， $x$ 无法以门限 2 来重建，即以下等式不成立。攻击成功。
$x \equiv x_1 \cdot \lambda_1′ + x_2 \cdot \lambda_2′ \pmod q$
$x \equiv x_1 \cdot \lambda_1” + x_3 \cdot \lambda_3” \pmod q$
$x \equiv x_2 \cdot \lambda_2”’ + x_3 \cdot \lambda_3”’ \pmod q$

漏洞攻击影响

采用如上攻击方式，单个恶意攻击方有可能提升最终分片的门限，典型的 MPC 多签协议，如 GG18[6]，GG20[7]，基于门限方案的 CMP[8]，Frost[10], DMZ21[9] 等中的 DKG 协议都会受到影响。具体的说，如果 DKG 协议预期的门限是 $(t ,n)$ ，即任意 $t$ 方可以恢复私钥/签名，那么单个恶意攻击方有可能修改门限为 $(T, n)$ 。

具体影响分析如下：
情况 1： $n \ge T \gt t$ 。单纯的提升了恢复私钥/签名的门限。比如预计生成三个分片   $x_1, x_2, x_3$ ，预期门限为 2，被恶意修改成 3，为了恢复私钥、MPC 签名，必须要三个分片都参与，才能成功实施。

情况 2： $T \gt n$ 。需要分两种情况来看：

• 如果 DKG 协议中有比较完整的验证工作，比如私钥可恢复性验证（参考 Safeheron 实现），那么仅仅会导致 DKG 协议无法成功结束，并不会带来进一步的问题。
• 如果 DKG 协议中没有额外验证，那么 DKG 协议会正常结束，但是最终生成的分片将永远无法恢复私钥，或者签名，这种情况会直接造成资损。补充一下，我们注意到有些开源算法库缺乏验证，会导致这种严重的后果。

注意：有一种特殊的情况，如果是 $n == t$ （比如分片模式是 $\{3,3\}$ ， $\{5,5\}$ ，   $\{10,10\}$ 等 ） ，且有必要的私钥可恢复性验证，那么该场景不受该漏洞的影响。

漏洞修复

为了修复漏洞，需要检查 Feldman VSSS 算法中的 Commitment 的长度，确保其和门限保持一致。具体的：
$P_i$ 在收到其他人发送的 $f_j(i)$ 后，

• 验证分片的合法性：

  • 验证等式。如果以下等式不成立，表示分片不合法。

  $g^{f_j(i)} = \prod_k {c_{i, k}^{i^k}}$

• 验证等式。如果以下等式不成立，表示分片不合法。

  $len(c_i) == t$

• 计算自己的分片:

  $x_i = \sum_{j \ne i} f_j(i) \pmod q$

本质上是通过约束随机多项式的度数来锁定分片的门限。

具体修复参考：

• https://github.com/Safeheron/safeheron-crypto-suites-cpp/commit/5531ce457a6de958cd0a5281d0db233188feb6d6
• https://github.com/Safeheron/multi-party-sig-cpp/commit/71da5cd3b7bb91f1abcfe5dc251d788bdacdef89

结语

理清此漏洞攻击原理与方法后，我们不难看出，这是一个协议实现层次的漏洞，利用此漏洞造成的危害随着情况的不同而有所差异，在极端情况下能造成极其严重的后果。Safeheron 的 SaaS 产品采用了 $\{3, 3\}$ 的门限方案与必要的可恢复性验证（基于零知识证明），因此不受该漏洞的影响。

实现值得信赖的安全需要持之以恒的严谨打磨，「不积跬步无以至千里」，保持敬畏，脚踏实地，让安全真正有效服务于行业。

Trail of Bits 团队的负责任安全披露展现了安全行业的开放与协作，Safeheron 也在不断与更多安全伙伴积极对话，能参与到此漏洞的修复与披露中我们也倍感欣慰。打造安全的行业环境，与厂商、安全从业人员、用户的对话必不可少，多方的共同关注与努力方能实现安全赋能行业。

参考文献

[1] Secret sharing
[2] Verifiable secret sharing
[3] How to share a secret
[4] A Practical Scheme for Non-interactive Verifiable Secret Sharing
[5] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing
[6] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup
[7] GG20: One Round Threshold ECDSA with Identifiable Abort
[8] CMP: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
[9] DMZ21: Promise Sigma-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups
[10] FROST: Flexible Round-Optimized Schnorr Threshold Signatures
[11] Breaking the shared key in threshold signature schemes