零知识证明中的专业漏洞

零知识（ZK）证明是近年来备受关注的密码学工具，尤其在加密货币领域应用广泛。ZK 证明的核心思想是：持有秘密信息（如加密密钥）的一方可以在不泄露秘密本身的情况下，证明关于该秘密的某些陈述。加密货币目前利用 ZK 证明实现匿名性、交易隐私和“汇总”系统，通过批量处理交易提高区块链效率。ZK 证明还被安全研究人员用于证明他们知道如何利用软件漏洞，而无需透露漏洞细节。

然而，与密码学中的大多数事物一样，ZK 证明的实现很难做到完美。本文讨论的是某些专用 ZK 证明代码中的两个漏洞，这些漏洞允许恶意行为者欺骗流行软件接受不可能陈述的无效证明，包括“证明”无效输入对群签名的有效性，进而导致无效签名。在使用阈值签名的区块链系统（如 ThorChain 和 Binance）中，攻击者可以利用此漏洞阻止目标交易完成，造成对整个链或特定参与者的拒绝服务攻击。

离散对数证明的背景

一种专用的 ZK 证明是离散对数知识证明。假设 Bob 向 Alice 提供一个 RSA 模数 N = PQ，其中 P 和 Q 是只有 Bob 知道的大素数，Bob 想向 Alice 证明他知道一个秘密指数 x，使得 s ≡ t^x (mod N)。也就是说，x 是 s 关于底数 t 的离散对数，他希望在不透露任何关于 x 的信息的情况下证明自己知道 x。

协议工作流程如下：

Bob 和 Alice 约定一个安全参数 k，这是一个正整数，决定协议执行的迭代次数。实践中通常设置为 k = 128。
Bob 从 ZΦ(N) 中随机采样 a_i（i=1,2,…,k），计算对应的值 α_i = t^{a_i} (mod N)，并将 α_1,α_2,…,α_k 发送给 Alice。
Alice 回应一串随机位 c_1,c_2,…,c_k。
Bob 计算 z_i = a_i + c_i x，并将 z_1,z_2,…,z_k 发送给 Alice。
Alice 检查对于所有 i = 1,2,…,k，是否满足 t^{z_i} ≡ α_i s^{c_i} (mod N)。如果所有检查通过，她接受证明并确信 Bob 确实知道 x；否则，她拒绝证明——Bob 可能在作弊！

为什么有效

假设 Bob 不知道 x。对于每个 i，Bob 有两种尝试欺骗 Alice 的方式：一种是他认为 Alice 会选择 c_i = 0，另一种是他认为 Alice 会选择 c_i = 1。

如果 Bob 猜测 Alice 将选择 c_i = 0，他可以选择一个随机 a_i ∈ Z_N 并发送 Alice α_i = t^{a_i} mod N。如果 Alice 选择 c_i = 0，Bob 发送 Alice z_i = a_i，Alice 看到 t^{z_i} ≡ t^{a_i} ≡ α_i s^0 ≡ α_i (mod N) 并接受证明的第 i 次迭代。另一方面，如果 Alice 选择 c_i = 1，Bob 需要计算 z_i 使得 t^{z_i} ≡ t^{a_i} s (mod N)，即他需要找到 t^{a_i} s 的离散对数，这等于 a_i + x。然而，Bob 不知道 x，因此无法计算通过 Alice 检查的 z_i。

如果 Bob 猜测 Alice 将选择 c_i = 1，他可以选择一个随机 a_i ∈ Z_N 并发送 Alice α_i = t^{a_i} s^{-1} (mod N)。如果 Alice 选择 c_i = 1，Bob 发送 Alice z_i = a_i。Alice 看到 t^{z_i} ≡ t^{a_i} 且 t^{a_i} ≡ α_i s ≡ t^{a_i} s^{-1} s ≡ t^{a_i} (mod N)，并接受证明的第 i 次迭代。但如果 Alice 选择 c_i = 0，Bob 需要计算 z_i 使得 t^{z_i} ≡ t^{a_i} s^{-1} (mod N)，这将是 z_i = a_i - x。但同样，由于 Bob 不知道 x，他无法计算通过 Alice 检查的 z_i。

关键在于，Bob 的每次猜测只有 50% 的正确概率。如果 Bob 对 Alice 的 c_i 值的任何一次猜测错误，Alice 将拒绝证明。如果 Alice 随机选择她的 c_i 值，Bob 欺骗 Alice 的机会大约是 1/2^k。

通常，Alice 和 Bob 会使用 k = 128 等参数。Bob 连续四次中强力球头奖的机会比正确猜测所有 c_1,c_2,…,c_{128} 的机会更大。

在非交互式证明的情况下，如下文代码所示，我们不依赖 Alice 选择值 c_i。相反，Bob 和 Alice 各自计算与证明相关的所有值的哈希：c = Hash(N ∥ s ∥ t ∥ α_1 ∥ … ∥ α_k)。c 的位被用作 c_i 值。这称为 Fiat-Shamir 变换。当然，Fiat-Shamir 变换可能出错，并带来一些相当严重的后果，但本文讨论的漏洞不涉及 Fiat-Shamir 失败。

代码

我们的证明结构和验证代码来自 Binance 团队编写的 tss-lib。我们在审查其他软件时遇到了这段代码，Binance 团队在我们向他们标记此问题时反应非常迅速。

首先，我们有我们的 Proof 结构：

1
2
3
4
5
6


type (
    Proof struct {
        Alpha,
        T [Iterations]*big.Int
    }
)

这是一个相当直接的结构。我们有两个大整数数组 Alpha 和 T。它们分别对应于上述数学描述中的 α_i 和 z_i 值。值得注意的是，Proof 结构没有包含模数 N 或值 s 和 t。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func (p *Proof) Verify(h1, h2, N *big.Int) bool {
    if p == nil {
        return false
    }
    modN := common.ModInt(N)
    msg := append([]*big.Int{h1, h2, N}, p.Alpha[:]...)
    c := common.SHA512_256i(msg...)
    cIBI := new(big.Int)
    for i := 0; i < Iterations; i++ {
        if p.Alpha[i] == nil || p.T[i] == nil {
            return false
        }
        cI := c.Bit(i)
        cIBI = cIBI.SetInt64(int64(cI))
        h1ExpTi := modN.Exp(h1, p.T[i])
        h2ExpCi := modN.Exp(h2, cIBI)
        alphaIMulH2ExpCi := modN.Mul(p.Alpha[i], h2ExpCi)
        if h1ExpTi.Cmp(alphaIMulH2ExpCi) != 0 {
            return false
        }
    }
    return true
}

这段代码实际上实现了验证算法。参数 h1 和 h2 分别对应于 t 和 s。首先，它计算挑战值 c。然后，对于 c 的每个位 c_i，它计算：如果对于任何 0 < i ≤ k，h1ExpTi ≠ alphaIMulH2ExpCi，则证明被拒绝。否则，它被接受。

问题

需要注意的是，Verify 函数没有进行任何类型的检查来验证 h1、h2 或 p.Alpha 或 p.T 的任何元素。缺乏有效性检查意味着我们可以触发各种有趣的边缘情况。特别是，当涉及对数和指数关系时，注意零很重要。回想一下，对于任何 x ≠ 0，我们有 0^x = 0。此外，对于任何 x，我们有 0 ∙ x = 0。我们将利用这些事实来强制等式检查 h1ExpTi = alphaIMulH2ExpCi 始终通过。

第一个不可能的事情：基数为 0 的离散对数

假设 Bob 创建一个 Proof 结构 p，具有以下值：

p.T 的所有元素都是正数（即所有 i 的 z_i > 0）
p.Alpha 的所有元素设置为 0（即所有 i 的 α_i = 0）

现在考虑使用以下参数调用 Verify 函数：

N 是两个大素数的乘积
h1 设置为任何整数（即 s 无约束）
h2 设置为 0（即 t = 0）

Verify 函数将检查 t^{z_i} ≡ α_i s^{c_i} (mod N)。在关系的右侧，α_i = 0 强制 α_i s^{c_i} = 0。在方程的左侧，t^{z_i} = 0^{z_i} = 0，因为 z_i > 0。因此，Verify 函数看到 0 = 0，并接受证明有效。回想一下，该证明旨在证明 Bob 知道 s 关于 t 的离散对数。在这种情况下，验证器例程将相信 Bob 知道一个整数 x，使得对于任何 s，s ≡ 0^x (mod N)。但如果 s ∉ {0,1}，这是不可能的！

修复

防止此问题很简单：验证 h2 和 p.Alpha 的所有元素都是非零的。作为实践，验证另一方提供的所有密码学值是一个好主意，确保例如椭圆曲线点位于曲线上，整数落在其适当区间内并满足任何乘法性质。对于此证明，此类验证将包括检查 h1、h2 和 p.Alpha 是非零的，与 N 互质，并落在区间 [1,N) 内。确保 N 通过一些基本检查（如位长度检查）也是一个好主意。

加密离散对数的证明

在某些阈值签名协议中，签名过程的一个步骤涉及同时证明关于 Bob 知道的秘密整数 x 的两件事：

X = R^x，其中 X 和 R 在一个阶为 q 的群 G 中（通常，G 是某个模数的乘法整数群，或椭圆曲线群）
密文 c = PaillierEnc_N(x,r) 对于某个随机化值 r ∈ Z*_N 和 Bob 的公钥 N。即 c = (N + 1)^x r^N (mod N^2)。

（为了清晰起见：G 通常与一个最大阶群生成器 g ∈ G 一起指定。它不直接在协议中使用，但会集成到哈希计算中——它不影响证明，所以不用太担心。）

证明密文 c 和 X 的离散对数之间的一致性，确保 Bob 对椭圆曲线签名的贡献与他之前在协议中贡献的值相同。这防止 Bob 贡献导致无效签名的虚假 X 值。

作为密钥生成的一部分，生成一组“证明参数”，包括一个半素数模数 Ñ（其因式分解对 Alice 和 Bob 未知），以及 h1 和 h2，两者都与 Ñ 互质。

Bob 首先选择均匀随机值 α←$Z_{q^3}, β←$Z*N, γ←$Z{q^3Ñ} 和 ρ←$Z_{q^3Ñ}。

Bob 然后计算：最后，Bob 计算一个 Fiat-Shamir 挑战值 e = Hash(N,Ñ,h1,h2,g,q,R,X,c,u,z,v,w) 和挑战响应值：

注意 s1 和 s2 不是模任何值计算的，而是在整数上计算的。Bob 然后发送 Alice 证明 π_{PDL} = [z,e,s,s1,s2]。

Alice 在收到 π_{PDL} 后，首先检查 s1 ≤ q^3；如果此检查失败，她拒绝证明无效。然后她计算：最后，Alice 计算：如果 e ≠ ê，她拒绝 π_{PDL} 无效。否则，她接受 π_{PDL} 有效。

为什么有效

首先，确保有效证明将验证：因为 û, v̂ 和 ŵ 分别匹配 u, v 和 w，我们将有 ê = e，证明将验证。

要了解如何防止 Bob 作弊，请阅读这篇论文和这篇论文的第 6 节。

代码

以下代码取自 kryptology 库的 Paillier 离散对数证明实现。具体来说，以下代码用于计算 v̂：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func (p PdlProof) vHatConstruct(pv *PdlVerifyParams) (*big.Int, error) {
    // 5. \hat{v} = s^N . (N + 1)^s_1 . c^-e mod N^2

    // s^N . (N + 1)^s_1 mod N^2
    pedersenInc, err := inc(p.s1, p.s, pv.Pk.N)
    if err != nil {
        return nil, err
    }

    cInv, err := crypto.Inv(pv.C, pv.Pk.N2)
    if err != nil {
        return nil, err
    }
    cInvToE := new(big.Int).Exp(cInv, p.e, pv.Pk.N2)
    vHat, err := crypto.Mul(pedersenInc, cInvToE, pv.Pk.N2)
    if err != nil {
        return nil, err
    }
    return vHat, nil
}

调用函数 Verify 使用 vHatConstruct 计算上述描述的 v̂ 值。在有效证明中，一切应该正常工作。

问题

在无效证明中，事情并不顺利。特别是，Bob 可能设置 v = s = 0。当这种情况发生时，c 的值无关紧要：Alice 最终检查 v̂ = 0^N ∙ (N+1)^{s1} ∙ c^{-e} = 0 = v，并接受结果。

第二个不可能的事情：任意密文

通过利用 v̂ = s = 0 问题，Bob 可以证明他知道 x 使得 X = R^x，但同时向 Alice“证明”任何 c ≠ 0 的值都是 x 的有效密文。Bob 甚至不需要知道 N 的因式分解。再次，Bob“证明”了不可能的事情！

这种伪造具有真实的安全影响。特别是，能够伪造此证明允许 Bob 破坏阈值签名协议而不被检测。在某些系统中，这可用于阻止有效交易执行。

值得注意的是：c = 0 的特定情况将被检测为错误。行 cInv, err := crypto.Inv(pv.C, pv.Pk.N2) 尝试对 c 模 N^2 求逆。当 c = 0 时，此函数将返回错误，导致 vHatConstruct 函数依次返回错误。

修复

再次，这可以通过更好的输入验证来防止。证明的基本验证将涉及检查 z 和 s 在 Z*_N 中。即，检查 gcd(z,N) = gcd(s,N) = 1，这强制 z ≠ 0 和 s ≠ 0。此外，应该有检查确保 s1 ≠ 0 和 s2 ≠ 0。

风险和披露

风险

这些漏洞在实现 GG20 阈值签名方案的存储库中发现。如果攻击者利用密文可塑性漏洞，他们可以“证明”无效输入对群签名的有效性，导致无效签名。如果特定区块链依赖阈值签名，这可能允许攻击者阻止目标交易完成。

披露

我们已向 Binance 报告了 tss-lib 的问题，他们迅速修复了问题。我们还联系了众多依赖 tss-lib（或更常见的是 tss-lib 的分支）的项目。这包括 ThorChain，他们也修复了代码；Joltify 和 SwipeChain 直接依赖 ThorChain 分支。此外，Keep Networks 维护他们自己的 tss-lib 分支；他们已集成修复。

kryptology 的问题已向 Coinbase 报告。GitHub 上的 kryptology 项目此后已被归档。我们未能识别任何当前依赖该库阈值签名实现的项目。

故事的寓意

最终，这是一个密码学失败，源于完全可以理解的数据验证疏忽。另一方提供的值应始终在使用前根据所有适用约束进行检查。哎呀，从另一方提供的值计算出的值应始终根据所有适用约束进行检查。

但如果你查看这些 ZK 证明的数学描述，甚至编写良好的伪代码，这些约束在哪里明确说明？这些文档从数学角度描述算法，而不是具体实现。你看到诸如 β←$Z*N 的步骤，随后是 v = (N + 1)^α β^N (mod N^2)。从数学角度来看，理解 v 在 Z*{N^2} 中，因此 v ≠ 0。但从编程角度来看，没有明确指示存在对 v 的约束要检查。

Trail of Bits 在 zkdocs.com 维护一个 ZK 证明系统资源指南。这类问题是我们提供此类指南的主要动机之一——将数学和理论描述转化为软件是一个困难的过程。诚然，我们的一些描述可以更清楚地解释这些检查；我们希望在下一次发布中修复这一点。

Trail of Bits 喜欢向审计员和密码学家提供的一条指导是注意两个特殊值：0 和 1（以及它们的类似物，如无穷远点）。与 0 或其类似物相关的漏洞在过去曾引起问题（例如，这里和这里）。在这种情况下，未能检查 0 导致两个独立的漏洞，允许阈值签名方案中的攻击者将诚实方引入歧途。

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

页面内容离散对数证明的背景为什么有效代码问题第一个不可能的事情：基数为 0 的离散对数修复加密离散对数的证明为什么有效代码问题第二个不可能的事情：任意密文修复风险和披露风险披露故事的寓意最近文章非传统创新者奖学金劫持你的 PajaMAS 中的多代理系统我们构建了 MCP 一直需要的安全层利用废弃硬件中的零日漏洞 Inside EthCC[8]：成为智能合约审计员 © 2025 Trail of Bits。