密码学团队硬核解析：Wintermute 遭黑客攻击损失 1.6 亿美金背后密码技术详解

2022-09-24

By Max

从最近的黑客攻击说起

9 月 20 日，数字资产做市商 Wintermute 首席执行官 Evgeny Gaevoy 宣布其 DeFi 相关业务遭到黑客攻击，损失约 1.622 亿美元，疑因其合约地址「私钥」遭到暴力破解，引发强烈的市场反响。无独有偶，9 月 19 日，据 The Block 报道，一名黑客利用 Profanity 漏洞从多个通过 Profanity 建立的以太坊地址中盗取 330 万美元资产。

Safeheron 密码学安全团队跟进分析发现，Wintermute 合约地址采用 Profanity 开源库生成，而该类 0x000000 开头的靓号地址，存在被暴力破解的可能性。此前 1inch 曾发文披露该漏洞潜在的安全威胁， 那么，这一系列攻击究竟是怎么发生的呢？靓号地址生成开源库 Profanity 在其中又起到什么作用呢？接下来，Safeheron 团队将从以下几个方面，硬核还原靓号地址被攻击的全技术过程。

• 什么是靓号地址？

• Profanity 的靓号地址生成原理

• Profanity 的理想安全性

• 直觉上 Profanity 存在的问题

• Profanity 算法的形式化描述

• 靓号地址的私钥攻击原理

• 靓号地址的私钥攻击示例

• 攻击效率分析

• 安全改进建议

• 进一步思考

什么是靓号地址？

所谓靓号地址，是加密货币生态中的很多参与者用以凸显个性的一种方式。具体来说，它是指这样的一些地址：

• 开头 8 个 8：

0x88888888bc27358faea388cdf91fa9b676068207

• 开头 7 个 0：

0x0000000925e311792debae85befaa946200ffc67

• 开头指定单词：

0xdead9b096ec34c35e45b5a2aab5337805916ac1e

• 镜像地址：

0x5b4d6554bd4d 89dfcd0bb0dcfd98 c3e73ab05f69

这些靓号地址不仅彰显个性，也带来一些其它的好处，比如方便记忆，让人印象深刻，不容易错判等等。

为生成这些靓号地址，开发者们提供各式各样的开源生成工具，而 Profanity 就是以太坊生态中最著名的开源生成工具之一。下面我们将介绍 Profanity 的具体原理。

Profanity 靓号地址生成原理

Profanity 到底是如何生成靓号地址的呢？通过分析 Profanity 开源库，可以整理出原理图：

生成步骤如下：

1. 获取安全随机数（从硬件或者熵池），作为伪随机数算法 mt19937 的种子。

2. 利用伪随机数算法 mt19937 生成种子私钥（Seed Private Key），然后计算出种子公钥（Seed Public Key）。

3. 调用 OpenCL 并行计算平台，调用基于种子公钥（Seed Public Key） 的多轮迭代算法，计算大量的候选公钥（Candidate Public Key） 和 eth 地址（Address）。

4. 调用指定靓号筛选器，筛出靓号，并输出靓号私钥（Vanity Private Key） 和靓号地址（Vanity Address）。

Profanity 库支持并行计算架构，不仅靓号模式选择多样，而且生成效率极高，受到社区广泛欢迎。然而这也为后面的攻击埋下伏笔。

Profanity 的理想安全性

理想中的 Profanity 安全性有多高呢？我们一起来看看，如果需要暴力破解这样一个靓号地址的私钥，到底需要多长时间。

0x88888888bc27358faea388cdf91fa9b676068207

我们可以大概评估一下总的计算次数。原始种子范围是 $(0, 2^{32})$，开头是 8 个 8，假设用户选择使用首次匹配地址，则需要计算次数为 $2^{32} * 2^{32} = 2^{64}$次，而这已经是个不小的量级。

接着评估一下破解时间。以我本地电脑为例，计算首次靓号地址耗时平均大概是 10 秒 （简单三次评估），那么暴力破解靓号地址私钥需要耗时（以月计) $2^{32} * 10 / ( 3600 * 24 * 30 ) = 16570$月。

如果使用并发加速，同时使用 1000 台跟我个人 PC 同配置的机器，则需要日夜不断的跑 16 个月。

看起来，要暴力破解似乎也是非常困难的事情。那么，是否真的安全么？

直觉上 Profanity 所存在的安全风险点

乍一看来，调用安全随机数，也进行大量计算，似乎没有明显的问题。可是黑客毕竟成功开展攻击，那么，问题究竟在哪里呢？

直觉上看，Profanity 至少有两大风险点：

• 从硬件或者熵池获取随机数时，仅仅获取 32 bit，这是非常短的。要知道，常见私钥的长度是 256 bit，远远超出 32 bit。

• 在后续的并行多轮计算时，其迭代算法并非使用单向函数（比如 hash 函数）。单向函数会带来更高的安全性，而不使用单向函数则意味着逆向追溯的可能。

单独一个风险点未必会立刻致命，但是当两个一起出现，则可能地覆天翻。

Profanity 算法的形式化描述

在描述攻击原理之前，我们首先将整个 Profanity 原理抽象一下。

Step 1: 计算种子公钥（Seed Public Key）

从随机设备（Random Device）到种子公钥，中间有两步：

• 获取 32 bit 安全随机数（从硬件或者熵池），作为伪随机数算法 mt19937 的种子。

• 利用伪随机数算法 mt19937 生成种子私钥（Seed Private Key），然后计算出种子公钥。

对应 32 bit 安全随机数，我们定义随机种子空间， $R = [0, 2^{32})$；由于伪随机数算法 mt19937 本质上是个确定性算法，因此种子私钥的计算就是确定性的，种子公钥 的计算也是确定性的。

如下所示：

$R = [0, 2^{32})$ $SeedPriv= mt19937(i), i\in R$ $SeedPub= SeedPriv * G$

为简化表述，我们定义函数：$f(x)=mt19937(x)*G$

记种子公钥集合为 $Set_{SeedPub}$，那么有：

$Set_{SeedPub} = \{f(i) \mid i \in R, R=[0, 2^{32}) \}$

显然，种子公钥的数量是 $2^{32}$。

Step 2: 计算候选公钥（Candidate Public Key）

Profanity 从种子公钥开始进行并发多轮迭代（Iteration）操作，生成一系列的候选公钥。整个迭代操作本质上是一个以指定种子公钥为中心的公钥搜索和遍历算法。具体的，迭代是基于轮序号 ($round$，记为 $r$) 和轮内序号 ($foundID$，记为$fid$) 两个维度下的线性搜索操作。

迭代算法如下：

$CandidatePub_{r, fid} = SeedPub + \Delta(r, fid) * G$

其中迭代偏移函数定义为：

$\Delta(r, fid) = r * k_1 + fid * k_2$

其中 $k1$ 和 $k2$ 是两个常数，$G$ 是椭圆曲线基点。

迭代计算的结果，备选公钥集合可以定义为：

$CandidateSet_{Pub} = \{CandidatePub_{r,fid} \mid r \in [0, r_{max}), fid \in [0, fid_{max}) \}$

代入 $CandidatePub_{r,fid}$ 定义，即：

$Set_{CandidatePub} = \{SeedPub + \Delta(r, fid) G \mid r \in [0, r_{max}), fid \in [0, fid_{max}) \}$其中 $r_{max}$ 和 $fid_{max}$ 分别是轮序号上限和轮内序号上限，定义迭代搜索空间的大小。

$SeedPub$ 取不同的值，就会生成不同的备选公钥集合。

例如：$SeedPub = f(2)$，则有：

$Set_{CandidatePub} = \{f(2) + \Delta(r, fid) G \mid r \in [0, r_{max}), fid \in [0, fid_{max}) \}$

注意: 根据迭代偏移函数定义，以下等式成立:

$\Delta_{r_1,fid_1} - \Delta_{r_2, fid_2} = \Delta_{r1-r2,fid_1-fid_2}$

Step 3: 过滤靓号

基于每个备选公钥，计算 eth 地址。随后使用模式过滤器，筛出靓号地址。这里，我们把靓号地址所构成的集合记为 $Set_{VanityAddr}$。

靓号地址的私钥攻击原理

现在我们考虑如何对上图中的私钥机制进行攻击。

Step 1: 穷举种子公钥集合

种子公钥集合 $Set_{SeedPub}$ 的元素个数上限也是 $2^{32}$，这不是个很大的数字，将其穷举出来，整个集合$Set_{SeedPub}$，包括其对应私钥，所占存储空间大概是 300 G，一台电脑就可以存储下来。

Step 2: 计算真实靓号公钥

找到靓号地址，从其线上任何一笔交易中的签名，即可恢复出靓号公钥，不妨设为找到靓号地址，从其线上任何一笔交易中的签名，即可恢复出靓号公钥，不妨设为 $VanityPub_0$。具体算法参见椭圆曲线数字签名算法。

Step 3: 计算候选公钥集合的一个平移集（Shift Set）

我们定义候选公钥集合关于靓号公钥 $VanityPub_0$的一个平移集：

$ShiftSet_{VanityPub_0} = \{VanityPub_0 - \Delta_{r,fid} G \mid r \in [0, r_{max}), fid \in [0, fid_{max}) \}$

为了更好的说明，不妨假设有一个3 轮、轮内迭代次数也是 3 的例子，以下是基于种子公钥 $f(2)$ 的一个候选公钥集合：

候选公钥集合中的某个公钥将被筛选出来为靓号公钥，不妨设被选出来的靓号公钥为：$VanityPub_0 = f(2) + \Delta_{1,2} G$

下面将演示，如何通过求平移集合 $ShiftSet_{VanityPub_0}$来求出种子公钥 $f(2)$：

如图所示，我们求出平移集合：

$\{ f(2)+\Delta_{-1,-1}G, f(2)+\Delta_{0,-1}G, f(2)+\Delta_{1,-1}G, f(2)+\Delta_{-1,0} G,$$f(2), f(2)+\Delta_{1,0}G, f(2)+\Delta_{-1,1}G , f(2)+\Delta_{0,1}G, f(2)+\Delta_{1,1}G \}$

其包含靓号公钥对应的种子公钥 $f(2)$，细心的人可以发现，靓号私钥相对与种子私钥的偏移为 $-\Delta_{1,2}$。

Tips:

• 为什么命名为「平移集合」？这是因为平移集合和候选公钥集合在二维空间中就是两个矩阵，这两个矩阵大小相等，可能相邻，也可能有一部分元素重合。看起来，基于靓号公钥，对候选公钥集合做平移，即可得到平移集合。如下图所示。

• 为什么求平移集合？因为平移集合中包括种子公钥。比如上图中的 $f(2)$ 就是种子公钥。

Step 4: 集合求交

将平移集合的计算的迭代搜索范围记为 $r_{max}，fid_{max}$，用户靓号公钥当初的迭代坐标为 $r，fid$， 则有以下命题成立：

命题：如果 $r_{max} > r$， $fid_{max} > fid$，则基于靓号公钥所计算的平移集合与种子公钥集合一定存在交集。

该命题保证一定能够找到与靓号公钥关联的种子公钥。

计算交集 $InterSect = Set_{SeedPub} \cap ShiftSet_{VanityPub}$。

交集中至少存在一个元素，它是一个种子公钥，不妨记为 $SeedPub_0$，从 Step 1 预存的数据中能获取对应的私钥。由于 $SeedPub_0 \in ShiftSet_{VanityPub}$，因此 $SeedPub_0$ 相对于 $VanityPub$ 的私钥偏移 $\Delta$ 也在 Step 3 中记录下来的，通过查询可得。

以 Step 3 中为例，如上图所示， 交集为 $InterSect = { f(0)}$，查询可知种子公钥相对于靓号公钥的私钥偏移 $\Delta = -\Delta_{1,2}$。

注意：集合求交很多不同的实现方法，比如数据量不大是可以直接通过查数据库，如果数据量太大，可以结合一些成熟算法解决。

Step 5: 计算靓号私钥

至此，可轻易计算出来靓号公钥 $VanityPub$ 的私钥：

$VanityPriv = SeedPriv - \Delta$

以 Step 3、Step 4 中的示例，可直接计算靓号私钥：

$VanityPriv = Priv_{f(0)} - ( - \Delta_{1,2} ) = Priv_{f(0)} + \Delta_{1,2}$

靓号地址攻击示例

现在我们通过一个具体的例子，来展示如何获取靓号地址的私钥。待破解的靓号地址如下，这是一个以「dead」单词开头的地址：

0xdead9b096ec34c35e45b5a2aab5337805916ac1e

Step 1: 穷举种子公钥集合

预生成种子公钥集合 $Set_{SeedPub}$ 并存储起来，注意此时所有种子公钥对应的私钥也同样存储了。

Step 2: 计算真实靓号公钥

找到该地址的链上交易，从签名中恢复公钥，如下所示：

0x0488dff9528cc2fc582e11688abce90cd84d8c805424fa3c761f50ad96b877a8cf3c3b0796ec099a05403562a4e0f8ecec9c511265e12ae45793bad11111e11e4d

Step 3: 计算候选公钥集合的一个平移集（Shift Set）

记 $VanityPub_0$ 为 Step 2 得到的公钥，指定 $r_{max} = 4，fid_{max} = 0x10000$。

此时平移集合元素个数为：$r_{max} * fid_{max} = 262144$，这是一个很小的集合，也意味这很小的搜索空间。

计算平移集合：

$ShiftSet_{VanityPub_0} = \{VanityPub_0 - \Delta_{r,fid} G \}$

（其中 $r \in [0, 4), fid \in [0, 0x10000)$）

Tips:

• 计算平移集合的过程中，平移集合中所有元素（即公钥点）相对于靓号公钥的偏移也被记录下来。

• 关于平移集合的 $r_{max}$，$fid_{max}$ 参数的选择，可以根据"靓号地址”的难度来设计平移集的大小。

Step 4: 集合求交

计算 $Set_{SeedPub}$ 与 $ShiftSet_{VanityPub_0}$ 的交集，得到集合 $\{SeedPub0\}$。

集合中的种子公钥 $SeedPub0$ 为：

0x04f316acd6890440bb7ed841e9c9d0a69dbd3545ef390947ad55248cd90719ff84e897f3359caf934fc2d6835f02038a00305aa2f823376e963afe42cfa159384c

通过查询预存储信息，可以获取对应的种子私钥 $SeedPriv$为：

0x045c2f14d04b94b99f64c1c36e984311d2fdb49c9b39f8aa272b92da72e323e0

由于 $SeedPub0 \in ShiftSet_{VanityPub0}$，因此 $SeedPub0$ 相对于 $VanityPub$ 的私钥偏移也在 Step 3 中记录下来的，查询可得：

$\Delta = -131222811778258561367987177892156266428619740566520641492090882$

Step 5: Calculate the vanity private key

$$\begin{align*} VanityPriv &= SeedPriv - \Delta \\ &= 0x045c2f14d04b94b99f64c1c36e984311d2fdb49c9b39f8aa272b92da72e323e0 - (-131222811778258561367987177892156266428619740566520641492090882) \\ &= 0x045c2f14d04be6629f64c1c36e984311d2fdb49c9b39f8aa272b92da72e323e2 \end{align*}$$

从靓号私钥计算靓号公钥，用于复验，复验正确，至此攻击成功结束。

攻击效率分析

详细分析

攻击步骤一共 5 步，Step 2 和 Step 5 基本不耗时，Step 1 可以预先计算，所以也可以省去 Step 1 的耗时。最终，主要耗时都在 Step 3 和 Step 4。

为分析计算规模，我们可以定义候选公钥集合计算的轮数上限为 $r_{max}$，轮内序数上限为 $fid_{max}$。

Step 4 中，需要解决两个集合求交的问题，一个集合大小是 $2^{32}$ ，另一个集合大小为 $r_{max}*fid_{max}$。集合求交是一个成熟的问题，有一些成熟的解决方案，此处不必赘言。

着重说一下 Step 3，Step 3 是需要计算候选集合的一个平移，理想状态下其规模跟候选公钥集合一样，因此计算次数为 $r_{max}*fid_{max}$。这是个什么概念呢？它意味着，如果不考虑集合求交的耗时，私钥破解耗时跟靓号地址生成耗时大致是一样的。

Tips:

• 平移集合的设计和计算方式直接影响到攻击的效率。

• 在实际攻击操作时，由于候选公钥集合是未知，我们可以根据靓号难度来估算候选公钥集合的大小，从而设计平移集合。

• 平移集合基数可能会略大于候选公钥集合。

实例分析

我们给一些具体的例子，让大家有个直观的印象：

通过实验观察发现：大部分时候，对于 Profanity 中指定模式下的前 2～3 个靓号地址，轮序号小于 $2^4$，轮内序号小于 $2^{22}$。这表明着大部分的平移集合的基数（元素总数）$|ShiftSet| <= r_{max} * fid_{max} = 2^{4} * 2^{22} = 2^{26} \approx 6kw$，意味着，大部分时候，你最多只需要进行 6 千万次穷举就能完成破解。

还有不少的情况，平移集甚至只有百万量级大小，更是反手可破。

效率总评

基本结论是攻击效率极高，不用付出太高的代价，就能破解几乎所有的 Profanity 靓号地址私钥。

• 如果不考虑集合求交的耗时，私钥的破解速度可以逼近靓号地址的生成速度，这是非常可怕的，完全摧毁 Profanity。

• 用户的不好的使用习惯会大大提升私钥破解的风险，一般来说，Profanity 越早生成出来的地址，搜索空间越小，风险越大，越容易破解。由于大部分用户都喜欢用最早生成出来的几个靓号地址，导致大部分 Profanity 用户的靓号地址私钥随时可能被破解。

Profanity的安全改进建议

主要是两点建议：

• 从硬件或者熵池获取随机数作为种子时，直接取出 256 bit。

• 并行多轮迭代计算时，使用单向函数（比如 hash 函数）。

进一步思考

如果 Profanity 算法中生成候选公钥时使用单向函数，算法是否安全？

答案是否定的。生成备选 Public Key 使用单向函数，确实能防止本文中提出的攻击方法，但是它不能阻止生日攻击。因为种子长度为 32bit 那么碰撞概率 50% 时，$n(0,5, H) = 1.1774 * \sqrt(H) = 1.1774 * \sqrt(2^{32}) = 77162$。这说明如果选择同样的靓号策略，只要 Profanity 的用户数接近 8 万，就有 50% 的概率生成重复私钥。

如果随机种子的长度提高到 64 bit，我们是不是就能用呢？

答案是否定的。64 bit 并不是足够长的随机数，同样存在生日攻击的问题，只不过 50% 碰撞概率的人数提高到大约 50 亿而已，这依然不够安全。

我们还能使用靓号么？

首先，Profanity 生成的靓号地址都存在致命的风险，因此我们强烈建议，所有的 Profanity 用户都应该将资产转移到其它安全的地址上。其次，我们还是可以使用靓号地址的。并不是所有的靓号地址都有问题，如果不一味强调效率，选择用更安全的算法来计算，那么就能生成安全的靓号地址。

关于私钥的安全生成有什么更好的建议？

私钥就是随机数，要想让私钥足够安全，就要足够随机。获取安全随机私钥的方法多种多样。

• 如果有经过认证的安全硬件，可以使用安全硬件提供的安全随机数。

• 对于足够复杂的运算平台，包括常见的各类 PC 和移动端，环境噪声足够复杂，使用平台自带的熵池和伪随机数发生器便已足够随机。

• 如果是简单平台，比某些硬件钱包，则需要从外部导入随机种子。方式包括不限于导入随机文件、环境照片、语音、视频等等。

• 还有一种更安全的方式，通过 MPC 聚合多平台的随机性。基于 MPC 从多平台生成私钥分片，即便单平台私钥不够随机或者遭遇黑客攻击，整个 MPC 钱包私钥依然是安全的。