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

2024-02-21 10:05

Safeheron

2024-02-21 10:05

来源链接

订阅此专栏

收藏此文章

背景

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

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

Trail of Bits 在 2024 年 1 月 3 日通过电子邮件向 Safeheron 披露了一个安全漏洞。Safeheron 经过分析研究，于 2024 年 1 月 4 日修补了该漏洞，同时公开了修复补丁（详见本文的「漏洞修复」部分）。在获得 Trail of Bits 的许可后，Safeheron 也立即通知了安全合作伙伴和业内其他厂商关于此漏洞的信息。

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 协议会正常结束，但是最终生成的分片将永远无法重建私钥，或者签名，这种情况会直接造成资损。补充一下，我们注意到有些开源算法库缺乏验证，会导致这种严重的后果。

注意：有一种特殊的情况，如果是（比如分片模式是 $\{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

https://en.wikipedia.org/wiki/Secret_sharing#Efficient_secret_sharing

[2] Verifiable secret sharing

https://en.wikipedia.org/wiki/Verifiable_secret_sharing

[3] How to share a secret

https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf

[4] A Practical Scheme for Non-interactive Verifiable Secret Sharing

https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/feldmanVSS.pdf

[5] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing

https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf

[6] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup

https://eprint.iacr.org/2019/114.pdf

[7] GG20: One Round Threshold ECDSA with Identifiable Abort

https://eprint.iacr.org/2020/540.pdf

[8] CMP: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts

https://eprint.iacr.org/2021/060.pdf

[9] DMZ21: Promise Sigma-protocol: How to Construct Efficient Threshold ECDSA from Encryptions Based on Class Groups

https://eprint.iacr.org/2022/297.pdf

[10] FROST: Flexible Round-Optimized Schnorr Threshold Signatures

https://eprint.iacr.org/2020/852.pdf

[11] Breaking the shared key in threshold signature schemes

https://blog.trailofbits.com/2024/02/20/breaking-the-shared-key-in-threshold-signature-schemes/

Safeheron 将持续输出更多安全分析，希望伴随传统行业以及区块链行业用户前行，提供有价值的参考。

Keep Your Funds

Safe From Here On

Twitter｜@Safeheron

LinkedIn｜Safeheron

公众号｜安全鹭

来源链接

【免责声明】市场有风险，投资需谨慎。本文不构成投资建议，用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。

数据请求中

数据请求中

在 App 打开

推荐专栏