安全鹭：Wintermute遭黑客攻击损失1.6亿美金背后的密码技术详解

原文作者： Max，Safeheron 安全鹭

从最近的黑客攻击说起

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：

· 开头 7 个 0：

· 开头指定单词：

· 镜像地址：

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

为生成这些靓号地址，开发者们提供各式各样的开源生成工具，而 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 安全性有多高呢？我们一起来看看，如果需要暴力破解这样一个靓号地址的私钥，到底需要多长时间。

我们可以大概评估一下总的计算次数。原始种子范围是（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 本质上是个确定性算法，因此种子私钥的计算就是确定性的，种子公钥 的计算也是确定性的。如下所示：

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

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

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

迭代算法如下：

Step 3: 过滤靓号

靓号地址的私钥攻击原理

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

Step 1: 穷举种子公钥集合

Step 2: 计算真实靓号公钥

具体算法参见 此处 。

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

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

候选公钥集合中的某个公钥将被筛选出来为靓号公钥，不妨设被选出来的靓号公钥为:

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

Tips：

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

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

Step 4: 集合求交

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

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

Step 5: 计算靓号私钥

靓号地址攻击示例

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

Step 1: 穷举种子公钥集合

Step 2: 计算真实靓号公钥

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

0x0488dff9528cc2fc582e11688abce90cd84d8c805424fa3c761f50ad96b877a8cf3c3b0796ec099a05403562a4e0f8ecec9c511265e12ae45793bad11111e11e4d  

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

Tips:

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

2. 关于平移集合的，参数的选择，可以根据"靓号地址」的难度来设计平移集的大小。

Step 4: 集合求交

Step 5: 计算靓号私钥

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

攻击效率分析

详细分析

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

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

Tips:

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

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

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

实例分析

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

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

效率总评

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

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

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

Profanity 的安全改进建议

主要是两点建议：

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

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

进一步思考

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

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

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

我们还能使用靓号么？

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

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

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

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

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

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

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

原文链接

欢迎加入律动 BlockBeats 官方社群：

Telegram 订阅群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方账号：https://twitter.com/BlockBeatsAsia