协调披露影响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转换应用于具有以下结构的证明系统：
- 证明者生成一个随机值：承诺
- 验证者用一个随机值响应：挑战
- 证明者然后使用承诺、挑战和她的秘密数据生成零知识证明
每个证明系统都附带一个安全证明，只要满足某些假设，它就保证攻击者伪造证明是不可行的。对于这种结构的证明系统，一个非常重要的假设是验证者生成的挑战值对证明者完全不可预测且不可控制。在高层次上，原因是证明者生成的零知识证明只有在满足非常特定的数学关系时才被认为是有效的。证明者可以通过以下两种方式之一满足这种关系：
- 他实际上拥有必要的秘密数据来满足关系，并以诚实的方式生成零知识证明
- 他没有必要的秘密数据，但他猜测随机值并幸运地猜中
对于一个安全的证明系统，只要随机挑战完全不可预测，恶意证明者实际上不可能实现选项2（即，他们只有1/2¹²⁸的概率猜对）。但如果恶意证明者能够以某种方式预测这个值，他实际上很容易通过找到满足必要数学关系的随机值来实施证明伪造。这正是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ˣ mod q，其中q是一个质数，g是有限群的生成元。这里，h、g和q都是公共值，x是私有值。因此，我们需要在我们的Fiat-Shamir计算中包含h、g和q。
但我们还没有完成。在协议的第1步中，证明者生成一个随机值r，并计算u = gʳ（这里，u是"承诺"）。这个u值然后作为证明的一部分发送给验证者，因此它也被认为是公共的。因此，u需要包含在Fiat-Shamir计算中。您可以看到所有这些值都包含在ZKDocs中的哈希计算中。
如果缺少这些值中的一些（特别是h或u），就会引入Frozen Heart漏洞。如果缺少这些值，恶意证明者可以为随机h值伪造证明，而不知道离散对数。再次，要了解这是如何工作的，请阅读我之前的Fiat-Shamir博客文章。
细节在这里至关重要。即使对于Schnorr证明系统，这可以说是实践中使用的最简单的零知识证明协议，也很容易出错。想象一下，在复杂的证明系统中引入错误是多么容易，这些系统使用多个Fiat-Shamir转换，例如Bulletproofs和PlonK。
问题
为什么这种类型的漏洞如此普遍？这实际上归结为学术论文中模糊的描述和围绕这些协议普遍缺乏指导的结合。
让我们以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 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、ING Bank、Dusk Network、Iden3、ConsenSys和Bulletproofs作者与我们迅速合作解决这些问题。
致谢
我要感谢我的每一位团队成员协助我审查公共实现，以及David Bernhard、Olivier Pereira和Bogdan Warinschi对这项漏洞的工作。最后，非常感谢Sarang Noether博士帮助我更深入地理解这些问题。
如果您喜欢这篇文章，请分享： Twitter | LinkedIn | GitHub | Mastodon | Hacker News