披露Shamir秘密共享漏洞并宣布ZKDocs - Trail of Bits博客
Filipe Casal, Jim Miller
2021年12月21日
密码学, 漏洞披露, 零知识
Trail of Bits公开披露两个影响币安阈值签名方案库(tss-lib)及其大多数活跃分叉的Shamir秘密共享实现漏洞。受影响代码库完整列表如下：
- 币安的tss-lib
- Clover Network的threshold-crypto
- Keep Network的keep-ecdsa
- Swingby的tss-lib
- THORchain的tss-lib
- ZenGo X的curv
这些漏洞允许恶意用户窃取其他用户的私钥或使其节点崩溃。利用这些漏洞非常简单：攻击者只需在密钥生成协议或重新共享协议开始时配置恶意ID即可。
什么是阈值签名方案？
阈值签名方案是一种允许用户群体生成和控制私钥签名密钥的协议。用户可以共同对消息生成数字签名，但任何个体都无法单独签名。
许多人熟悉多重签名(multisig)协议的概念，主要用于加密货币钱包，只有在收到足够多用户签名后才会执行交易。主要区别在于：在多重签名方案中，每个用户拥有个人私钥/公钥对进行签名；而在阈值签名方案中，每个用户持有同一密钥的一个份额。使用多重签名方案时，签名数量与用户数量成正比；使用阈值签名方案时，只产生一个组签名。
阈值签名非常复杂。这些方案的工作原理超出本文范围，但如果您想了解实际工作原理或与其他方案(如多重签名)的比较，可以找到详细描述的博客文章。
什么是可验证秘密共享(VSS)？
秘密共享是一种将密钥(或其他秘密数据)拆分为密钥份额的密码协议。这些密钥份额应完全随机，单独看不会泄露原始秘密的任何信息，但当足够多份额组合时，可以恢复原始秘密。最常用的技术是Shamir秘密共享方案，利用多项式特性。
Shamir方案的核心思想是：对于n个用户，至少需要t个用户(其中t≤n)通过组合份额来恢复秘密。为此，我们在有限群上生成一个t-1次随机多项式，常数项设置为秘密值。
然后通过在n个不同点(每个用户一个点)计算多项式来创建秘密份额。单个点(甚至几个点，取决于t值)不会泄露多项式信息。但如果用户组合足够多点，可以通过多项式插值恢复原始多项式。由于秘密值编码在多项式中，恢复多项式即恢复秘密。
阈值签名方案使用秘密共享生成在多个用户间共享的签名密钥，但实际上大多数方案必须使用更高级的可验证秘密共享(VSS)。用户通常不能假设协议参与者都是诚实的。VSS允许用户验证收到的份额是否诚实生成。最常用的VSS方案由Feldman开发，使用与Shamir方案相同的技术生成份额(即使用秘密作为常数项生成随机多项式)，并创建额外值使这些份额可验证。
从零到英雄
我们披露影响不同阈值签名方案实现中Feldman可验证秘密共享的两个漏洞。这些漏洞并非无法预见的新颖分析结果；相反，它们源于秘密共享的少数已知弱点之一。我们今天强调它们不仅因为受影响厂商数量多，还因为它们代表了非标准化密码学中同一重复问题导致的大量关键漏洞：缺乏文档和指导。
第一个漏洞与秘密份额生成方式相关。由于我们将多项式常数项定义为秘密值，生成份额时必须确保多项式点的x值非零。如果在0点创建份额，多项式计算结果就是常数项，完全泄露秘密值：
大多数实现通过在多点(1,2,…,n)计算多项式来完全避免这种可能性，其中n是所需份额数。但有些实现在特定值计算多项式；例如币安实现在每个用户唯一ID值计算多项式。这种设计必须验证这些ID非零；大多数成功做到这一点。但有些实现忘记这些共享方案在有限群上运行，因此零检查必须在模群阶下执行！如果不执行此检查，秘密值会立即泄露给将唯一ID设置为群阶的恶意用户。如果群阶为q，则：
受影响实现检查了用于生成秘密份额的用户ID非零，但未在椭圆曲线群阶下执行此检查。
从零到崩溃
第二个漏洞与模算术运算处理不当相关。根据签名消息的用户组，用户计算拉格朗日系数，即IDi/(IDi-SelfID)形式项的乘积。由于我们在有限域上工作，我们通过(IDi-SelfID)的模逆计算除法。如果用户IDi模等于当前用户ID(SelfID)，减法模等于零——但零没有模逆！易受攻击的实现未验证模逆，会因空解引用而崩溃。
我们在审计中经常发现这些漏洞；如果不严格关注模算术细节，很容易遗漏。大多数时候甚至存在验证，但如果未在有限域上下文中检查参数，这些验证是不充分的。
使用通用大整数类进行模算术时，请采取以下步骤：
- 在验证(如比较)前始终模约简数字
- 始终验证模逆和模平方根等运算。根据API，检查返回值或捕获错误以确保函数不会崩溃
- 如果仍不确定或需要第二意见，请联系我们进行审计
ZKDocs
今天我们发布ZKDocs，这是我们为非标准化密码原语编写的文档。希望通过提供这些协议的全面实现细节和安全考虑，帮助开发者未来避免这些漏洞。
随着发现更多此类漏洞实例，我们开始思考为什么它们会发生以及如何防止未来发生。不幸的是，对于非标准化密码协议，开发者需要自行弄清楚所有低级实现细节和安全陷阱。要了解资源多么有限，尝试搜索Feldman可验证秘密共享方案(同类中最常见方案！)信息。可能找到的唯一结果是维基百科文章和Feldman 1987年的原始论文。除此之外，可能找到一些Stack Overflow讨论或旧讲义。但仅此而已。
这些方案很复杂！面对如此有限的文档和指导，这些漏洞在实践中出现不应令人惊讶。通过ZKDocs，我们旨在填补这一空白。例如，要阅读我们发现的第一个零份额相关漏洞的更多细节，请查看ZKDocs中的秘密共享部分！
协调披露
- 2021年10月19日：在tss-lib中发现秘密数据泄露
- 2021年10月21日：向币安报告
- 2021年11月1日-12月3日：内部发现影响Clover、Keep Network、Swingby、THORChain和ZenGo X的问题
- 2021年12月6日：向Clover、Keep Network、Swingby、THORChain和ZenGo X报告
截至2021年12月20日，币安、Keep Network、Swingby、THORChain和ZenGo X已使用所需修复补丁其实现。唯一例外是Clover，未回复我们的邮件。
币安首先提交此补丁，随后提交此补丁修复后续错误。 Keep Network提交此补丁。 Swingby提交此补丁，随后提交此补丁修复后续错误。 THORChain提交此补丁。 ZenGo X提交此补丁。
我们要感谢币安、Keep Network、SwingBy、THORChain和ZenGo X团队与我们迅速合作解决这些问题。