Girault知识证明中的Frozen Heart漏洞

在本系列的第一部分中，我们披露了破坏多个零知识证明系统实现健全性的关键漏洞。这类被我们称为Frozen Heart的漏洞，是由Fiat-Shamir转换的不安全实现引起的，允许恶意用户为随机声明伪造证明。该漏洞具有普遍性，可应用于任何不安全实现Fiat-Shamir转换的证明系统。在本文中，我将展示如何利用Girault知识证明中的Frozen Heart漏洞。

零知识证明与Fiat-Shamir转换

本文假设您对零知识证明有一定了解。如果您想了解更多相关信息，可以参考Matt Green的入门文章等有用的博客文章和视频。要详细了解Fiat-Shamir转换，请查看我写的详细解释博客文章。您还可以查看ZKDocs获取关于这两个主题的更多信息。

Girault知识证明

在Girault知识证明协议中，证明者证明他知道某个值在复合模数下的离散对数。换句话说，证明者使验证者相信他知道某个秘密值x，使得h = g⁻ˣ mod N，其中g是高阶生成元，N是某个复合模数（例如，N = p * q，其中p和q是两个素数）。要了解更多关于该协议的信息，请查看我们在ZKDocs上的描述。如果您熟悉Schnorr证明，可以将Girault知识证明视为在复合模数而非素数模数上进行的Schnorr证明。

该协议默认是交互式的，但可以使用Fiat-Shamir转换使其变为非交互式：

来自ZKDocs的Girault知识证明的交互式和非交互式版本（来源）

从高层次来看，证明者首先生成一个随机值r，并计算承诺u = gʳ。然后，证明者获取随机挑战值e（在交互式版本中来自验证者，在非交互式版本中通过使用Fiat-Shamir转换来自自己），并计算最终证明值z = r + x * e。只要在所使用的群上无法计算离散对数且Fiat-Shamir挑战计算正确，该协议就被证明是安全的。

Girault知识证明中的Frozen Heart漏洞

但是，如果我们没有正确计算Fiat-Shamir挑战会发生什么？让我们看一个例子。在ZenGo的Girault知识证明实现（在修补之前）中，e是通过哈希g、N和u计算的，但不包括h（在此实现中，h由statement.ni表示）。在本系列的第一部分中，我们介绍了安全实现Fiat-Shamir转换的经验法则：Fiat-Shamir哈希计算必须包括零知识证明语句中的所有公共值以及证明中计算的所有公共值（即所有随机“承诺”值）。因此，未能在此计算中包含h会引入Frozen Heart漏洞，允许恶意证明者为随机h值伪造证明，即使他们不知道其离散对数。

让我们逐步了解如何利用此Frozen Heart漏洞。我们首先为u和z选择随机值。由于h未包含在Fiat-Shamir实现中，我们现在可以计算e = Hash(g,N,u)。接下来，我们需要找到一个能通过验证检查的h值：u = gᶻhᵉ mod N。除了h之外，我们已经知道所有值：我们生成了u和z，我们计算了e，而g和N都是公共的。因此，我们可以求解h：

u = gᶻhᵉ mod N
hᵉ = ug⁻ᶻ mod N
e_inv = e⁻¹ mod phi(N)
h = (ug⁻ᶻ)^(e_inv) mod N

如果我们代入此h值，我们知道第二次验证检查将通过，因为我们选择h specifically是为了通过此检查。执行的唯一其他检查是挑战值e的检查，但此检查也将通过，因为我们以相同方式计算了此值。请记住，我们只是随机选择了u。这意味着我们实际上不知道u的离散对数（即，找到值t使得gᵗ = u mod N是不可行的）。由于我们不知道u的离散对数，我们也不知道h的离散对数。然而，我们欺骗了验证者认为此证明有效，即使不知道此离散对数，这意味着我们成功伪造了证明。

注意：为了计算e_inv，恶意证明者需要能够计算phi(N)，这需要知道N的质因数。

Frozen Heart对Girault知识证明的影响

Frozen Heart漏洞在Girault知识证明中至关重要，因为它们允许攻击者伪造证明。但是，此漏洞对使用此证明系统的应用程序的影响完全取决于证明系统的使用方式。如果Girault知识证明仅用于独立的公钥（即不作为某些更大协议一部分使用的密钥），那么Frozen Heart漏洞可能不那么严重。

原因是，对于Girault方案，Frozen Heart漏洞使得伪造随机h值成为可能。但这并不比生成随机x并计算h = g⁻ˣ更强大，这会导致我们可以为其构造证明的随机h。然而，如果此证明系统在更大、更复杂的协议中使用——例如阈值签名方案，要求证明不可伪造——那么Frozen Heart漏洞可能非常严重。

尽管在某些上下文中，Frozen Heart漏洞对Girault方案（以及出于相同原因的Schnorr方案）可能不关键，但对于更复杂的证明系统而言，情况并非如此。要更详细地了解这一点，请查看本系列即将发布的第3部分，其中我们探讨了Bulletproofs证明系统中的Frozen Heart漏洞。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News