Announcements

Zerocoin漏洞的密码学描述

By 四月 30, 2019 No Comments

(由于翻译者密码学知识有限,本文难免存在较多表达错误,请学术研究者参考英文原文

我们在几天前披露了Zcoin发现的Zerocoin漏洞,据我们所知,迄今为止实施了Zerocoin的所有主要项目都已使用sporks来禁用Zerocoin或推出了一个紧急补丁来禁用Zerocoin,因此此漏洞暂时不会困扰他们。

我们正在发布这些信息,以帮助那些希望探索修补Zerocoin的人,同时也让各项目方能够确定他们是否已成为此次攻击的目标。

密码学缺陷描述

要取回Zerocoin,您需要执行以下操作:

1.铸造铸币的公共价值`C = g ^ S * h ^ r(mod p)`并且在不同的组(“C1”和“C2”)下对“C”做出两个Pedersen承诺。

2.`P1` = ZK证明`C1`和’C2`是对相同值的承诺而没有透露有问题的值。

3.`P2` = ZK证明`C2`被提交给RSA累加器中包含的值。

4.`P3` = ZK证明`C1`承诺的值本身就是对序列`S`的承诺。

5.输出`S`,`C1`,`C2`,`P1`,`P2`,`P3`。

6.对于证明创作值,使用“r”,“C”,“w”(见证)但未公开。证据与公开的“A”(取回时的累加值)相关联。

这里的薄弱环节是’P1`证明。尽管它是Zerocoin协议的一个重要的加密构建块,但它的描述甚至存在都从所有论文中省略,但它自libzerocoin开始以来就在libzerocoin的源代码中进行了描述。

它运行在两组:{generators`g1`,`h1`,modulus`p1`,order`G1`}和{`g2`,`h2`,`p2`,`G2`}。这个结构应该证明两个承诺“A = g1 ^ F1 * h1 ^ R1(mod p1)”和“B = g2 ^ F2 * h2 ^ R2(mod p2)”被赋予相同的值,即`F1 = F2 = m`。

创建证明:

1.创建`r1`,`r2`,`r3`  – 比组顺序和模数大得多的随机值。

2.创建两个帮助器承诺`T1 = g1 ^ r1 * h1 ^ r2(mod p1)`和`T2 = g2 ^ r1 * h2 ^ r3(mod p2)`。

3.计算`challenge = Hash(A || B || T1 || T2)`。

4.`S1 = r1 +(m * challenge)`,`S2 = r2 +(R1 * challenge)`,`S3 = r3 +(R2 * challenge)`其中`m`是共同承诺值和`R1`, `R2`是承诺的秘密价值。

5.输出`S1`,`S2`,`S3`,`challenge`作为证据。

验证:

6.计算`T1 = g1 ^ S1 * h1 ^ S2 * A ^( – 挑战)(mod p1)`和`T2 = g2 ^ S1 * h2 ^ S3 * B ^( – 挑战)(mod p2)`。

7.`hash =哈希(A || B || T1 || T2)`。

8.将`hash`与`challenge`进行比较。

这里的问题是步骤4中使用的“m”可能比较大,但我们的组订单较小。所以我们可以选择满足以下条件的`F`的值:

`F = F1(mod G1)`

`F = F2(mod G2)`

并在步骤4中将其用作“m”。然后,即使对不同的值做出两个承诺,证据仍将验证。

现在伪造一个硬币攻击者从合法铸造的硬币中创建“P2”证明,然后用不同的序列从书上掏出一枚新硬币并用它来创建“P3”证明。然后伪造“P1”以证明“P2”和“P3”指的是同一枚硬币,即使它们没有。

总结一下:攻击者至少需要一枚真正的硬币,但他可以根据自己的需要创造尽可能多的支出。这些假取回与真正取回无法区分。

如何确定您的区块链是否被被攻击过

尽管使用上述攻击可以使虚假取回与真实取回无法区分,但在这种情况下,攻击者的取回具有唯一的指纹,其中S1大小超过1808位,因此我们能够评估最大伤害。

同样,我们希望强调可以在不留指纹的情况下完成此攻击。

解决方案的探讨[不经过进一步分析前请勿使用]

我们在下面提出的解决方法是依据推理提出的可能解决方案,未接收过任何形式的密码分析。它仅仅是为了激发那些希望探索修复Zerocoin的人的讨论。使用它前请务必严格审查,我们认为更好的解决方法是用新方案完全取代P1阶段的证明。我们不对此修复提供任何承诺。

首先让我们修改攻击,使其更强大。而不是使用`F`我们使用具有以下属性的`F’:

`F’= F1 *挑战(mod G1)`

`F’= F2 *挑战(mod G2)`

然后计算“S1 = r1 + F”。您可以使用中国剩余定理计算“F”,并且“F”的位大小是两个组顺序的位大小的总和:`bitsize(F’)= bitsize(G1)+ bitsize(G2)`。通过使用强力直到“F”中所需的前导位数变为零,可以进一步降低“F”的位大小。 “S1”的最小可能位大小与“F”相同。

使这种攻击成为可能的原因是`bitsize(F’)`小于允许的位大小`S1`。 `r1`中的位数使用以下公式计算:

`bitsize(r1)= bitsize(max(p1,p2,G1,G2))+ bitsize(challenge)+ K`

其中`K`是安全参数(`libzerocoin`中的512),用于掩盖`S1`的非均匀分布,从而使证明零知识。同样在当前的实现中,验证允许`S1`的位大小比`r1`(100000+位)大64倍。

解决问题的建议方法是只允许“S1”中的绝对最小位。首先,没有必要让`r1`和组模数一样大,组顺序就足够了。接下来我们可以将参数“K”降低到几位。最后,我们可以减少散列函数中的位数以减少挑战大小。这带给我们的是:

`bitsize(r1)= bitsize(max(G1,G2))+ bitsize(challenge)+ K`

为了安全起见,它必须比攻击中使用的“F”大小小得多(至少128位,更接近256):

`max(bitsize(G1),bitsize(G2))+ bitsize(challenge)+ K <bitsize(G1)+ bitsize(G2)

使用当前参数,它是不可能实现的,因为组命令的大小为1024和257位,并且挑战是256位长。只有当我们改变参数使得组顺序“G2”大得多且接近512位时才有可能。或者,我们可以将“challenge”中的位数减少到128,尽管这是一个更糟糕的解决方案。并且`K`应该在16-32的范围。

可以将“S2”和“S3”的大小分别缩小为“bitsize(G1)+ bitsize(challenge)+ K”和“bitsize(G2)+ bitsize(challenge)+ K”。