他山之石丨价值百万美元的比特币密钥追回记

技术的突破是推动区块链行业前进的引擎，币安中国区块链研究院与链闻 ChainNews 同为密切关注区块链与密码学等领域技术发展前沿的组织，故而联合推出「他山之石」专栏，向中文世界读者介绍全球范围最值得关注的区块链技术进展，以及在金融等产业最新的应用分析与动态，以期为中国的区块链行业「攻玉」提供借鉴和思考。

区块链开发公司 Pyrofex CTO、密码学专家 Mike Stay 讲述他如何用 11 天时间帮助客户找回丢失的比特币私钥。

撰文：Mike Stay，区块链开发公司 Pyrofex CTO，谷歌前软件工程师
翻译：Chen Bo Yu、Hsu Tzu Hsiu

原文发表于 2020 年 4 月 3 日，彼时比特币约 6918 美元，价值 30 万美元即约 43 枚 BTC。

原本预想需要花费数十万年、十万美元建造 GPU 农场才能找回的比特币密钥，幸运地在短时间内被密码学专家 Mike Stay 找回，或许奥地利经济学派支持者、黄金支持者、比特币反对人士 Peter Schiff 可以考虑联系一下 Stay 找回他丢失的比特币。

大约二十年前，我在杨百翰大学 BYU 攻读物理学学位的同时，也在 AccessData 公司做逆向工程和密码分析师。当时是 90 年代末和 2000 年代初，美国政府已经逐渐放宽了对含有密码学的软件出口限制，但大多数软件仍然包含着相当脆弱的密码保护。我们会去买桌面办公软件，对它进行逆向工程，弄清楚它是用什么算法进行访问控制，然后破解密码。这是一个有趣且永无止境但并非不可能的数学难题。我在那里的时候写了大约 40 个密码破解器，我们会把它们卖给家庭用户、系统管理员，以及地方和联邦执法机构，我就去过了几次位于 Glynco 的联邦执法培训中心，给特勤局、FBI 和 ATF 教授密码学和我们产品的使用方法。

Mike Stay，区块链开发公司 Pyrofex CTO，谷歌前软件工程师

从 Word 97 与 zip 的加密算法讲起

在我的记忆中，有两个项目让我特别印象深刻。第一个是 Microsoft Word 97。在 Word 97 之前，文件的加密方式是用密码衍生的 16 字节字符串对文件进行 xor 加密。Word 文件中最常见的字节通常是 0x00、0xFF 或 0x20 （空格），所以我们只需查看每列中最常见的字符，然后尝试这些字符的 3^16 种可能组合。找回密钥通常是瞬间的事，但为了帮助人们觉得自己的钱花得值，我们会像好莱坞中出现的黑客场景一样，用大量随机字符上演一个小动画，逐渐揭示破解出的正确密码。

Microsoft Word 97 改变了这个加密算法。也许可以通过 MSDN 找出微软使用的加密格式，但我们当时规模小，没钱订阅，也不清楚我们从他们那里得到的信息是否足以让我们写出破解器。为了弄清它的工作原理，我用 SoftICE 在输入密码后立即停止软件，然后在堆栈上慢慢一步一步执行，直到找到加密算法。这都是在 IDA Pro 诞生

之前，所以我打印了几十页汇编代码贴在墙上，用红色蜡笔在上面画满了我的注记。当我终于把它的模式找出来的时候高兴极了。当时微软只允许输出 40 位比特的密码算法，所以他们在允许的范围内做了很多事情：他们会用「盐」（salt，随机选取存储在文件中的字节）反复对密码进行 MD5 哈希，得到 40 位的输出，然后在此基础上加盐，再反复哈希。在当时的电脑上运行这个过程测试一个密码大概需要半秒钟的时间，我们不得不采用字典攻击的方式，因为直接破解它几乎是不可能的，我们最终也确实为大公司和机构写了一个破解器，利用 Intel Pentium 处理器上那些花哨的 MMX 指令集，强行破解了 40 位哈希值的组合。我听说过有人花了九个月才破解了这个软件。

另一个非常有趣的是 zip 档案。PKZIP 的开发者 Phil Katz 做出了一个决定：将他的档案格式记录下来，并将其包含在他的软件中，这在当时是很不常见的，这也因此使其成为了开发者的最爱。Roger Schlafly 设计了用于加密压缩档案的流密码，zip 标准也很快就成为 Windows 上最流行的压缩格式，许多其他格式如 Java 的 jar 档案和 OpenOffice 的文档格式，其实都是内部有特定目录结构的 zip 文件。而 InfoZIP 是一个开源版本的软件，它 zip 的实作方式几乎被作为其他所有知名压缩软件的基础，比如 WinZip。在我当时试图破解它的时候，WinZip 占据了 95% 的市场。

Eli Biham 和 Paul Kocher 曾发表过对其密码算法的已知明文攻击，但已知明文通常就是压缩明文中的一部分，要想透过一个 zip 加密压缩文件获得压缩明文，你基本会上需要整个文件，所以这种攻击对执法机构来说几乎是无用的。

zip 的加密算法有 96 位比特的内部状态，分成三个 32 位的小块，分别称为 key0、key1 和 key2。而 key0 和 key2 是两组线性反馈移位寄存器 CRC32 算法的内部状态，如果要用一个新的数据字节更新状态，你要将所有的字节向下移动一个字节（舍弃低字节），然后与查找表中的一个常数进行 xor 操作，这个常数在查找表中的索引是被舍弃低字节与该数据字节 xor 后的结果。key1 是截断线性同余方法（linear congruential generator）的内部状态，要更新它的内部状态，输入一个数据字节，乘以一个我称之为 c 的常数，然后加 1。而这个加密算法的工作原理是这样的：你向第一个 CRC32 输入一个数据字节，然后取其舍弃的低字节并将其输入 TLCG，然后取其产生的高字节并将其输入第二个 CRC32，然后取其状态并（粗略地）平方，然后输出结果的第二个字节作为流字节。最一开始的 96 位状态是已知的，接着加密密码，然后加密十个字节长的盐（salt）。

PKZIP 通过直接分配未经初始化的内存来获得它的 salt 字节，所以它可能实际上包含了你运行的其他程序上的一些内容，也可能是图像或文档等等。这在 Windows 上工作得很好，没遇到什么问题，但在许多 Unix 系统上，当内存被分配时它会自动初始化。InfoZIP 通过使用 C 语言的 rand 函数来选择盐字节，它将通过 xor 时间戳和进程 ID 来初始化随机数生成器的状态，然后为每个文件生成 10 个字节。如果他们只有这样做的话，那么知道时间戳和进程 ID 后就足以恢复部分信息，接着就能够发动 Biham 和 Kocher 的已知名文攻击。看来 InfoZIP 的作者知道这种攻击，因为他们更进一步，用密码对头文件加密了一次。这样一来，攻击者就只有双重加密的明文，他们的攻击就无法得逞了。

我注意到由于两次使用密码都是一样的，所以每次密码的第一个流字节都是一样的。就像电灯开关两次操作会让它停留在开始的地方一样，用相同的数据流字节 xor 一个字节两次会让它回到初始状态。这让我可以发动一个非常强大且只针对密码文本的攻击：给定一个档案中的五个加密文件，我可以推导出 C 的 rand 函数中的内部状态，而无需查看时间戳或知道进程 ID 。这就得以让我可以生成原始、未加密的头文件。而因为密码的每一部分只有几位影响下一部分，所以我也只能猜测状态的几位，并检查两次解密一个字节是否给了我预期的答案。随着我的继续，我需要猜测的内容越来越少，每一个额外的档案也让我排除了更多潜在的可能。当时这个过程在一台台式机上花了几个小时。我之后发表了一篇关于这个攻击的论文，并在 2001 年日本的快速软件加密会议（Fast Software Encryption）上公开发表。

2002 年我离开了 AccessData，接着在一家神经网络初创公司工作了一年，在奥克兰大学和 Cris Calude 一起读了三年计算机科学硕士，在加州大学河滨分校和数学物理学家 John Baez 一起读博士，在 Google 的应用安全团队工作了六年并完成了博士学业，又过了几年，最后成为一家初创公司的 CTO。

比特币来敲门

大约半年前，我在 LinkedIn 上突然收到了一个俄罗斯人的消息。他看了我 19 年前写的那篇论文，想知道攻击是否能在只有两个档案的场景上发挥作用。我分析了一下后表示，没有巨大的计算能力和大量的金钱是行不通的。因为我只有两个档案可以使用，所以每个阶段都会有更多的假设需要去计算验证。最后会有 2^73 个可能的密钥需要测试，将近 10^22 这么大。我估计需要一个大型的 GPU 农场一年才能攻破，成本在 10 万美金左右。可是他让我大吃一惊，因为他表示愿意花这么多钱来找回密钥。

早在 2016 年 1 月，他就花了 1 万或 1.5 万美元买了左右的比特币，并把密钥放在一个加密的压缩文件中。现在它们的价值高达 30 多万美元，而他却不记得密码了。幸运的是，他还保留着原来的笔记本电脑，并且知道加密发生的确切时间。因为 InfoZip 使用了时间戳作为熵的种子，这就大大地减少了工作量，只需要 10^19 次测试，并使它变得相当可行，在一个中等的 GPU 农场上只需要几个月的时间。我们签订了合同，我就开始工作了。

我花了一会儿时间根据当初论文中的概述重建了这次的破解。令我懊恼的是，有一些棘手的细节在我撰写论文时忽略了，不过我又顺利把它们解决了。然而我发现我在估算工作时犯了一个可怕的错误！

在我最初的攻击中，我会去猜测 key1*c、key1*c^2、key1*c^3 和 key1*c^4 的高字节。当我猜到第四个字节的时候，我已经知道了密码其余部分的完整状态，我只需要把这四个字节转换成原始的 key1 就可以了。我会尝试在 key1 的 32 位空间中找出所有可能，并检查每一个状态是否给出了正确的高字节。不过在这里，我有 10^19 个密钥要检查，如果我必须对每个密钥进行 2^32 次测试，那就需要花上几十万年的时间。

我隐隐约约记得，曾经有人用晶格还原法对 TLCGs 进行过加密分析，于是我挖出了原始论文，发现实在是太完美了！我只需要定义一个由 2^32 和 TLCG 中的常数幂给定的基向量的网格，然后进行网格还原。给定了还原后的基数，我只要做一个矩阵乘法就可以从高字节中恢复原始状态。

至少，这是我的想法。但我需要五个字节才能将其限制在单一结果上，而在攻击的那个点上，我只有四个字节。根据论文中描述的过程这几乎不会算出正确的答案。然而，我知道答案会很接近正确的答案，所以我跑遍了所有可能的 key1 值，并检查它给我的答案和真实答案的差异，发现了差值总是 36 个向量中的其中一个！这就是我的优化，有了这个优化，我可以只运行 36 种可能性，而不是 40 亿个。

接下来，我们遇到的是在机器上的 GPU 之间传输数据的问题。我的业务伙伴 Nash Foster 研究了 GPU 的实现，告诉我不同操作 GPU 操作的速度是多少，并为了将加密破解代码放入其中的应用程序编写了很多支持结构。我们如何将这些 PB 级的候选密钥送到 GPU 上进行测试？我突然想到，我的攻击的每个阶段都在猜测大量的比特，然后只在大约六万五千个的候选密钥中选定一个。如果我有某种方法能够透过这些信息来推导比特，而不是仅仅去猜测和检查，我就可以节省很多工作，更重要的是可以节省很多网络流量。但这个想法的问题是数学太复杂了，它涉及到将有限域的数学和整数环的数学混合在一起，而这并不是什么容易的事情。

我想了想我所知道的其他密码攻击，其中有一种似乎可以派上用场，那就是中间相遇攻击。中间相遇攻击适用于块加密，当它使用一部分密钥做前半部分的加密，而另一部分密钥做后半部分的加密。这基本上适用于压缩密码，但密钥的数量远远超过了中间的位数。后来我想到可以利用 CRC32 的线性优势：把最后一个 CRC32 的两个输出 xor 在一起，结果就可以不受 key2 的影响了 ! 与其计算加密的中间状态并将其存储在表中，我不如计算两个中间状态的 xor 结果并将其存储。

我写出了差分的中间相遇攻击，并在我的笔记本电脑上运行。之前在我的笔记本电脑上需要几个小时的阶段，现在只用了几秒钟就完成了。下一个阶段，我预计在 GPU 农场上需要一周的时间，在强大的 CPU 上只用了几个小时就完成了。我没办法让它在第三阶段计算得更快，以至于对加速整体攻击有用，但它完全避免了移动数据的需要：我们只需在每个 GPU 的电脑上计算出候选组合并让它们运算。Nash 编写了 GPU 代码，运行速度快得惊人。

攻击运行了十天，失败了。

我伤心极了。难道我们漏掉了哪些候选密钥？我们回去看了看他笔记本上的最大进程 ID，发现它比我们预期的大了几个位，因此 rand 还有其他几个可能的初始种子。我还回去仔细检查了我们所有的测试。是否有我们遗漏的东西？基于 CPU 的版本和 GPU 版本的表现有什么不同吗？我们的客户重新运行了我们的测试，发现 GPU 版本在正确的答案排在候选列表中的第二位时，无法找到正确的密钥，但在排在第一位的时候却能找到。仔细研究代码，我们发现我们在计算偏移到数据结构中的数据块索引和线程索引时，将数据块索引和线程索引互换了。

我们修复了这个错误，接着重新运行代码，并在一天之内找到了正确的密钥。我们的客户非常高兴，给了我们一大笔奖金，因为我们很快就找到了密钥，所花的费用远小于最初的估计。

来源链接：reperiendi.wordpress.com

免责声明：作为区块链信息平台，本站所发布文章仅代表作者个人观点，与链闻 ChainNews 立场无关。文章内的信息、意见等均仅供参考，并非作为或被视为实际投资建议。

—-

编译者/作者：币安区块链研究院

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。