价值数百万美元的比特币密钥恢复

技术突破是推动区块链产业进步的引擎作为一个关注区块链和密码学领域技术发展前沿的组织，我们联合推出了“别山之石”专栏，介绍全球最值得关注的区块链技术以及在金融等行业的**应用分析和趋势，从而为中国区块链产业“攻坚”提供借鉴和思考。

区块链开发公司pyroflex CTO和密码专家Mike stay描述了他如何花11天时间帮助客户找回丢失的比特币私钥。

作者：Mike stay，区块链开发公司pyroflex CTO，前谷歌软件工程师
翻译：Chen Bo Yu，Hsu Tzi Xiu

原文发表于2020年4月3日。当时，比特币约为6918美元，价值30万美元，约合43个比特币。

比特币密钥原本预计需要几十万年和10万美元才能建立一个GPU农场来检索，幸运的是密码专家迈克·斯泰伊在很短的时间内检索到了密钥。或许，奥地利经济学派支持者、黄金支持者和比特币反对者彼得·希夫（Peter Schiff）可以考虑联系stay找回他丢失的比特币。

大约20年前，当我在杨百翰大学（Brigham Young University）的BYU学习物理时，我还在access data担任逆向工程和密码分析师。当时是20世纪90年代末21世纪初，美国政府逐步放宽了对含密码软件出口的限制，但大部分软件的密码保护仍然相当脆弱。我们将购买桌面办公软件，对其进行反向工程，找出它用于访问控制的算法，然后破解密码。这是一个有趣的，永无止境的，但不是不可能的数学问题。当我在那里的时候，我写了大约40个密码破译器，我们会把它们卖给家庭用户、系统管理员、地方和联邦执法机构。我去了几次位于格林科的联邦执法培训中心，向特勤局、FBI和ATF教授密码学以及如何使用我们的产品。

比特币 Mike stay，区块链开发公司pyroflex CTO，谷歌前软件工程师

从word97和zip的加密算法

在我的记忆中，两个项目给我留下了特别深刻的印象。第一个是微软word97。在word97之前，文件加密方法是XOR加密，16字节字符串来自密码。word文件中最常见的字节通常是0x00、0xff或0x20（空格），因此我们只需要查看每列中最常见的字符，然后尝试3^16个这些字符的可能组合。取回钥匙通常是瞬间的，但为了让人们觉得自己的钱是值得的，我们会上演一个有大量随机角色的小动画，就像好莱坞的黑客场景一样，并逐步揭示正确的密码。

Microsoft Word 97更改了加密算法。也许我们可以通过MSDN找到微软使用的加密格式，但那时我们很小，没有钱订阅，也不知道从他们那里得到的信息是否足以让我们编写一个破解程序。为了找出它是如何工作的，我在输入密码后立即使用softice停止软件，然后在堆栈上一步一步地执行，直到找到加密算法。这一切都是在艾达专业出生的

以前，我打印了几十页的汇编代码，贴在墙上，用红蜡笔写满了我的笔记。当我终于找到了模式时，我非常高兴。当时，微软只允许输出40位的密码算法，所以他们在允许的范围内做了很多事情：他们会用salt（随机选择存储在文件中的字节）对密码反复执行MD5哈希运算，得到40位的输出，然后在此基础上添加salt，然后反复哈希运算。当时在计算机上运行这个过程大约需要半秒钟来测试密码。我们不得不使用字典攻击，因为直接破解它几乎是不可能的。**，我们确实为大公司和机构编写了一个破解程序，并使用英特尔奔腾处理器上奇特的MMX指令集强制破解40位哈希值的组合。我听说有人花了九个月才破解这个软件。

另一个有趣的事情是zip文件。PKZIP的开发人员Phil Katz做了一个决定：记录他的文件格式并将其包含在他的软件中，这在当时是非常不寻常的，这使得它成为开发人员的**。rogerschlaf设计了一种用于加密压缩文件的流密码。Zip标准很快成为windows上***的压缩格式。许多其他格式，如javajar文件和OpenOffice文档格式，实际上是zip文件，其中包含特定的目录结构。Infozip是一个开源版本的软件，它的zip实现几乎是所有其他知名压缩软件的基础，如winzip。当我试图破解它时，winzip占据了95%的市场份额。

Eli-Biham和Paul-Kocher已经公布了他们的密码算法中已知的明文攻击，但是已知的明文通常是压缩明文的一部分。为了通过zip加密的压缩文件获得压缩的明文，基本上需要整个文件，所以这种攻击对执法机构来说几乎是无用的。

Zip的加密算法有96位的内部状态，分为三个32位的块，分别是key0、key1和key2。Key0和key2是两组线性反馈移位寄存器CRC32算法的内部状态。如果要用新的数据字节更新状态，则需要将所有字节下移一个字节（放弃低位字节），然后在查找表中用一个常量进行异或。查找表中常量的索引是丢弃的低字节和数据字节XOR，即测试后的结果。Key1是截断线性同余发生器的内部状态。要更新它的内部状态，输入一个数据字节，将它乘以一个常数，我称之为C，然后加1。这种加密算法的工作原理是：先在第一个CRC32中输入一个数据字节，然后把它丢弃的低位字节输入tlcg，再把它生成的高位字节输入第二个CRC32，然后取它的状态并（粗略地）平方，然后输出结果的第二个字节作为流字节。第一个96位的状态是已知的，然后密码被加密，然后十字节的salt被加密。

PKZIP通过直接分配未初始化的内存来获取salt字节，因此它实际上可能包含您运行的其他程序上的某些内容，也可能是图像或文档等。这在windows上运行良好，没有任何问题，但在许多UNIX系统上，分配内存时它会自动初始化。Infozip使用C语言的rand函数选择salt字节。它通过XOR时间戳和进程ID初始化随机数生成器的状态，然后为每个文件生成10个字节。如果他们只这样做，知道时间戳和进程ID就足以恢复部分信息，然后他们就可以发动已知的Biham和Kocher文本攻击。infozip的作者似乎知道这种攻击，因为他们更进一步，用密码加密了头文件。这样，攻击者只有双重加密的明文，他们的攻击不会成功。

我注意到，由于密码是相同的两次，每个密码的第一个流字节是相同的。正如对灯开关的两次操作将使其停留在开始时一样，使用相同的数据流字节异或两次将使其返回原始状态。这使我能够对密文发起非常强大的攻击：给定一个文件中的五个加密文件，我可以在不查看时间戳或不知道进程ID的情况下推断C的rand函数的内部状态。这使我能够生成原始的、未加密的头文件。因为密码的每一部分只有几位会影响下一部分，所以我只能猜测状态的几位，并检查对一个字节解密两次是否给出了预期的答案。随着我的继续，我需要猜测的越来越少，每增加一个文件都会让我排除更多潜在的可能性。当时，这个过程在桌面上花了几个小时。后来我发表了一篇关于这一攻击的论文，发表在2001年日本快速软件加密会议上。

我在2002年离开accessdata，然后在一家神经网络初创公司工作了一年，在奥克兰大学的Cris Calude学习了三年，在加州大学河滨分校的数学物理学家John Baez攻读了计算机科学硕士学位，在谷歌工作了六年之后，在谷歌攻读了博士学位在应用程序安全团队，他完成了博士学位，几年后成为一家初创公司的首席技术官。

比特币敲门

大约半年前，我突然在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次，那就需要几十万年的时间。

我模模糊糊地记得有人用格化简法加密tlcg，所以我把原稿挖出来，发现很完美！我只需要定义一个由2^32和tlcg中的常数幂组成的基向量网格，然后恢复网格。给定恢复的基数，我只需要做一个矩阵乘法，从高位字节恢复原始状态。

至少，我是这么想的。但是我需要5个字节来限制它到一个结果，在攻击点，我只有4个字节。根据本文描述的过程，这很难得出正确答案。然而，我知道答案会非常接近正确的答案，所以我浏览了所有可能的key1值，检查了我的答案和真实答案之间的差异，发现差异总是36个向量中的一个！这是我的优化。通过这种优化，我只能运行36种可能性，而不是40亿。

接下来，我们遇到了在机器上的gpu之间传输数据的问题。我的商业伙伴Nash foster研究了GPU的实现，告诉我不同GPU操作的速度，并为应用程序编写了许多支持结构，将加密代码放入其中。如何将这些Pb级候选密钥发送到GPU进行测试？我突然想到，我攻击的每个阶段都在猜测大量的位，然后在大约65000个候选密钥中只选择了一个。如果我有办法从这些信息中推断出比特，而不是仅仅猜测和检查，我可以节省大量的工作，更重要的是，我可以节省大量的网络流量。但这个想法的问题是数学太复杂了。它涉及到有限域的数学和整数环的数学的混合，这并不容易。

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

我写了一个“中间相遇”攻击，并在我的笔记本电脑上运行了它。以前在我的笔记本电脑上花几个小时，但现在只需要几秒钟。下一阶段，我预计，将需要一个星期的GPU农场，只有几个小时的强大的CPU。我不能让它在第三阶段计算得更快，这有助于加速整体攻击，但它完全避免了移动数据的需要：我们只需要计算每台GPU计算机上的候选组合，让它们运行。Nash编写了GPU代码，运行速度惊人。

这次袭击持续了十天，但失败了。

我很难过。我们错过了哪些候选钥匙？我们回头查看了他笔记本电脑上**的进程ID，发现它比我们预期的要大好几位，所以兰德有其他几种可能的初始种子。我回去做了所有的测试。我们有什么遗漏吗？基于CPU的版本和GPU的版本有什么区别吗？我们的客户重新运行了我们的测试，发现当正确答案在候选列表中排名第二时，GPU版本找不到正确的密钥，但当它****时，就可以找到它。在仔细研究代码之后，我们发现在计算数据结构的数据块索引和线程索引偏移量时，我们交换了块索引和线程索引。

我们修复了错误，重新运行代码，并在一天内找到了正确的密钥。我们的客户很高兴，给了我们很大的奖励，因为我们很快找到了钥匙，而且成本远远低于最初的估计。