如何利用 Groth16 的漏洞伪造证明

image045.jpg

1 Groth16 简介

Groth16 是非常著名的 zkSNARK 证明算法(proving scheme)之一(此外还有 PGHR13,GM17 等)。Groth16 相较于之前的证明协议,具有证明数据小(仅需3个证明数据)且验证速度快(仅需验证1个等式)的特点。目前 Groth16 已被广泛应用到诸多项目中,例如:Zcash, Filecoin 等。
Groth16 是由大牛 Jens Groth 在 2016 年发表的论文 “On the Size of Pairing-based Non-interactive Arguments” 中提出的零知识证明协议。
一般算法名称的命名会以论文的作者姓的首字母和年份组成。
例如:GGPR13,是由 Rosario Gennaro,Craig Gentry,Bryan Parno,Mariana Raykova于 2013 年在论文 “Quadratic Span Programs and Succinct NIZKs without PCPs” 中提出的算法。而 Groth16(也简称为G16),是 Jens Groth 在 2016 年发表的论文中的算法。

2 Groth16 算法速览

跟其他基于 QAP 的算法一样,Groth16 需要证明者证明自己知道一个秘密 witness (aₗ₊₁, aₗ₊₂, …, aₘ) 使得这个秘密和公开的 statement (a₁, a₂, …, aₗ) 能够满足下面的等式(其中 a₀ = 1),
image047.png
上述等式中的 uᵢ(X),vᵢ(X),wᵢ(X),h(X),t(X) 都跟具体要证明的问题本身相关,而与证明者持有的秘密 witness 以及公开的 statement 无关。

2.1 初始化阶段Initialization phase

在初始化阶段,首先随机生成一些参数 α, β, γ, δ, x ← ℤₚ*,定义 τ = (α, β, γ, δ, x),计算 σ=([σ₁]₁, [σ₂]₂)。其中,
image048.png
这里 [σ₁]₁ 是椭圆曲线 ?₁上的点, 而 [σ₂]₂ 是椭圆曲线 ?₂ 上的点,
注:[σ₁]₁,[σ₂]₂ 计算完成后,原始参数集合 σ₁ 和 σ₂ 需要被丢弃,因为它们是有毒的废料(toxic waste)。如果不丢弃,整个系统将不安全,因为拿到这些参数的人可以伪造证明。

2.2 证明阶段

证明者(prover)随机挑选 r, s ← ℤₚ,并使用 witness (aₗ₊₁, aₗ₊₂, …, aₘ) 和 statement (a₁, a₂, …, aₗ) 以及 a₀ = 1 计算 proof π = ([A]₁, [C]₁, [B]₂)。其中
image049.jpg
image050.jpg
image051.jpg

2.3 验证阶段

将 statement (a₁, a₂, …, aₗ) 以及 a₀ = 1 代入,验证以下等式是否相等。
image052.jpg
如果相等则 proof π = ([A]₁, [C]₁, [B]₂) 正确,否则 proof π 无效。
有关 Groth16 算法的详细剖析,可以参见 李星(Star Li) 的这两篇文章 《Groth16算法介绍》 和 《有关Groth16的zk证明的理解》

3. Groth16 的安全问题

Groth16 虽然效率相较之前的证明算法有质的飞跃,但使用它时要特别注意安全。一不小心就会在造成漏洞。大名鼎鼎的开源项目 zokrates 在它的入门教程里,就有这样一段描述:
image053.gif
这段描述的核心点是说,攻击者可以基于一个已有的 Groth16 的 proof,生成一个新的且有效的 proof。换句话说,攻击者在不需要获得证明者的 witness,就可以基于证明者已经公开的 proof 构造一个新的 proof。但关于如何构造这样的proof,文中并没有提及。这引起了笔者极大的兴趣,仔细研读 Groth16 的论文,希望可以从中找到蛛丝马迹。

注:G16 只有延展性(malleability)问题,其算法上目前为止并没有发现漏洞。但用 G16 设计系统时,如果不注意 G16 的延展性(malleability)问题,所设计系统就会产生漏洞。

4 攻击思路Attack Idea

通过 zokrates 教程中的描述,我们可以得知,攻击者生成的 proof 一定是基于已有的一个正确的 proof 生成的。那么我们从这一点切入,尝试找到线索。

观察验证等式
image054.jpg
我们可以似乎得出这样一个思路,如果攻击者能够根据已有的 proof π = ([A]₁, [C]₁, [B]₂),构造出一个新的 proof π' = ([A']₁, [C']₁, [B']₂) 使得验证等式
image055.jpg
成立即可。
做一个大胆的尝试,令

image056.jpg
image057.jpg
image058.jpg

则
image059.jpg
image060.jpg
image061.jpg
image062.jpg

得证。
更一般地,挑选一个随机数 η ← ℤₚ,且 η ≠ 0,构造
image063.jpg
都可以使得验证等式
{0, 1},令
image064.jpg
成立。
当然也有其他但构造方法,例如,安比实验室(Secbit) 的 胡宇光 提出了一种更加好的构造方法:挑选一个随机数 x ← ℤₚ,且 x ∉{0, 1},令
image065.jpg
image066.jpg
image067.jpg
这种方式更加简单巧妙且好理解!

5 攻击实践

理论上梳理清楚了,但还需要实践来验证,毕竟理论需联系实际。就地取材,直接用 zokrates 教程中的 “sha256” 例子来做实验。
这个例子是证明者生成 zkSNARK proof 来证明自己知道 sha256 0xc6481e22c5ff4164af680b8cfaa5e8ed3120eeff89c4f307c4a6faaae059ce10 的 pre-image 5。建议先试一下这个例子,之后再往下读。
注,zokrates 默认 proving scheme 就是 groth16,并且基于的椭圆曲线是 alt_bn128 (也被称为 bn256)。

5.1 编译电路

首先,直接使用例子中的电路:
import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> (field):

h = sha256packed([a, b, c, d])
h[0] == 263561599766550617289250058199814760685
h[1] == 65303172752238645975888084098459749904
return 1

将其保存为 hashexample.zok,然后编译
./zokrates compile -i hashexample.zok
编译好的电路,会默认保存在 out 文件中

5.2 初始化

接下来初始化电路,
./zokrates setup
该命令默认会读取 out 文件中的电路,进行初始化,并将 vk 写入 verification.key,将 pk 写入 proving.key。其中 verification.key 中有我们一会要用的 delta (δ)。
笔者本次初始化产生的 verification.key 中的 delta (δ) 是:
...
vk.delta = [0x08d8de30e1b96070599f473822831a5c84675e1ae26d38df88065be710c1ae51, 0x16d8e6761d0e470349897bb92b9a29f50934f76b8208226baef2f107a1914ec4], [0x141806f6a7fc82fbb2b73b544fe06902d2fb0c0ef68531801d92c2937a6d39a3, 0x2587d44143e5ef58550d5691ae14f73ed529cc756b619e4bb10bc7ed02c993a3]
...
注:这个 delta (δ) 表示的是 alt_bn128 ?₂ 上的一个点。alt_bn128 ?₂ 上的每个点的横坐标 x 和纵坐标 y 都是复数(complex number),每个复数又有虚部(imaginary part)和实部(real part)。因此,表示这样的一个点,需要四个值。
然后我们可以直接生成验证 proof 的智能合约代码
./zokrates export-verifier
该命令会根据 verification.key 生成智能合约代码,并保存在 verifier.sol 中。这个智能合约可以直接部署到 Ethererum 上。

5.3 生成证明

接下来我们根据 private input 计算 witness
./zokrates compute-witness -a 0 0 0 5
然后,根据 witness 生成证明
./zokrates generate-proof
proof 会保存在 proof.json 文件中
{

"proof": {
    "a": ["0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035", "0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1"],
    "b": [["0x04567073d4db9932c4e6fec8c5c715bbc7d981bbd2771aba57988bedaf2654f7", "0x1fcbe2f4653402e614d7a5aee078180a6063869c139b352450184015387d0d4f"], ["0x0b6f1e65d68b60e377194800473d1f06498ee37ac14d814732fd9858b1ffa102", "0x03faefb041fee3b4c82eaa96c278c55c09d5937a7101d66bd1dc9e30366e1fba"]],
    "c": ["0x000f6a3ba957a10e387494b36da172de81e71db3fbb3cf131122439c10c3c35e", "0x1ed51ff80897f736c03ac95176e48272c3bb4573262d271aeceaaed89707c428"]
},
"inputs": ["0x0000000000000000000000000000000000000000000000000000000000000001"]

}

5.4 实施攻击

攻击的过程,就是将上述 proof.json 文件中的 b 和 c,分别替换称 b + ηδ 和 c + ηa 替换 c。简单地,我们设 η = 1。
注,这里的 “+” 是椭圆曲线上两个点的加法,不是简单的数字相加。
因此,我们需要写一些代码来完成这个过程。
注:前面提到了 zokrates 使用的是 alt_bn128 这条曲线。我们需要找 alt_bn128 对应的库来帮助我们进行椭圆曲线上点的运算。好消息是以太坊里就有,拿来开箱即用。ethereum/go-ethereum/crypto/bn256/cloudflare
接下来,编写简单的小程序(gen-g16-proof)来根据 [A]₁, [C]₁, [B]₂, [δ]₂ 计算出 [B']₂ = [B + η δ]₂,[C']₁ = [C + η A]₁:
注:上述程序中的 [δ]₂ 来自于 verification.key, [A]₁, [B]₂, [C]₁ 来自于 proof.json。将他们整合为 input.json(参考格式)
执行命令
gen-g16-proof -i input.json -o output.json
后,可在 output.json(参考格式)中获得新的 [B']₂ 和 [C']₁ 值。
注:读者需要根据自己运行时产生的值来替换上述 input.json 中的 delta, a, b, c。并从 output.json 中获取新计算出的 b 和 c。
将 output.json 中 b 和 c 的值替换原 proof.json 中的 b 和 c,另存为 proof2.json (内容如下)。
{

"proof": {
    "a": ["0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035", "0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1"],
    "b": [["0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567", "0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4"], ["0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358", "0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefb"]],
    "c": ["0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537", "0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018c"]
},
"inputs": ["0x0000000000000000000000000000000000000000000000000000000000000001"]

}
接下来根据 proof.json 和 proof2.json 分别生成调用智能合约的参数。这里的 proof2.json 是攻击者基于 proof.json 构造出来的。
$ ./zokrates print-proof -f remix -j proof.json

["0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035","0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1"],[["0x04567073d4db9932c4e6fec8c5c715bbc7d981bbd2771aba57988bedaf2654f7","0x1fcbe2f4653402e614d7a5aee078180a6063869c139b352450184015387d0d4f"],["0x0b6f1e65d68b60e377194800473d1f06498ee37ac14d814732fd9858b1ffa102","0x03faefb041fee3b4c82eaa96c278c55c09d5937a7101d66bd1dc9e30366e1fba"]],["0x000f6a3ba957a10e387494b36da172de81e71db3fbb3cf131122439c10c3c35e","0x1ed51ff80897f736c03ac95176e48272c3bb4573262d271aeceaaed89707c428"],["0x0000000000000000000000000000000000000000000000000000000000000001"]

$ zokrates print-proof -f remix -j proof2.json

["0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035","0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1"],[["0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567","0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4"],["0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358","0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefb"]],["0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537","0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018c"],["0x0000000000000000000000000000000000000000000000000000000000000001"]

最后将刚才在初始化阶段生成的 verifier.sol 部署到以太坊网络,并用上述调用合约的参数调用 verifier.verifyTx() 方法。
以下是笔者在 rinkeby 网络上的测试结果。
• verifier contract: 0x46d6b34c…
• proof.json: 0x728ddfc2…
• proof2.json: 0x91f65d9d…
有兴趣的朋友可以尝试修改 input.json 中的 eta ( η ),构造更多的有效 proof。

6 如何防御

那么如何防御这种攻击方式呢?回想 zokrates 给出的四条建议就很有参考价值:
• signed proofs
要求给出 zkSNARK proof 的同时也给出 proof 的生成者的签名。这样即使有攻击者伪造了 proof,也无法伪造签名。
• nullifiers
可以考虑将 proof 中 public input 的部分或者全部作为 nullifier,由于上述的攻击方式不能更改 public input, 因此限制 nullifier 只能使用一次,可以有效防止这种攻击。
• usage of an Ethereum address as a public input to the program
将提交 proof 的 msg.sender 作为 public input 的一部分,也可以防止种攻击。但这要求电路在设计时就要把这个因素考虑进去。
• usage of non-malleable schemes such as GM17
最后一个方法是换其他 proving scheme。这是显而易见的,但就失去了使用 groth16 算法高效的优势了。

7 总结

Groth16 是非常优秀的 zkSNARK 证明算法。不仅 proof 数据量小,生成 proof 和验证 proof 的速度都有质的提升。 Groth16 技术上已经成熟,已被广泛的应用到各种类型的项目中。Zcash, Filecoin 等明星项目都用到了 Groth16 算法。
但我们在用 Groth16 设计新系统时,需要考虑攻击者可能会利用已公开的 proof 生成新 proof 的情况。因此对于 Groth16,系统设计者不能很草率的拿来就用,而是要考虑具体的业务场景和潜在的攻击模型,采用适当的措施规避缺陷,避免造成漏洞。

参考文献

  1. G16 Paper On the Size of Pairing-based Non-interactive Arguments, Jens Groth.
  2. Zokrates g16 malleability
  3. Zokrates sha256 example
  4. Ethereum bn256 library
  5. gen-g16-proof

评论

暂无评论