Bulletproofs中的Frozen Heart漏洞
在本系列的第一部分中，我们披露了破坏多个零知识证明系统实现健全性的关键漏洞。这类被我们称为Frozen Heart的漏洞，是由Fiat-Shamir转换的不安全实现引起的，允许恶意用户为随机陈述伪造证明。在第二部分中，我们演示了如何利用特定证明系统（Girault的知识证明）中的Frozen Heart漏洞。在本文中，我们将演示针对另一个证明系统Bulletproofs的此类利用。
零知识证明与Fiat-Shamir转换
本文假设您对零知识证明有一定了解。如果您想了解更多相关信息，可以参考一些有用的博客文章和视频，例如Matt Green的入门指南。要了解更多关于Fiat-Shamir转换的信息，可以查看我写的详细解释博客文章。您还可以查看ZKDocs获取关于这两个主题的更多信息。
Bulletproofs
Bulletproofs是复杂且高效的零知识范围证明，证明者可以证明某个秘密值位于预定义范围内，而无需透露该值本身。
Bulletproofs基于称为Pedersen承诺的密码学原语，这是一种特定类型的承诺方案。使用承诺方案，一方可以创建承诺，该承诺将该方绑定到秘密值，但不透露有关该值的任何信息。之后，该方可以解承诺或揭示该承诺；如果被揭示，并且如果方案是安全的，另一方可以确信揭示的值与原始承诺值相同。
要为值x创建Pedersen承诺，您生成一个随机的gamma，然后使用comm = (g^x)(h^gamma)计算承诺：g和h是您的有限群的不同生成元，并且h相对于g的离散对数未知（即，找到a使得g^a = h是不可行的）。由于Pedersen承诺是安全的，承诺不会透露有关x的任何信息，并且不可能对承诺进行模棱两可的解释；这意味着您不能发布产生相同承诺的不同x’和gamma’值（假设g和h之间的离散对数未知）。
Pedersen承诺不透露任何信息这一事实对于复杂协议可能是有问题的，例如那些需要保证秘密值落在预定义范围内的协议（例如，限制这些值以防止整数溢出）。然而，使用Bulletproofs，我们可以证明我们的承诺对应于预定义范围内的值，例如[0, 2^32)，而不透露具体的输入值。
不幸的是，Bulletproofs协议过于复杂，无法在本文中详细讲解。为了描述Frozen Heart漏洞，我将逐步介绍Bulletproofs协议，但如果您之前没有见过它，这将很难理解。如果您想了解更多关于Bulletproofs的工作原理，可以在网上找到许多博客和视频，例如这篇撰写。
Bulletproofs中的Frozen Heart漏洞
Bulletproofs有几个Fiat-Shamir转换（确切数量取决于所使用的参数），这些转换可能以不同方式被滥用。在本节中，我将逐步介绍如何利用其中一个漏洞。实际上，这个漏洞是原始Bulletproofs论文作者犯的一个错误的结果，他们推荐使用不安全的Fiat-Shamir实现。ING Bank的zkrp、SECBIT Labs的ckb-zkp和Adjoint, Inc.的bulletproofs都受到了这个问题的影响。
Bulletproofs基于Pedersen承诺，其形式为V = (g^v)(h^gamma)。提醒一下，Bulletproofs的目标是证明秘密值v位于预定义范围内。为了本文的目的，我们将使用[0, 2^32)作为我们的预定义范围。以下是Bulletproofs的形式零知识证明陈述：
Bulletproofs的形式证明陈述（来源）
在本系列的第一部分中，我们介绍了安全实现Fiat-Shamir转换的经验法则：Fiat-Shamir哈希计算必须包括零知识证明陈述中的所有公共值以及证明中计算的所有公共值（即所有随机“承诺”值）。因此，我们希望确保此陈述中的所有公共值（g、h、V、n）都在Fiat-Shamir计算中，以及我们尚未涵盖的随机承诺。
与大多数密码学论文一样，Bulletproofs算法以其交互版本呈现。以下是论文中呈现的证明者角色：
原始论文中的交互式Bulletproofs协议
（需要明确的是，这不是协议的完整版本。Bulletproofs论文后面描述了一个重要的优化，以减少步骤（63）中发送的证明大小，但这对于此利用的目的无关紧要。）
一旦证明者在步骤（63）中发送最终证明，验证者需要通过执行以下检查来验证它：
验证者执行以验证Bulletproofs的检查（来源）
在证明者协议的步骤（49）/（50）和（55）/（56）中，需要生成三个不同的Fiat-Shamir挑战值：x、y和z。然而，作者推荐使用不安全的计算这些值：
原始Bulletproofs论文中推荐的不安全Fiat-Shamir挑战计算（来源）
根据作者的说法，我们应该设置y = Hash(A,S), z = Hash(A,S,y), 以及（根据他们的描述）x = Hash(A,S,y,z,T1,T2)。这违反了我们的经验法则：陈述中的公共值——最重要的是V——都没有被包括在内。这是一个Frozen Heart漏洞！这个漏洞是关键的；正如您可能已经猜到的，它允许恶意证明者为实际上位于预定义范围之外的值伪造证明。
现在，要实际利用这一点，恶意证明者可以执行以下操作：
- 将v设置为范围内的任何值。所以我们假设v = 3。
- 选择一个随机的gamma值。
- 使用这些v和gamma值，按照预期（分别根据步骤（41）、（42）、（44）和（47））生成aL、aR、A和S。
- 按照Bulletproofs论文中的描述计算t1和t2（这不在上图中，但在论文的文本中描述），然后通过随机生成数字计算值t1’和t2’。在计算T1和T2时，将t1替换为t1’，t2替换为t2’。所以，明确地说，我们设置Ti = (g^{t’_i})(h^{tau_i})（如预期，但我们将ti切换为ti’）。
- 按照协议计算其余值（l、r、t_hat、tau_x、mu）。
- 最后，使用相同的gamma但使用新的v’值计算一个新的V。具体来说，设置v’ = 3 + (t1 - t'1)(x/z^2) + (t2 - t'2)(x^2/z^2)（您稍后会看到为什么这样选择）。这里，3来自步骤1中设置v = 3。
现在，回顾上面的所有验证检查。我们计算的不同于预期的唯一值是T1、T2和V。由于我们按预期计算了其他值，所有检查将自动通过，除了检查（65），它依赖于T1、T2和V。但由于x、y和z是独立于V计算的，我们可以计算一个恶意的V值，该值依赖于这些值，并将通过检查（65）。让我们看看这是如何工作的：
首先，让我们简化检查（65）的左侧：
LHS = (g^{t_hat})(h^{tau_x}) = (g^{[t0 + t1 * x + t2 * x^2]})(h^{[tau2 * x^2 + tau1 * x + z^2 * y]})
现在，让我们简化检查（65）的右侧：
RHS = (V^{z^2})(g^{delta(y,z)})(T1^x)(T2^{x^2}) = (V^{z^2})(g^{delta(y,z)})[(g^{t'1})(h^{tau1})]^x[(g^{t'2})(h^{tau2})]^{x^2}
现在，如果您查看我们为V选择的v’值，您会看到g中T1和T2的指数将抵消V中g的指数。因此右侧简化如下：
= g^{[3z^2 + t1 * x + t2 * x^2 + delta(y,z)]}h^{[gamma * z^2 + tau1 * x + tau2 * x^2]}
我们可以看到h中的指数在两侧是相同的。我们现在只需要检查g中的指数是否匹配。
在左侧的g指数中，我们有t0 + t1 * x + t2 * x^2。
在右侧的g指数中，我们有3z^2 + delta(y,z) + t1 * x + t2 * x^2。
而t0在原始论文中定义为：
Bulletproofs论文中定义的t0（来源）
这完全正确，意味着我们成功伪造了证明。
需要明确的是，这是一个伪造，因为我们刚刚为新计算的V值提交了这个证明，其中v被设置为v’ = 3 + (t1 - t'1)(x / z^2) + (t2 - t'2)(x^2 / z^2)。由于x和z是随机的Fiat-Shamir挑战，v’最终将成为区间[0, 群阶)中的随机值。由于群阶通常比所讨论的区间（这里是2^32）大得多，v’将以压倒性概率成为范围之外的值，但证明仍然会通过。如果由于某种原因，v’不在此范围之外，恶意行为者可以简单地用新的随机值（例如，新的gamma、新的t'1等）重新开始相同的过程，直到获得所需的v’值。
Frozen Heart对Bulletproofs的影响
Frozen Heart漏洞是关键的，因为它们允许攻击者伪造证明，但它们对周围应用程序的影响取决于应用程序如何使用证明系统。正如我们在本系列第二部分中针对Schnorr和Girault证明系统所看到的，可能存在这些漏洞不关键的情况。然而，对于Bulletproofs来说，这种情况不太可能发生。
在我们的示例中，我们能够为群阶中的随机值产生伪造。在大多数应用程序中，范围证明的预定义范围通常比群阶的大小小得多。这意味着，尽管无法选择特定值，但攻击者可以轻松地为所需范围之外的值产生证明。在我们看到使用Bulletproofs的大多数上下文中，这是严重的。
请关注本系列的最后一部分，我们将在其中探索更复杂证明系统PlonK中的Frozen Heart漏洞。
如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News