Trail of Bits公开披露了影响多个零知识证明系统（包括PlonK和Bulletproofs）实现的关键漏洞，这些漏洞破坏了系统的可靠性。这些漏洞是由于Fiat-Shamir转换的不安全实现导致的，使得恶意用户可以伪造随机陈述的证明。
我们将这类漏洞命名为“Frozen Heart”。其中“Frozen”是“零知识证明伪造”（FoRging Of ZEro kNowledge proofs）的首字母缩写，而Fiat-Shamir转换是大多数证明系统的核心：它对实际应用至关重要，并且通常位于协议的中心位置。我们希望这个引人注目的名称能帮助密码学和更广泛的技术社区提高对这些问题的认识。
这是一次协调披露：我们已经通知了已知受影响的各方，并在我们发布之前，他们已修复了这些问题。以下仓库受到影响：
- ZenGo的zk-paillier
- ING银行的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^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 = g^x mod q，其中q是一个素数，g是一个有限群的生成元。这里，h、g和q都是公共值，x是私有值。因此，我们需要在Fiat-Shamir计算中包含h、g和q。
但我们还没有完成。在协议的第1步中，证明者生成一个随机值r，并计算u = g^r（这里u是“承诺”）。然后，这个u值作为证明的一部分发送给验证者，因此它也被视为公共值。因此，u需要包含在Fiat-Shamir计算中。您可以看到所有这些值都包含在ZKDocs的哈希计算中。
如果缺少其中一些值（特别是h或u），就会引入Frozen Heart漏洞。如果缺少这些值，恶意证明者可以为随机h值伪造证明，而不知道离散对数。再次强调，要了解这是如何工作的，请阅读我之前的Fiat-Shamir博文。
细节在这里至关重要。即使对于Schnorr证明系统（可以说是实践中使用的最简单的零知识证明协议），也容易出错。想象一下，在复杂的证明系统中引入错误有多容易，比如Bulletproofs和PlonK，它们使用多个Fiat-Shamir转换。
问题
为什么这类漏洞如此普遍？这实际上归结为学术论文中的模糊描述和围绕这些协议的普遍缺乏指导。
以PlonK为例。如果您检查协议的细节，您会发现作者没有明确解释如何计算Fiat-Shamir转换（即哈希这些值）。相反，作者指示用户通过哈希“转录”来计算该值。他们在另一个位置描述了“转录”的含义，但从未明确说明。一些证明系统的实现仅仅因为“转录”一词的模糊性而错误地进行了计算。
信不信由你，PlonK的描述实际上比大多数论文中的重要描述要好。有时，论文的作者实际上会指定一个不安全的实现，就像Bulletproofs的情况一样（我们将在后续文章中看到）。此外，大多数学术论文只呈现协议的交互版本。然后，在他们描述了协议之后，他们顺便提到可以使用Fiat-Shamir转换使其非交互。他们向您提供了1980年代的原始Fiat-Shamir出版物，但他们很少说明应该如何实际使用这种技术！
您能想象如果所有加密原语都有这样的文档问题吗？我们有一个完整的RFC专门用于确定性地为ECDSA生成随机数，但它仍然被错误地实现。想象一下，如果没有ECDSA的标准或指导，开发人员只能通过阅读其原始论文来实现该算法。想象一下，如果这篇论文没有明确解释如何生成这些随机数，而是指向1980年代论文中的技术。这基本上就是大多数零知识证明系统的现状。
需要明确的是，我并不是要谴责这些论文的作者。这些协议非常令人印象深刻，并且已经花费了大量工作来构建，而这些作者的工作并不是为他们的协议编写全面的实现细节。但问题在于，确实没有强有力的指导来支持这些协议，因此开发人员不得不主要依赖学术论文。因此，我的观点不是我们应该责怪作者，而是我们不应该对后果感到惊讶。
解决方案
解决这些问题的最佳方法是提供更好的实现指导。学术论文并不是为全面指导实现而设计的。开发人员，尤其是非密码学家，仅依靠这些论文的指导来实现复杂协议时，很可能会出错并引入这些关键漏洞。这正是我们创建ZKDocs的原因。通过ZKDocs，我们旨在提供更清晰的实现指导，特别关注协议中常见的错误区域，例如Fiat-Shamir转换。如果您正在创建自己的零知识证明实现，请查看ZKDocs的Fiat-Shamir部分！
值得一提的是，如果这些协议的测试向量广泛可用，这些问题可能会或多或少地被消除。具有不正确Fiat-Shamir转换的实现将无法通过来自正确实现的测试向量的测试。然而，鉴于大多数证明系统的指导有限，为所有这些系统生成测试向量似乎不太可能。
最后，调查这些Frozen Heart漏洞很好地提醒了我们代码审计的价值。我和我的团队审查了许多公共仓库，我们发现很多实现正确地执行了这些转换。这些实现大多数是由进行内部和通常外部代码审计的人员组构建的。
协调披露
在我们披露之前，我和我的团队成员在过去几个月里研究和审查了尽可能多的证明系统的实现。一旦我们的研究完成，我们于2022年3月18日向ZenGo、ING银行、SECBIT Labs、Adjoint Inc.、Dusk Network、Iden3、ConsenSys以及它们的所有活跃分支披露了这些漏洞。我们还于当天联系了Bulletproofs论文的作者。
截至2022年4月12日，ZenGo、Dusk Network、Iden3和ConsenSys已使用所需的修复程序修补了它们的实现。ING银行已删除其易受攻击的仓库。Bulletproofs论文的作者已更新了关于Fiat-Shamir转换的部分。我们未能与SECBIT Labs或Adjoint Inc.取得联系。
- ZenGo提交了此补丁。
- Dusk Network提交了此补丁。
- Iden3提交了此补丁。
- ConsenSys提交了此补丁。
我们要感谢ZenGo、ING银行、Dusk Network、Iden3、ConsenSys和Bulletproofs的作者迅速与我们合作解决这些问题。
致谢
我要感谢我的每位团队成员协助我审查公共实现，以及David Bernhard、Olivier Pereira和Bogdan Warinschi对这项漏洞的工作。最后，特别感谢Sarang Noether博士帮助我更深入地理解这些问题。
如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News