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

密码学 2个月前 admin
16 0 0


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


背景

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


举例来说,假设执行 DKG 协议的预期是  ,一共生成3个分片,任意两方可以执行 MPC 签名或者私钥重建。那么利用该漏洞,可能生成  的分片,一共生成三个分片,任意两方无法执行 MPC 签名或者私钥重建,需要三方都参与,才能执行 MPC 签名或者私钥重建。极端情况下,如果 DKG 协议实现中缺少完整的检测,甚至会生成  的分片,因为实际上仅保存三个分片,所以永远无法执行 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] 进行了扩展。协议实现了如下目的:

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


典型的 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 协议,生成了各自的分片  ,如下图所示:

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 协议,生成了各自的分片   ,如下图所示:

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 协议无法成功结束,并不会带来进一步的问题。

DKG 协议的门限提升漏洞分析
  • 如果 DKG 协议中没有额外验证,那么 DKG 协议会正常结束,但是最终生成的分片将永远无法重建私钥,或者签名,这种情况会直接造成资损。补充一下,我们注意到有些开源算法库缺乏验证,会导致这种严重的后果。


注意:有一种特殊的情况,如果是 (比如分片模式是  ,  ,  等 ) ,且有必要的私钥可恢复性验证,那么该场景不受该漏洞的影响。


漏洞修复

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

   在收到其他人发送的    后,

  • 验证分片的合法性: 

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

         

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

     

  • 计算自己的分片:

     


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


具体修复参考

  • https://github.com/Safeheron/safeheron-crypto-suites-cpp/commit/5531ce457a6de958cd0a5281d0db233188feb6d6

  • https://github.com/Safeheron/multi-party-sig-cpp/commit/71da5cd3b7bb91f1abcfe5dc251d788bdacdef89


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


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


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 将持续输出更多安全分析,希望伴随传统行业以及区块链行业用户前行,提供有价值的参考。





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




Keep Your Funds

Safe From Here On

Twitter@Safeheron

LinkedInSafeheron

公众号安全鹭


原文始发于微信公众号(安全鹭):DKG 协议的门限提升漏洞分析

版权声明:admin 发表于 2024年2月21日 上午10:06。
转载请注明:DKG 协议的门限提升漏洞分析 | CTF导航

相关文章