安全与技术

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

By Max - 2024-02-21

背景

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$ ,如下图所示:
2_3 scheme executes DKG protocol CN
存在私钥 $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$ ,如下图所示:
Attack towards 2_3 scheme executing DKG protocol CN

注意, $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$

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

具体修复参考:

结语

理清此漏洞攻击原理与方法后,我们不难看出,这是一个协议实现层次的漏洞,利用此漏洞造成的危害随着情况的不同而有所差异,在极端情况下能造成极其严重的后果。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