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

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

参与者    共同生成了  门限模式下的一组私钥分片，但是任意少于  方不知道真正的私钥的任何信息。

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

给定椭圆曲线群   ，每个参与者(  )都执行如下算法：

1.    随机生成一个密钥  

2.    随机选择一个度数为    的多项式；

• 选择    个随机数   ；

• 构造多项式    ，注意   是秘密值。

•  计算 VSSS（Verifiable Secret Sharing Scheme）的 Commitment：     

3.     将分片  对应分发给参与者   ，并广播发送   。

4.   在收到其他人发送的  后 

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

•  计算自己的分片:

以  为例，  执行 DKG 协议，生成了各自的分片  ，如下图所示：

存在私钥  （此即为真正的私钥），能以门限 2 恢复出来，不仅满足

还满足下列等式，即任意两个私钥分片均可重建私钥。

其中各个  指拉格朗日插值系数，注意它是公开的，因为它可以从公开的 Index 数据计算出来，如下所示：

  ，  ,   

  ，  ,   

  ，  ,   

  ，  ,   

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

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

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

1.     随机生成一个密钥   ； 

2.     随机选择一个度数为    的多项式，注意此处的  有别于期望中的  ，  ； 

• 选择    个随机数   ；

• 构造多项式   ，  是秘密值。

• 计算VSSS（Verifiable Secret Sharing Scheme）的 Commitment：  

3.     将分片     分发给参与者   ，并广播发送   给所有人。

4.   在收到其他人发送的  后 

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

• 计算自己的分片:

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

以  为例，  为恶意方，  执行 DKG 协议，生成了各自的分片   ，如下图所示：

注意：  的门限被恶意修改为 3，而不是预期中的 2。也就是说，  无法以门限 2 来重建，即以下等式不成立。攻击成功。

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

情况 1：  。单纯地提升了重建私钥/签名的门限。比如预计生成三个分片    ，预期门限为 2，被恶意修改成 3，为了重建私钥、MPC 签名，必须要三个分片都参与，才能成功实施。

情况 2：  。需要分两种情况来看：

• 如果 DKG 协议中有比较完整的验证工作，比如私钥可恢复性验证（参考 Safeheron 实现，如下图所示），那么仅仅会导致 DKG 协议无法成功结束，并不会带来进一步的问题。

为了修复漏洞，需要检查 Feldman VSSS 算法中的 Commitment 的长度，确保其和门限保持一致。具体的：

   在收到其他人发送的    后，

• 验证分片的合法性： 

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

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

• 计算自己的分片:

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

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

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

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