慢雾：Fiat-Shamir 冰心漏洞解析

by: Johan

背景

Frozen Heart “冰心”漏洞，由 Trail of Bits 团队命名，其中 Frozen 代表 FoRging Of ZEro kNowledge proofs，Heart 指 Fiat-Shamir transformation 是很多 proof system 的核心。该漏洞指应用了“弱 Fiat-Shamir”变换，只对证明者的部分消息进行散列而不散列公开信息（比如参数、公开输入等），因此出现的安全问题。

下面我们将对这个漏洞进行全面的解析，我们先来谈下什么是 Fiat-Shamir 变换。

Fiat-Shamir 变换

Fiat-Shamir 变换，又叫 Fiat-Shamir Heuristic 或者 Fiat-Shamir Paradigm，是 Fiat 和 Shamir 在 1986 年提出的一个变换，用于将交互式零知识证明协议转化为非交互式零知识证明协议。它通过将协议中的随机挑战（challenge）替换为哈希函数的输出来实现这一转化。这样，证明者可以生成证明并将其发送给验证者，而无需进行交互式的挑战和响应。

Schnorr 证明是一种交互式零知识证明协议，它允许证明者向验证者证明某个陈述为真，而不需要透露陈述的细节，同时验证者可以进行交互式的验证。它通常用于证明者知道某个秘密值而不透露该秘密值的情况。

借助 Fiat-Shamir 变换，可以将 Schnorr 交互式证明改造成非交互式。

Schnorr 可以在有限域或椭圆曲线（EC）上实现，技术规范基本相同，只是底层循环群不同。下面我们主要以有限域的形式来描述这两个过程 [1]：

* 符号说明：
Alice: 协议中的证明者的假定身份
Bob: 协议中的验证者的假定身份
a | b: a 能整除 b
a || b: a 和 b 的连接
[a, b]: 整数区间，包括 a 和 b
t: Bob 选择的挑战的比特位数
H: 安全的密码哈希函数
p: 一个大素数
q: p-1 的一个大素数因子，即 q | p-1
Zp*: 模 p 的整数的乘法群
Gq: 具有素数阶 q 的 Zp* 的一个子群
g: Gq 的生成元
g^d: g 的 d 次方
a mod b: a 对 b 取模
Fp: 一个由 p 个元素组成的有限域，其中 p 是一个素数

基于有限域的实现

1. 交互式

首先，Alice 计算 A = g^a mod p，其中私钥 a 取值 [0, q-1]，然后公开公钥 A；

然后，Alice 在不公开 a 的情况下，向 Bob 证明他知道 A 对应的私钥 a：

如果 check 为 true，那么就能证明 Alice 知道 a ，原理如下：

这里之所以需要由 Bob 生成随机 c ，是因为如果攻击者在公开 A 之前知道了这个值，那么他就可以在不知道真实 a 的情况下伪造证明。攻击者伪造 (A, V, r) 方法如下：

Verifier 收到这三个参数后，代入验证公式，也是可以通过验证的。但是我们注意看这些参数的生成过程，它们与要证明的秘密值 a 没有任何关系。

2. 非交互式

非交互式的改造也很容易，在交互式的基础上，把 Bob 随机生成 c 的过程，改成参数的 Hash 形式：

基于椭圆曲线的实现

首先，Alice 计算 A = G x [a]，其中私钥 a 取值 [0, n-1] ，然后公开公钥 A；

接着，Alice 在不公开 a 的情况下，向 Bob 证明她知道 A 对应的私钥 a：

如果 check 为 true，那么就能证明 Alice 知道 a ，原理如下：

非交互式的实现方式与上述的基于有限域的实现方式相同，就不再赘述。

弱 Fiat-Shamir 变换

上面非交互式的实现过程中，随机数：

这就存在一个安全问题，我们称它为弱 Fiat-Shamir 变换，它可以被用于伪造证明，通过预计算 A，欺骗验证者。

使用以下方法重新构造参数 (A, r)：

我们可以看到这个 A 变成了一个和 a 无关的参数，代入验证方程：

还有一些论文 [3] 描述这个过程如下：

其表达的内容是相同的。

冰心漏洞

Trail of Bits 团队曾发表文章 [2] 指出 Bulletproofs 和 Plonk 等 ZKP 系统中的 Fiat-Sharmir 实现存在漏洞，使得恶意用户可为随机 statement 伪造 proof。

以 Plonk 为例，在证明生成的 Round 2,3,4,5 中，均利用了 Fiat-Shamir 算法生成随机数。

在论文 [3] 中调查了许多现代零知识证明系统的开源实现，发现有 36 个使用了弱 Fiat-Shamir 变换，包括 Bulletproofs、Plonk、Spartan 和 Wesolowski 的 VDF 等。攻击者可以生成通过验证的证明，而不需要知道有效的证明秘密。

漏洞实例

1. gnark

这里 fs 就是一个 Fiat-Shamir 计算实例，在 Round2 证明计算 z(X) 参数时，由于没有将公共输入绑定到 challenge，导致了可以伪造证明信息。

2. snarkjs

同样由于没有包含 publicSignals ，导致可以伪造证明信息。

总结

从披露的内容我们可以看到这个漏洞的通用性和广泛性，它会对零知识证明造成严重危害，在实际应用中我们需要注意审查 Fiat-Shamir 实现的正确性，将公共见证数据也加入到随机数生成中，避免被攻击者伪造证明。

最后，感谢领先的⼀站式数字资产⾃托管服务商 Safeheron 提供的专业技术建议。

参考文档:

[1]. https://datatracker.ietf.org/doc/html/rfc8235

[2]. https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/

[3]. https://eprint.iacr.org/2023/691.pdf

原文始发于微信公众号（慢雾科技）：慢雾：Fiat-Shamir 冰心漏洞解析