GG18/GG20 协议安全漏洞分析
2023-08-14
最后更新于
2023-08-14
最后更新于
By Max
近期，Fireblocks 团队披露了 GG18、GG20 、Lindel 17 MPC 协议中的 0-day 漏洞，该漏洞允许攻击者提取一组 MPC 私钥分片背后的真实密钥。
在披露该问题前，Fireblocks 团队与 Safeheron 取得联系并展开积极沟通。Safeheron 开源的 GG18/GG20 MPC 协议严格按照论文内容实现，如果使用此版本的开源算法则可能受到类似攻击。在漏洞披露前，Safeheron 已经修复了开源项目中存在的漏洞，Fireblocks 团队也协助确认了补丁的生效。
Fireblocks 团队采用 Safeheron 的基于 C++ 实现的开源 GG18/GG20 协议构造了 POC， 以演示并帮助社区理解该漏洞。
Safeheron 商业版服务中的 GG18/GG20 MPC 协议额外引入了 CMP20/CGGMP21 中的相关零知识证明，因此不受该漏洞影响。
本文重点关注漏洞针对 GG18 和 GG20 的影响。针对 GG18/GG20 协议，攻击方通过构造特殊的 Paillier 密钥，从而在 MPC 签名阶段完成攻击，通过有限次的签名，攻击方可以解析出其它各参与方的私钥分片。
此次漏洞的影响范围比较广泛，由于影响到了 MPC 协议的安全假设，因此几乎所有主流的开源 GG18/GG20 协议实现都受到该漏洞的影响。
如何攻击 MPC 协议呢？常见的 MPC 协议在安全假设前提下是可证明安全的，因此针对 MPC 协议的攻击常常聚焦于协议依赖的安全假设。安全假设就好比是 MPC 协议大厦的地基，如果安全假设不成立了，那么整个 MPC 的协议都将会受到影响。
整个攻击的核心逻辑如下：
（1）在 KeyGen 子协议阶段，攻击方构造不安全的同态密钥。
（2）在 Sign 子协议阶段：
（b）利用不安全的同态密钥的特性，构造恶意的零知识证明，从而完成对其他参与方的欺骗，通过验证；
（3）重复若干次 Sign 子协议，基于中国剩余定理计算出对方私钥分片。
本节我们详细介绍攻击的细节。在通用的 MPC 门限多签场景中存在多个参与方，这些参与方两两之间可以发起攻击，而且攻击方式完全相同。
首次攻击发生在 KeyGen 子协议的执行过程中，我们可以称其为攻击准备阶段。在攻击准备阶段，攻击方 Party A 成功构造了不安全的 Paillier 同态密钥。
正常构造同态密钥的过程如下：
计算
攻击方 Party A 构造同态密钥的过程如下：
计算
注意，攻击需要成功执行 16 次 Sign 子协议，不妨假设当前是执行第 $i$ 次 Sign 子协议。
正常的计算过程如下：
后续正常完成 MPC Sign 子协议
攻击者的计算过程如下：
构造恶意的零知识证明，实施欺骗
后续正常完成 MPC Sign 子协议
接下来介绍其具体操作方式。
Witness：$k_A' = 0 \ne k_A$，其它随机数
注意，以上是一个非法的 Statement，因为：
正常情况下，GG18 协议中此处的 Range Proof 是完全有效的，攻击者难以构造零知识证明使得该 Statement 通过验证。
GG18/GG20 协议中的零知识证协议描述如下：
在 Verfier 的验证过程中，最重要的就是满足对密文约束的恒等式（红框部分）：
可知:
在运行 16 次成功的 MPC Sign 子协议以后，得到
GG18 论文有两个实现版本，修正版和老版，针对不同版本的攻击效果有所区别。
注意：在 GG18 修正版论文中作者提供了很多安全修改建议，因此在实现该 MPC 协议时应基于修正版实现。
上述章节描述了该漏洞的原理和算法层面的攻击方式，那么针对真实的基于 MPC 的自托管钱包应用场景，如果使用的 MPC 协议存在该漏洞，应该如何完成攻击呢？
该漏洞影响 t/n 门限，为方便理解，我们假设 MPC Wallet 的参与方为 2 方 Party A 和 Party B，签名的门限为 2/2，其中 Party A 对应的私钥分片由用户持有，通过钱包提供方提供的手机 App 管理和使用；Party B 对应的私钥分片由钱包提供方持有，并且在云端存储和使用。
如果要完成攻击，攻击者必须具备以下能力：
（1）掌握钱包提供方创建钱包和发起交易的实现逻辑和机制
（2）能够模拟钱包提供方 App 使用 MPC 协议完成创建钱包以及签名交易
那么攻击者便可以发起攻击：
在上述攻击场景中，如果要攻击该钱包必须在创建钱包时就已经启动了攻击，并且通过使用该钱包签名多次完成攻击，最终获得该钱包的私钥。
修复漏洞需要添加两个零知识证明：
Safeheron 已经修复了开源算法中的该漏洞，具体修复方式可参考：
Safeheron 提供了大整数分解工具可以快速进行批量检测，关于大整数分解相关的算法原理可以参考大整数分解算法与实践。
理清此漏洞的原理与攻击方法后，我们不难看出，此漏洞的利用门槛相对较高，但身处安全行业，面对充满未知与挑战的黑森林，我们始终需要对安全保持敬畏之心。
Fireblocks 团队的负责任安全披露彰显了「安全从来都不是孤军奋战」，Safeheron 同样坚持开源透明、以技术为重，能参与到此次安全披露中深感荣幸。Safeheron 后续会联合安全合作伙伴 SlowMist 协助行业内其他厂商修复该漏洞，以确保用户资产安全。
实现行业安全，需要每一家厂商、每一位安全从业人员、每一位用户的关注与努力，望与行业共勉。
[1] Fireblocks: Practical Key-Extraction Attacks in Leading MPC Wallets
[2] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup
[3] GG20: One Round Threshold ECDSA with Identifiable Abort
[4] CGGMP21: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
以 GG18/GG20 为例，该 MPC 协议依赖于 Paillier 同态加密算法的安全性。 Paillier 同态加密算法基于复合剩余类的困难问题设计，是一种广泛使用的且满足加法运算的同态加密算法。此次的漏洞就是针对 Paillier 同态密钥的构造入手，步步递进，攻陷了 协议和相关零知识证明协议，最终形成了有效的攻击。
（a）在两两运行的 协议中，比如 和 协议，攻击方基于自身不安全的同态密钥，构造非法的 值；
（c）攻击方与被攻击方完成签名，并记录下过程中的 。
为了方便介绍攻击方法，这里不妨假设 MPC 钱包由三方 Party A、Party B 和 Party C 共同创建和使用，每一方分别管理各自的私钥分片 、 和 。利用该漏洞，Party A 可以攻击 Party B 和 Party C 以获取对方的私钥分片。本节我们以「Party A 试图攻击 Party B」为例，介绍如何提取 Party B 的私钥分片 。(Party A 可以同样的方式提取 Party C 的私钥分片 ，此处不再赘述。)
随机选择安全素数
随机选择素数 ，其中 是互不相同的小素数，而 是大素数
， 的长度为 2048 bit
我们可以发现，攻击方 Party A 构造的 Paillier 公钥 包含大量的小因子，那么攻击方 Party A 构造的非法 Paillier 密钥能骗过 Party B 吗？毕竟这里需要构造零知识证明供 Party B 验证。
仔细观察上图所示的 GG18/GG20 中的 协议可以发现，这里只要求提供 零知识证明。由于攻击者构造的 Paillier 同态公钥 只包含了互不相同的素因子，因此，该构造方法显然能通过 零知识证明。
在 Sign 子协议中，前几轮需要运行 协议，参考 GG18 4.2节。
随机选择
计算
执行 协议
生成关于随机数 的密文 的零知识证明。参考 GG18 A.1 节 Range Proof
构造特殊的 值
使用特殊构造的 值，正常执行 协议
攻击者不使用随机值，而是在第 $i$ 次 MPC Sign 子协议中，采用如下方式构造 。
注意，该特殊构造的 ，正常情况下已经无法通过预期零知识证明。其中 为椭圆曲线的阶。
GG18 协议要求攻击者在 运行阶段提供有效的零知识证明，参考 GG18 A.1节 Range Proof。该零知识证明能证明:
Statement： $Enc_{N_A}(k_A)$ 对 的加密密文，且满足
不是 的加密密文
那么，攻击方 Party A 如何突破阻碍呢？这时就需要利用攻击方 Party A 在 KeyGen 协议阶段构造的不安全的 Paillier 密钥 了。因为有了不安全的 Paillier 密钥，所以才能有机会构造恶意的零知识证明。
攻击技巧是构造合理的挑战值 ，满足：
由于 ,
这里将 「变换」成了 的密文，从而成功构造了零知识证明。
注意，这里可以通过在构造过程中暴力迭代 ，不断加 1，并更新 ，从而满足 。由于模数 $p_i$ 为小素数，因此完全可以暴力迭代成功。
攻击方与被攻击者完成 Sign 子协议，并额外记录下 协议中的 值。
考虑最新版的 论文，已知 ，
记
注意到等式右边全都是攻击方已知的参数，因此攻击方可以计算出
从而得到：
由于 ，根据中国剩余定理，攻击方 Party A 可以计算出 Party B 的私钥分片 。攻击成功。
修正版论文中 协议使用的 （对应前文的 ），采用上述攻击方法，需要 16 次签名，攻击方就可以解析出被攻击方的私钥分片。
老版论文中 协议使用的 （对应前文的 ），需要采用上述攻击方法的变型来实施攻击，此处不做额外说明。因为需要大量的猜测运行，需要进行大量的签名，至少需要进行 10^6 量级的签名尝试，攻击方才可能解析出被攻击方的私钥分片。更准确的说，为了以概率 成功提取对方私钥分片所需签名次数是： 次。
其中，。Fireblocks 的论文中相应的公式有个书写错误，在此进行了修正。
（1）模拟 App 创建钱包，在创建钱包时（对应 KeyGen 子协议），构造本地 Party A MPC 协议中不安全的同态密钥，然后使用该同态密钥完成钱包创建，同时获取本地 Party A 私钥分片
（2）模拟 App 使用该钱包正常发起交易签名 16 次（对应 Sign 子协议），并且每次构造 MPC 协议中恶意的 和恶意的零知识证明，完成 16 次签名并收集每次签名中的
完成上述操作后，攻击者就可以获取所创建钱包对应的云端 Party B 的私钥分片 。因为签名门限为 2/2，攻击者从本地获取了私钥分片 ，同时又攻击协议获得了云端私钥分片 ，至此攻击者可以通过 和 得到钱包对应的真实私钥 。
通观整个攻击过程，我们发现所有的攻击都起源于攻击准备阶段，在该阶段攻击方 Party A 构造了不安全的同态密钥 ，其中包含了大量的小因子，这些都促成了后续的攻击达成 。
漏洞修复也正是针对这一点， 在 GG18/GG20 协议中，添加额外的零知识证明，避免同态公钥 中小因子的出现，从根源上阻止了攻击。从整个 GG18/GG20 协议来说，打完该补丁以后，安全假设就不存在安全问题了，因此协议仍然是安全的。
第一个零知识证明是 Paillier 的 Blum 模数证明，它保证了同态公钥 最多只有两个素因子，且每个素因子满足特定特性。
第二个零知识证明是无小因子证明，保证了同态公钥 中没有小的素因子。
这两个零知识证明实现可以参考 CMP20 和 CGGMP21（6.3 节 和 C.5 节)，该证明可保证Paillier 公钥 不存在小于 的因子。
在完成 MPC 协议安全升级之后，为了安全起见，可以检测历史数据进行验证是否曾经受到针对该漏洞的攻击。由于该漏洞的利用依赖于构造不安全的 Paillier 密钥，如果曾经受到过此类攻击，在攻击方的 Paillier 公钥 中一定存在小因子，因此我们可以通过分析 MPC 参与方的 Paillier 公钥 中是否存在小因子来检测是否存在过攻击。
具体的检测方式可以利用成熟的大整数分解算法工具检查 Paillier 模数 是否具有小因子。如果存在小因子，则有被攻击的可能，建议尽快转移资产并创建新的 MPC 钱包。
