慢雾安全团队提醒，在实际应用中需注意审查 Fiat-Shamir 实现的正确性。
作者：Johan， 慢雾安全团队
封面：Photo by Nicolas Arnold on Unsplash
背景
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 和 bt: 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 无关的参数，代入验证方程：
可以等于 V 。
也就是说攻击者可以在不知道秘密值的情况下通过协议验证。
还有一些论文 [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免责声明：作为区块链信息平台，本站所发布文章仅代表作者及嘉宾个人观点，与 Web3Caff 立场无关。文章内的信息仅供参考，均不构成任何投资建议及要约，并请您遵守所在国家或地区的相关法律法规。
