零知识证明中的特殊漏洞

零知识（ZK）证明是一种近年来因加密货币应用而受到广泛关注的密码学工具。其核心思想是：持有秘密信息（如加密密钥）的一方能够在不泄露秘密本身的情况下证明关于该知识的某些陈述。目前加密货币使用ZK证明实现匿名性、交易隐私性，以及通过“roll-up”系统提升区块链效率（使用ZK证明将交易批量处理）。ZK证明还被安全研究人员用于证明已知软件漏洞的利用方法而不泄露漏洞细节。

然而，与密码学中大多数技术一样，ZK证明的实现极易出错。本文重点讨论两个存在于专用ZK证明代码中的漏洞，攻击者可利用这些漏洞诱使流行软件接受对不可能陈述的无效证明，包括“证明”对群签名无效输入的有效性，进而导致无效签名。在使用阈值签名的区块链系统（如ThorChain和Binance）中，这可能使攻击者阻止目标交易完成，造成对整条链或特定参与者的拒绝服务攻击。

离散对数证明的背景

一种专用ZK证明是离散对数知识证明。假设Bob向Alice提供RSA模数N = PQ（P和Q为只有Bob知道的大素数），Bob想向Alice证明他知道秘密指数x，使得s ≡ t^x (mod N)。即x是以t为底s的离散对数，且他希望在完全不泄露x的情况下证明自己知道x。

协议流程如下：

1. Bob和Alice商定安全参数k（正整数，决定协议执行次数，通常设k=128）
2. Bob从ZΦ(N)中随机采样ai（i=1,2,…,k），计算对应值αi = t^{ai} mod N，并将α1,α2,…,αk发送给Alice
3. Alice回复随机比特序列c1,c2,…,ck
4. Bob计算zi = ai + ci*x，并将z1,z2,…,zk发送给Alice
5. Alice验证是否对所有i=1,2,…,k满足t^{zi} ≡ αi * s^{ci} mod N。若所有验证通过，则接受证明；否则拒绝。

为何有效

假设Bob不知道x。对每个i，Bob有两种欺骗Alice的方式：预测ci=0或ci=1。

若Bob预测ci=0，他可选择随机ai ∈ ZN并发送αi = t^{ai} mod N。若Alice确实选择ci=0，Bob发送zi=ai，Alice验证t^{zi} ≡ t^{ai} ≡ αi * s^0 ≡ αi mod N并通过该轮证明。但若Alice选择ci=1，Bob需计算zi使得t^{zi} ≡ t^{ai} * s mod N，即需要计算t^{ai}*s的离散对数（等于ai+x），但由于不知道x，无法通过验证。

若Bob预测ci=1，他可选择随机ai ∈ ZN并发送αi = t^{ai} * s^{-1} mod N。若Alice选择ci=1，Bob发送zi=ai，Alice验证t^{zi} ≡ t^{ai}且t^{ai} ≡ αi * s ≡ t^{ai} * s^{-1} * s ≡ t^{ai} mod N并通过该轮。但若Alice选择ci=0，Bob需计算zi使得t^{zi} ≡ t^{ai} * s^{-1} mod N，即需要zi = ai - x，同样因不知道x而失败。

关键在于Bob每次猜测只有50%的正确概率。只要k次猜测中有一次错误，Alice就会拒绝证明。若Alice随机选择ci值，Bob欺骗成功的概率约为1/2^k。通常k=128时，Bob连续中四次Powerball头奖的概率比猜对所有ci值的概率更高。

在非交互式证明中（如下文代码所示），不依赖Alice选择ci值，而是双方计算与证明相关所有值的哈希：c = Hash(N ∥ s ∥ t ∥ α1 ∥ … ∥ αk)，c的比特位用作ci值（称为Fiat-Shamir变换）。虽然Fiat-Shamir变换可能出错并导致严重后果，但本文讨论的漏洞不涉及Fiat-Shamir失败。

代码实现

证明结构和验证代码来自Binance开发的tss-lib库。我们在审查其他软件时发现该代码，Binance团队在收到问题反馈后响应迅速。

Proof结构定义：

1
2
3

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

这是简单结构体，包含两个大整数数组Alpha和T，分别对应数学描述中的αi和zi值。值得注意的是Proof结构未包含模数N或值s和t。

验证函数Verify：

 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的每个比特ci计算： h1^{zi} mod N 和 αi * s^{ci} mod N 若对任意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所有元素为正（即所有zi > 0）
• p.Alpha所有元素设为0（即所有αi = 0）

使用以下参数调用Verify函数：

• N为两大素数乘积
• h1为任意整数（即s无约束）
• h2设为0（即t = 0）

Verify函数检查t^{zi} ≡ αi * s^{ci} mod N。等式右边αi=0迫使αi * s^{ci}=0；左边t^{zi}=0^{zi}=0（因zi>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的两件事：

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

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

密钥生成过程中生成一组“证明参数”，包括半素数模数Ñ（其分解对Alice和Bob未知）以及均与Ñ互质的h1和h2。

Bob首先选择均匀随机值α←$Zq³, β←$Z*N, γ←$Zq³Ñ 和 ρ←$Zq³Ñ。

然后计算： u = h1^α * β^Ñ mod Ѳ v = (Ñ+1)^α * β^Ñ mod Ѳ w = h1^γ * ρ^Ñ mod Ѳ

最后Bob计算Fiat-Shamir挑战值e = Hash(N,Ñ,h1,h2,g,q,R,X,c,u,z,v,w)和挑战响应值： s = r^e * β mod Ñ s1 = e * x + α s2 = e * r + γ

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

Alice收到πPDL后，首先检查s1 ≤ q³；若检查失败则拒绝证明。然后计算： û = h1^{s1} * s^Ñ * z^{-e} mod Ѳ v̂ = (Ñ+1)^{s1} * s^Ñ * c^{-e} mod Ѳ ŵ = h1^{s2} * s2^Ñ * w^{-e} mod Ѳ

最后Alice计算： ê = Hash(N,Ñ,h1,h2,g,q,R,X,c,û,z,v̂,ŵ)

若e ≠ ê，拒绝π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)尝试模N²求c的逆。当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证明的数学描述或甚至编写良好的伪代码，这些约束在何处明确说明？这些文档从数学而非具体角度描述算法。您看到步骤如β←$ZN，后跟v = (N+1)^α * β^N mod N²。从数学角度，理解v在ZN²中，因此v ≠ 0。但从编程角度，没有明确指示存在对v的约束要检查。

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

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