打破阈值签名方案中的共享密钥 - Trail of Bits博客
Fredrik Dahlgren
2024年2月20日
密码学, 漏洞披露
今天我们披露一个拒绝服务漏洞，该漏洞影响基于Frost、DMZ21、GG20和GG18协议的多个阈值签名方案实现中的Pedersen分布式密钥生成（DKG）阶段。该漏洞允许单个恶意参与者秘密提高重构共享密钥所需的阈值，可能导致使用共享密钥生成的签名无效。
我们最初在去年与Chainflip的客户合作中意识到这个漏洞。在审查Chainflip的Frost阈值签名方案实现时，我们注意到它做了一些不寻常的事情——这是我们以前从未见过的。通常，这类观察表明代码库中存在弱点或漏洞，但在这种情况下，Chainflip的防御性编码实践实际上保护了其实现免受漏洞影响。通过格外谨慎，Chainflip还避免了在代码库中引入可能被单方利用来破坏协议密钥生成阶段创建的共享密钥的漏洞。当我们意识到这一点时，我们开始好奇其他实现是否容易受到这个问题的影响。这开始了一项长期调查，最终导致了十次独立的漏洞披露。
什么是Pedersen DKG协议？
该漏洞实际上很容易理解，但为了能够解释它，我们需要了解Pedersen DKG协议背后的一些数学细节。别担心——如果你理解什么是多项式，你应该没问题，如果你以前听说过Shamir的秘密共享，你已经大部分理解了。
Pedersen DKG协议基于Feldman的可验证秘密共享（VSS）方案，这是Shamir秘密共享方案的扩展。Shamir的方案允许n方共享一个密钥，然后可以由t+1方重构。（这里，我们假设组已经以某种方式事先商定了阈值t和组大小n。）Shamir的方案假设一个可信的经销商，不适合参与者可能被破坏并恶意行动的多方计算方案。这就是Feldman的VSS方案的用武之地。它建立在Shamir的方案之上，允许参与者验证共享是否诚实生成。
设G是一个离散对数问题困难的交换群，设g是G的生成元。在(t, n)-Feldman VSS上下文中，经销商生成一个随机t次多项式p(x) = a0 + a1 x + … + at xt，其中a0表示要共享的原始秘密。然后她计算各个秘密共享为s1 = p(1), s2 = p(2), …, sn = p(n)。这部分与Shamir的方案完全相同。为了允许其他参与者验证他们的秘密共享，经销商发布值A0 = ga0, A1 = ga1, …, At = gat。然后参与者可以使用系数承诺（A0, Ai, …, At）通过以下方式“在指数中”重新计算p(i)来验证他们的秘密共享si：
计算V = gp(i) = g s i。
计算V’ = gp(i) = ga0 + a1 i + … + at i t = ∏k (gak) i k = ∏k Aki k。
检查V = V’。
与Shamir的秘密共享一样，秘密s = a0可以使用拉格朗日插值通过t+1个共享恢复。
在Feldman的VSS方案中，共享秘密对经销商是已知的。为了生成协议所有参与者未知的共享密钥，Pedersen DKG协议基本上并行运行n个Feldman的VSS方案实例。结果是一个(t, n)-Shamir秘密共享一个所有参与者未知的值：每个参与者Pi首先生成一个随机t次多项式pi(x) = ai,0 + ai,1 x + … + ai,t xt。她发布系数承诺（Ai,0 = gai,0, Ai,1 = gai,1, …, Ai,t = gai,t），然后将秘密共享si, j = pi(j)发送给Pj。（注意索引j必须从1开始，否则Pi最终会泄露她的秘密值ai,0 = pi(0)。）Pj可以通过计算V和V’并检查它们是否一致来验证秘密共享si, j是否正确计算。为了获得他们的秘密共享sj，每个参与者Pj只需将从其他参与者获得的秘密共享相加。也就是说，他们计算他们的秘密共享为
sj = s1, j + s2, j + … + sn, j = p1(j) + p2(j) + … + pn(j)
注意，如果我们定义p(x)为多项式p(x) = p1(x) + p2(x) + … + pn(x)，很容易看出我们最终得到的是p(x)常数项的Shamir秘密共享，s = p(0) = a1, 0 + a2, 0 + … + an, 0。由于每个多项式pi(x)的次数是t，p(x)的次数也是t，我们可以像以前一样使用拉格朗日插值通过t+1个共享恢复秘密s。
（在实现Pedersen DKG协议时还需要考虑一些其他因素，但它们与此无关。有关更多细节，请参阅引言部分链接的任何论文。）
在Pedersen DKG中移动球门柱
现在，我们准备回到开始这一切的与Chainflip的合作。在审查Chainflip的Frost签名方案实现时，我们注意到该实现正在对最高系数的承诺A1,t + A1,t + … + An,t求和，并检查结果是否等于G中的单位元，这意味着结果多项式p(x)的最高系数为0。这显然是不可取的，因为它将允许少于t+1的参与者恢复共享密钥，但发生这种情况的概率在密码学上可以忽略不计（即使有主动恶意参与者）。通过检查，Chainflip将此概率降低到0。
这让我们想知道，如果参与者在Pedersen DKG协议中使用次数不同于t的多项式pi(x)会发生什么？特别是，如果参与者使用次数T大于t的多项式pi(x)会发生什么？由于p(x)等于和p1(x) + p2(x) + … + pn(x)，p(x)的次数将是T而不是t，这意味着签名协议将需要T+1而不是t+1参与者才能成功完成。如果其他参与者未检测到此更改，它将允许任何参与者通过选择严格大于参与者总数的阈值来秘密使共享密钥无法使用。如果DKG协议用于生成作为阈值签名方案（如引言中引用的方案之一）一部分的共享密钥，任何使用t+1参与者签署消息的尝试都将失败。根据实现，这还可能导致系统在检测到故障时将恶意行为错误地归因于诚实参与者。更严重的是，这种攻击还可用于在大多数基于Feldman的VSS的密钥重新共享方案中使共享密钥无法使用和不可恢复。这包括CGGMP21和Lindell22早期版本中描述的密钥重新共享方案。在这种情况下，共享密钥可能已经控制大量资金或代币，这些资金或代币将不可逆转地丢失。
显然，这种类型的恶意行为可以通过简单地检查每个参与者发布的系数承诺向量（Ai,0, Ai,1, …, Ai,T）的长度并在发现任何长度与t+1不同时中止来防止。事实证明，Chainflip已经检查了这一点，但我们好奇其他实现是否也这样做了。总之，我们发现了十个实现容易受到这种攻击，因为它们允许单个参与者在未被检测的情况下提高使用Pedersen DKG生成的共享密钥的阈值。（我们没有发现任何易受攻击的密钥重新共享方案实现。）
披露过程
我们于2024年1月3日联系了以下易受攻击代码库的维护者：
- Chelsea Komlo维护的Frost参考实现
- ZCash Foundation的Frost实现
- Penumbra在decaf377上的Frost实现
- Isis Lovecruft维护的Frost-Dalek
- Toposware的ICE-FROST实现
- Trust Machines基于Frost的WSTS实现
- Jesse Possner维护的FROST-BIP340
- ZenGo-X的GG18和GG20实现
- Safeheron的GG20实现
- LatticeX的GG20 Open TSS实现
七位维护者回应确认他们已收到披露。其中四位维护者（Chelsea Komlo、Jesse Possner、Safeheron和ZCash Foundation）还报告说他们已经或计划解决此问题。
我们于2024年2月7日再次联系了三位未回应的维护者（Toposware、Trust Machines和LatticeX）。此后，Toposware也回应确认他们已收到我们的披露。