影响 Girault、Bulletproofs 和 PlonK 的漏洞的协同披露

Trail of Bits 公开披露了多个零知识证明系统（包括 PlonK 和 Bulletproofs）实现中存在的严重漏洞，这些漏洞破坏了系统的可靠性。这些漏洞是由 Fiat-Shamir 变换的不安全实现引起的，这些实现允许恶意用户伪造随机语句的证明。

我们将这类漏洞称为 Frozen Heart。frozen 是 FoRging Of ZEro kNowledge proofs（伪造零知识证明）的首字母缩写，而 Fiat-Shamir 变换是大多数证明系统的核心：它对于证明系统的实际应用至关重要，并且通常位于协议的中心位置。我们希望一个引人注目的名字将有助于提高密码学和更广泛的技术社区对这些问题的认识。

这是一次协同披露：我们已经通知了我们所知的受影响方，并且他们在我们发布之前已经修复了这些问题。以下存储库受到影响：

• ZenGo 的 zk-paillier
• ING Bank 的 zkrp (已删除)
• SECBIT Labs 的 ckb-zkp
• Adjoint, Inc. 的 bulletproofs
• Dusk Network 的 plonk
• Iden3 的 SnarkJS
• ConsenSys 的 gnark

其中一个证明系统 Bulletproofs 中的漏洞源于最初的学术论文中的一个错误，作者在其中推荐了一种不安全的 Fiat-Shamir 生成方法。除了向上述存储库披露这些问题之外，我们还联系了 Bulletproofs 的作者，他们现在已经修复了这个错误。

由 Fiat-Shamir 实现问题引起的漏洞并不新鲜（例如，参见此处和此处），当然也不是由我们发现的。不幸的是，根据我们的经验，它们在整个零知识生态系统中非常普遍。事实上，我们已经向之前的一些客户报告了几个类似的漏洞。令人惊讶的是，尽管这些问题非常普遍，但密码学和安全社区似乎普遍没有意识到这些问题。

在这篇博文中，我将首先从高层次上描述 Frozen Heart 漏洞。然后，我将讨论 Frozen Heart 漏洞在实践中如此常见的原因（剧透：糟糕的文档和指导），社区可以采取哪些步骤来预防它们，以及 Trail of Bits 在领导这项工作中的作用。最后，我将提供我们协同披露的详细信息。

这是关于 Frozen Heart 漏洞的系列文章的第一部分。在第 2、3 和 4 部分中，我将通过介绍它们对 Girault 知识证明、Bulletproofs 和 PlonK 的影响来描述这些漏洞在实践中是如何实际运作的。请务必关注未来几天的这些帖子！

零知识证明和 Fiat-Shamir 变换

这篇文章假定你对零知识证明有一定的了解。如果你想了解更多关于它们的信息，你可以找到一些有用的博客文章和视频，例如 Matt Green 的入门读物。要了解更多关于 Fiat-Shamir 变换的信息，请查看我写的博客文章，其中更详细地解释了它。你还可以查看 ZKDocs 以获取有关这两个主题的更多信息。

Frozen Heart 漏洞

Fiat-Shamir 变换应用于具有以下结构的证明系统：

1. 证明者生成一个随机值：承诺。
2. 验证者用一个随机值响应：挑战。
3. 然后，证明者使用承诺、挑战和她的秘密数据来生成零知识证明。

每个证明系统都附带一个安全证明，该证明保证只要满足某些假设，攻击者就无法伪造证明。对于这种结构的证明系统，一个非常重要的假设是，验证者生成的挑战值是完全不可预测且不受证明者控制的。从高层次上讲，原因是证明者生成的零知识证明只有在满足一个非常特定的数学关系时才被认为是有效的。证明者可以通过两种方式满足这种关系：

1. 他实际上拥有满足该关系所需的必要秘密数据，并且他以诚实的方式生成零知识证明。
2. 他没有必要的秘密数据，但他猜测随机值并侥幸成功。

对于一个安全的证明系统，恶意证明者实际上不可能实现选项 2（即，只要随机挑战是完全不可预测的，他们只有 2 的 128 次方分之一的概率猜对）。但是，如果恶意证明者可以用某种方式预测这个值，那么他实际上很容易通过找到满足必要数学关系的随机值来提交证明伪造。这正是 Frozen Heart 漏洞的工作方式。

这个漏洞是通用的；它可以应用于任何不安全地实现 Fiat-Shamir 变换的证明系统。但是，该漏洞的确切细节取决于所讨论的证明系统，并且该漏洞的影响取决于周围应用程序如何使用该证明系统。有关该漏洞如何影响不同系统的示例，请务必阅读我即将发布的文章，其中描述了 Girault 知识证明、Bulletproofs 和 PlonK 中的 Frozen Heart 漏洞。你还可以查看我之前的 Fiat-Shamir 博客文章，其中我展示了它如何适用于 Schnorr 证明系统。

预防 Frozen Heart 漏洞

Frozen Heart 漏洞会影响使用 Fiat-Shamir 变换的任何证明系统。为了防止这些漏洞，你需要遵循以下计算 Fiat-Shamir 变换的经验法则：Fiat-Shamir 哈希计算必须包括零知识证明语句中的所有公共值和证明中计算的所有公共值（即，所有随机“承诺”值）。

在这里，零知识证明语句是对证明系统正在证明的内容的正式描述。举个例子，让我们看一下 Schnorr 证明系统。Schnorr 证明系统的（非正式）证明语句如下：证明者证明她知道一个秘密值 x，使得 h = gx mod q，其中 q 是一个素数，g 是一个有限群的生成元。这里，h、g 和 q 都是公共值，而 x 是一个私有值。因此，我们需要将 h、g 和 q 包含在我们的 Fiat-Shamir 计算中。

但我们还没有完成。在协议的第 1 步中，证明者生成一个随机值 r，并计算 u = gr（这里，u 是“承诺”）。这个 u 值然后作为证明的一部分发送给验证者，所以它也被认为是公开的。因此，u 需要包含在 Fiat-Shamir 计算中。你可以看到所有这些值都包含在 ZKDocs 中的哈希计算中。

如果缺少其中一些值（特别是 h 或 u），则会引入 Frozen Heart 漏洞。如果缺少这些值，恶意证明者可以伪造她不知道离散对数的随机 h 值的证明。同样，要了解这是如何工作的，请阅读我之前的 Fiat-Shamir 博客文章。

这里的细节至关重要。即使对于 Schnorr 证明系统（可以说是实践中最简单的零知识证明协议），也很容易犯错误。试想一下，在复杂的证明系统中引入错误有多么容易，这些证明系统使用多个 Fiat-Shamir 变换，例如 Bulletproofs 和 PlonK。

问题

为什么这种类型的漏洞如此普遍？这实际上归结为学术论文中含糊不清的描述以及围绕这些协议的一般指导不足的结合。

让我们以 PlonK 为例。如果你检查协议的细节，你会看到作者没有明确解释如何计算 Fiat-Shamir 变换（即，哈希这些值）。相反，作者指示用户通过哈希“transcript（副本）”来计算值。他们确实在另一个位置描述了他们所说的“transcript”是什么意思，但从未明确地。该证明系统的一些实现仅仅因为围绕术语“transcript”的歧义而错误地进行了这种计算。

信不信由你，PlonK 的描述实际上比大多数论文中的重要描述要好。有时论文的作者实际上会指定一个不安全的实现，就像 Bulletproofs 的情况一样（我们将在即将发布的后续文章中看到）。此外，大多数学术论文只介绍协议的交互式版本。然后，在他们描述了协议之后，他们顺带提一下，可以使用 Fiat-Shamir 变换使其变为非交互式。他们向你提供了 1980 年代最初的 Fiat-Shamir 出版物，但他们很少说应该如何实际使用这种技术！

你能想象如果所有密码学原语都有这样的文档问题吗？我们有一个完整的 RFC 专门用于确定性地为 ECDSA 生成 nonce，但它仍然被错误地实现。想象一下，如果没有 ECDSA 的标准或指导，开发人员只能通过阅读其原始论文来实现该算法。想象一下，如果这篇论文没有明确解释如何生成这些 nonce，而是将读者指向 1980 年代一篇论文中的技术。这基本上是大多数零知识证明系统目前的状态。

需要明确的是，我并不是要谴责这些论文的作者。这些协议非常令人印象深刻，并且已经需要大量工作来构建，并且编写其协议的全面实现细节不是这些作者的工作。但问题是，对于这些协议，实际上没有强有力的指导，因此开发人员不得不主要依赖学术论文。所以，我的观点不是我们应该责怪作者，而是我们不应该对后果感到惊讶。

解决方案

解决这些问题的最佳方法是生成更好的实施指导。学术论文并非旨在成为实施的综合指南。开发人员，尤其是非密码学家，仅使用这些论文中的指导来实施复杂的协议可能会出错并引入这些关键漏洞。这正是我们创建 ZKDocs 的原因。通过 ZKDocs，我们旨在提供更清晰的实施指导，特别关注协议中经常搞砸的领域，例如 Fiat-Shamir 转换。如果你正在创建自己的零知识证明实现，请查看我们的 ZKDocs 的 Fiat-Shamir 部分！

还值得一提的是，如果这些协议的测试向量被广泛使用，这些问题可能会或多或少地被消除。具有不正确的 Fiat-Shamir 变换的实现将无法通过使用来自正确实现的测试向量的测试。但是，鉴于对大多数这些证明系统的指导有限，为所有这些系统生成测试向量似乎不太可能。

最后，调查这些 Frozen Heart 漏洞很好地提醒了代码审计的价值。我的团队和我审查了许多公共存储库，我们发现了很多正确执行这些转换的实现。这些实现大多由执行内部审计和通常外部代码审计的人员小组构建。

协同披露

在我们的披露之前，我的队友和我花了过去几个月的时间研究和审查尽可能多的证明系统的实现。一旦我们的研究完成，我们于 2022 年 3 月 18 日向 ZenGo、ING Bank、SECBIT Labs、Adjoint Inc.、Dusk Network、Iden3、ConsenSys 及其所有活跃的分支披露了这些漏洞。我们还在这一天联系了 Bulletproofs 论文的作者。

截至 2022 年 4 月 12 日，ZenGo、Dusk Network、Iden3 和 ConsenSys 已使用所需的修复程序修补了他们的实现。ING Bank 已删除其易受攻击的存储库。Bulletproofs 论文的作者已更新了他们关于 Fiat-Shamir 变换的部分。我们无法与 SECBIT Labs 或 Adjoint Inc. 取得联系。

• Zengo 提交了此补丁。
• Dusk Network 提交了此补丁。
• Iden3 提交了此补丁。
• ConsenSys 提交了此补丁。

我们要感谢 ZenGo、ING Bank、Dusk Network、Iden3、ConsenSys 和 Bulletproofs 作者与我们迅速合作以解决这些问题。

致谢

我要感谢我的每位队友帮助我审查公共实现，并感谢 David Bernhard、Olivier Pereira 和 Bogdan Warinschi 他们在这方面的工作。最后，非常感谢 Sarang Noether 博士帮助我更深入地理解这些问题。

• 原文链接： blog.trailofbits.com/202...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～