2022黑帽亚洲议题分享——Use Zero to Attack ZKP

渗透技巧 2年前 (2022) admin
451 0 0

  密码学中最有趣的数字是什么,2?不,是0。因为 。对于任意的 ,这个等式都是成立的。在这里,我们将使用 0,去攻击零知识证明(ZPK)。实际上,我们将讨论 ZKP PLONK 的C++实现中的一个关键问题,该是实现存在一个漏洞允许攻击者伪造所有验证器都会接受的证明。我们将展示,理论是如何指导实践的,攻击这颗小石子是如何落入由软件的一系列漏洞产生的裂缝中的。

另外在同一个代码库中,还有一个关于 ECDSA 的bug,其中(r,s)=(0,0)是任意密钥和消息的有效签名,但我们将不再进一步讨论,因为这是我几年前参与的 Google Wycheproof 密码分析项目中已知的 ECDSA 攻击向量。















part 1
 理论如何指导实践 

  在任何一个零知识证明(ZKP)系统中,都存在一个证明者(prover)和一个验证者(verifier),证明者必须向验证者证明他知道某一事实,而验证者需要检查某个等式是否满足。PLONK 使用 polynomial commitment 和 pairing。就本文而言,你不必知道 polynomial commitment 和 pairing,你只需要知道 pairing 能将 这两个点映射到有限域上,以及 是椭圆曲线上的两个基点(base point)。

  另外介绍一个PLONK中的一个符号:,当我们公开 后,如果攻击者无法解决椭圆曲线离散对数问题的话,其仅仅能知道 的值,而 仍然是保密的。然后,攻击者仍然可以 “操纵” ,我们将在攻击中使用这样的一个操作。、

  在PLONK中,验证者需要验证的多项式为

其中2022黑帽亚洲议题分享——Use Zero to Attack ZKP

  上面的式子看着很吓人昂,有这么多的变量,这里我们稍微简化一下,令

  那么等式就是

  现在就变得很简单了,嗯,开个玩笑嘻嘻。

  在处理这种复杂问题时,重要的是找到最弱和最容易攻击的地方。回想一下,我们希望绕过完全验证,即攻击者不知道事实,但希望说服验证者接受他的证明。因此,我们在寻找两件事:

  1. 攻击者可以操纵的变量
  2. 操纵变量最省力的方式

(同时能够通过验证)

这里是一些信息:

  • 可以被攻击者操纵,但是攻击者不知道具体的 的值。
  • ,其中 扮演的是一个预言机的角色,所以显然攻击者不太能操纵
  • 是可信设置的一部分,假设没有人(包括验证人和证明者)知道
  • 是由验证者(不是攻击者)在复杂的多步骤过程中计算的,所以我们忽略它们。

  那么显然, 就是我们操纵的目标了,如果攻击者使用 ,其中 是椭圆曲线中的一个恒等(无穷)点,会发生什么呢?

  • ,与哈希值 无关,看起来有点搞头!

  • ,因为

  • 我们再看看另一边:

因为

因此  ,所以,攻击失败了吗?
















part 2
 为什么我们的攻击得以奏效? 

  幸运的是,我们不是a theoretical cryptographer,我不相信理论安全,至少不完全相信。我相信代码,相信在跑的二进制程序。无论如何,至少程序的输出告诉我,我的想法是对的。当我输入 ,并拿去验证,想看看会发生什么。验证函数计算出 并返回 ,所以攻击成功的绕过了验证,woo-hoo!

  注意,在攻击过程中,攻击者观察到无法解释的行为,这一点都不奇怪。有些时候,我们正是从这些奇怪点切入,从而发现了很多有意思的攻击。后来我们深入发现,这次攻击是由一系列的软件漏洞导致的。
















part 3
 根本原因分析 

  在此之前,我们需要了解一下软件实现的技术细节,就是椭圆曲线中的点通常以3种形式表示:byte array(在内存中),仿射坐标 ,或射影坐标

  回顾一下我们的攻击向量,我们操纵 或者 ,其中 表示仿射坐标 。提醒一下,攻击者不直接控制 ,而是通过操纵 去间接控制。

  1. 验证者第一步首先检查 是否在椭圆曲线上。 并不是椭圆曲线上合法的点,然而验证函数发现了后并没有立刻停止验证。它把这些非法点给移除了,并继续执行。然而,发生了一件神奇的事,当 在一些前面的计算被移除了,却仍在配对计算中使用了,这使得我们的攻击得以奏效。如果验证函数发现非法点后立刻返回false,那么我们的攻击将失败。

  2. 在椭圆曲线的实现代码中,这里有另一个检查,会拒绝无限原点,然而,根据代码, 并不是无限原点,检查是否无限原点的方法是查它最高比特是不是 1,但是 的最高比特是 0,因此 绕过了无限原点的检查,否则,我们的攻击将失败。

  3. 在程序中,有一个方法计算 ,这个方法没有检查到 这个输入,因为它使用费马小定理,即 ,所以 ,所以 就是 下的逆元。然而,当 ,即 的逆元还是 ,在数学上这显然是不对的,因为 不存在逆元。如果这个求逆函数拒绝了 0 作为输入,那么我们的攻击将失败。

  4. 继续,数组 是用射影坐标 表示的。射影坐标是用于优化计算速度的一种中间表示,在计算结束后,射影坐标会使用一种叫做归一化( normalization )的方法去消除 ,(即让 )然后变回放射坐标 ,然而代码中不是对单独一个点进行归一化 ,而是对 一起进行批量归一化 (batch-normalizes),此时, 中的 就会影响到 ,这样有漏洞的代码就会输出 ,即原本非零点的 输出为了 零点。下面是样例

    "Before batch_normalize
    P[0]: { 0x12270675066dbf202e8766f5fa48648f95032fbff46996a08e05e427ed0fffb9,
    0x2cce89ca786bd0a3db55776a24aa3253bce3b8ef689849f93596b5b26afec90f,
    0x04ae1f4cd5f84a484acc4ba115fbd02a879d2e30b8cd97e18f3865887213823b }
    P[1]: { 0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000000 }
    After batch_normalize
    P[0]: { 0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000001 }
    P[1]: { 0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000000,
    0x0000000000000000000000000000000000000000000000000000000000000001 }"

    值得注意的是,在射影坐标中,我们应该拒绝 的点作为合法点,但是代码没有。如果代码拒绝了 出现在射影坐标中,我们的攻击将失败。另外,如果每个点都独立归一化,那么归一化后 将不同于零,我们的攻击将失败。于是验证函数最终计算输出

  5. 最后,在 2 中,   不在曲线上,认为 不是无限原点。在 4 中最后配对函数的计算中认为它是无限原点,因为 。如果同一个输入 在 2 和 4 中没有这样矛盾的处理方式,那么我们的攻击将失败。


原文始发于微信公众号(山石网科安全技术研究院):2022黑帽亚洲议题分享——Use Zero to Attack ZKP

版权声明:admin 发表于 2022年8月29日 上午10:50。
转载请注明:2022黑帽亚洲议题分享——Use Zero to Attack ZKP | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...