披露Shamir秘密共享漏洞并宣布ZKDocs
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即可。
阈值签名方案的挑战
阈值签名方案是强大的密码学对象，但它们需要复杂的非标准化原语，如零知识证明、承诺方案和可验证秘密共享。遗憾的是，除了学术出版物外，基本上没有关于实现这些方案或其安全陷阱的指导或文档，这导致了实践中的多个问题，包括我们今天披露的这两个漏洞。
随着这些漏洞的披露，我们发布了ZKDocs——我们为非标准化密码学原语编写的文档。我们希望这项工作能够惠及更广泛的密码学社区。
什么是阈值签名方案？
阈值签名方案是一种允许多个用户生成和控制私签名密钥的协议。用户可以共同对消息生成数字签名，但没有人能够单独签名。
许多人都熟悉多重签名（multisig）协议的概念，主要用于加密货币钱包，只有在收到足够多用户签名后才会执行交易。这些方案的主要区别在于：在多重签名方案中，每个用户都有用于签名的个人私钥/公钥对；而在阈值签名方案中，每个用户持有同一密钥的一个份额。使用多重签名方案时，签名数量与用户数量成正比；使用阈值签名方案时，只产生一个组签名。
可验证秘密共享（VSS）是什么？
秘密共享是一种将密钥（或其他秘密数据）分割成密钥份额的密码学协议。这些密钥份额应该看起来完全随机，单独来看不会泄露任何关于底层秘密的信息。但当足够多的份额组合时，可以恢复原始秘密。最常见的秘密共享技术是Shamir秘密共享方案，它利用了多项式的特性。
Shamir方案的高层思想是：对于n个用户，需要至少t个用户（其中t ≤ n）通过组合他们的份额来恢复秘密。为实现这一点，我们在有限群上生成一个次数为t-1的随机多项式p，常数项设置为秘密值。
然后，通过在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团队与我们迅速合作解决这些问题。