应用密码学。我们如何以30万美元的价格恢复比特币

我将与您分享一个故事。大约二十年前，我获得了物理学学位，但是从事反向工程和密码分析。我们的AccessData公司在90年代末和2000年代初开始工作。然后，美国政府逐渐取消了对密码术出口的限制，但是，大多数程序中的密码保护仍然相当无用。我们采用了办公程序，我进行了逆向工程并找出了加密算法，然后破坏了密码保护。

这是无穷无尽的有趣难题，但并不是特别困难的数学难题。我一直写大约40个密码破解程序。我们将其出售给家庭用户，系统管理员以及地方和联邦执法机构。我不得不去了位于格林科的联邦执法培训中心，向特勤局，联邦调查局和ATF的人员讲解了密码学的基本知识以及如何使用我们的产品。

我特别记得两个项目。第一个是Microsoft Word97。在它出现之前，文件使用XOR字节的明文和从密码输出的16字节的字符串进行加密。 Word文件中最常见的字节通常是0x00、0xFF或0x20（空格），因此我们只选择了每一列中最常见的字符并选中了3到^16个选项。密钥恢复通常会立即发生，但是为了使人们不觉得自己在浪费钱，我们插入了一个类似于好莱坞黑客场景的小动画，其中包含很多随机字符，然后逐渐出现正确的密码。

Microsoft Word 97改变了一切。也许MSDN也透露了加密格式，但是我们的小公司买不起。并非事实是我们将被允许在收到信息后编写用于黑客的程序。要理解，在SoftICE中，我在输入密码后立即设置了一个断点，然后缓慢地向上移动堆栈，直到找到算法为止。这是在发布IDA Pro之前，所以我有数十页的打印输出，墙上有一个带有红色标记的汇编代码。终于弄明白了，我感到非常高兴。当时，Microsoft只允许导出40位密码，因此该公司严格执行了严格允许的密码：他们使用“盐”（从文件中随机选择的字节）反复对MD5中的密码进行哈希处理，得到一个40位的密钥，然后向其添加salt并再次进行哈希处理。当时在计算机上进行密码检查大约需要半秒钟。我们不得不使用字典攻击，因为用暴力破解密码几乎是不可能的。结果，我们为大型公司和代理商编写了密码破解程序。该程序使用这些奇特的MMX Pentium指令执行了40位密钥空间的强力攻击。我听说她工作了9个月之后才领取密码。该程序使用这些奇特的MMX Pentium指令执行了40位密钥空间的强力攻击。我听说她工作了9个月之后才领取密码。该程序使用这些奇特的MMX Pentium指令执行了40位密钥空间的强力攻击。我听说她工作了9个月之后才领取密码。

另一个非常有趣的项目是zip存档。 PKZIP的创建者Phil Katz当时做出了一个不寻常的决定来记录其文件格式，并将此文档包含在软件包中，这使ZIP成为开发人员最喜欢的格式。 Roger Schlafly开发了用于加密档案的流密码。 zip标准迅速成为Windows下最流行的标准，许多其他格式（例如.jar java文件和OpenOffice文档）实际上是内部具有特定目录结构的zip文件。该程序的开源版本称为InfoZIP，它是几乎所有专有zip存档程序（例如WinZip）的基础。当我开始入侵WinZip时，它占领了95％的市场。

Eli Biham和Paul Kocher用已知的明文（加密前的文本）发表了关于攻击的描述，但在我们的案例中，已知的明文已存档。要在压缩文件的开头获取霍夫曼代码，您实际上需要整个文件。这次袭击实际上对执法没有用。

密码包含内部状态的96位的拉链，分成3个32位的块称为key0，key1和key2。第一个和第三个是CRC32的两个副本的内部状态，CRC32是具有反馈的线性移位寄存器（允许您创建伪随机序列的简单数学模型）。简而言之，要用新的数据字节更新状态，您将所有内容向下移一个字节（丢弃低字节），然后对转换表中的常量进行XOR，该常量由数据字节索引后与低字节进行XOR。key1截断线性同余生成器（TLCG）的内部状态。要更新其内部状态，我们添加一个数据字节，然后乘以一个常量，我们将其称为c，然后添加一个。密码的工作方式如下：在第一个CRC32中输入数据字节，然后取低字节并在TLCG中输入，然后从高字节中取数据并在第二个CRC32中输入，然后取状态和平方（近似），然后发出第二个字节导致字节流。要初始化内部状态的96位，请从一个已知状态开始并加密密码，然后再加密10个字节的salt。

PKZIP获取其盐字节，在不初始化的情况下分配内存，因此它包含其他正在运行的程序，图像或文档等内容。这在Windows上运行良好，但是在许多Unix系统上，内存在分配时会自动初始化。 InfoZIP使用函数选择盐字节randC语言。他通过对进程ID进行XOR时间戳来初始化随机数生成器的状态，然后每个文件生成十个字节。在这种情况下，在了解时间戳和进程标识符的情况下，理论上可以恢复标头的字节，从而可以攻击Beham和Kocher。看来InfoZIP的作者知道这种攻击是因为他们走得更远了-使用密码对标头进行了加密。因此，攻击者只有两倍的加密明文，并且攻击不会奏效。

我注意到了这一点，因为两次密码都相同，所以流中的第一个字节在每次密码中都相同。以与两次切换电灯开关相同的方式，它保持在开始时的位置，当该字节与相同的流字节重复XOR时，它保持不变。这使我只能对密文进行强大的攻击：在存档中接收到五个加密文件后，我可以输出函数的内部状态rand无需查看时间戳或知道进程ID。然后，我可以生成原始的未加密头。由于密码的每个部分中只有几位会影响下一部分，因此我还可以猜测状态的几位，并检查两次解码下一个字节是否给出了我期望的答案。随着前进，我不得不猜测越来越少的钥匙。每个附加文件还允许排除更多潜在的关键材料；当时，在一台台式机上花了几个小时。我发表了一篇有关此的文章，并有机会在日本的Fast Software Encryption 2001大会上进行介绍。

不久，我离开了AccessData，在神经网络初创公司工作了一年，并花了三年时间与Chris Kaloud在奥克兰大学攻读计算机科学硕士学位，并在加州大学河滨分校的数学物理学家John Baez开始了我的博士学位研究，工作了六年作为Google应用安全团队的一员，他完成了博士学位，几年后成为了这家新公司的CTO。

大约半年前，我很意外地收到一个俄罗斯人在LinkedIn上发来的消息。他读了我19年前写的文章，想知道这种攻击是否可以在仅包含两个文件的存档中起作用。快速分析表明，它需要大量的计算能力和金钱。由于只有两个文件，因此在选择的每个阶段都会有更多的误报。结果是有^2,773个可能的测试密钥，将近10兆。我计算出，GPU上的大型群集可以使用一年，其成本约为10万美元。他打了我，说他同意花那么多钱来恢复钥匙。

事实是，在2016年1月，他以大约10至1.5万美元的价格购买了比特币，并将密钥放置在加密的zip文件中。现在他们花费了超过30万美元，他不记得密码了。幸运的是，他仍然拥有原始笔记本电脑，并且他确切地知道加密时间。由于InfoZip基于时间戳输出熵，因此这有望将可能的关键选项数量“仅减少”至10亿五千万，并且使攻击在平均一个GPU场上数月之内变得十分可行。我们签了合同，我开始工作。

我花了一些时间来恢复本文所述的攻击。令我感到恼火的是，我在文章中错过了一些棘手的细节，但我再次加以解决。然后我发现在评估计算量时犯了一个严重的错误！

在我最初的攻击中，我猜到了密钥key1·c，key1·c ²，key1·c ³和key1·c ⁴的高字节。当我猜到第四个字节时，我知道了其余密码的完整状态。我只需要将这四个字节转换为原始的key1即可。我将遍历key1的32位状态空间，并检查每一个状态空间是否提供正确的高字节。但是，这里必须检查5百万个密钥。如果您需要每次进行2 ^32次测试，则将花费数十万年。

我隐约地记得，通过减少晶格基础已经在TLCG密码分析上做了一些工作，因此我挖了原始文章。原来如此！只需用2 ³²给出的基矢量和TLCG的常数来确定晶格，然后对晶格的基进行约简。在简化的基础上，我可以通过简单地将矩阵相乘来从高字节中恢复原始状态。

至少那是主意。花了五个字节才能得到唯一正确的结果，那时我只有四次攻击。本文中描述的过程很少给出正确的答案。但是，我知道答案应该接近正确的答案，所以我可以遍历key1的所有可能值并检查真实答案和真实答案之间的差异。差异一直是36个向量之一！通过这种优化，我可以将搜索减少到36个选项，而不是40亿个。我们仍在营业。

此外，我们还面临着使用GPU在机器之间传输数据的问题。我的业务伙伴Nash Foster参与了GPU的实现。他告诉我各种操作的执行速度，并用我的密码破解代码编写了该应用程序的大多数支持结构。如何获得这些PB级的候选密钥进行GPU测试？他们几乎总是无所事事，在工作预期中丢掉了自己的核心。我想到，在攻击的每个阶段都要检查很多位，然后保存大约6.5万名候选人中的只有一个。如果我能找到某种输出方式这些位基于可用信息，而不仅仅是强行使用它们，我可以节省大量工作，更重要的是，可以节省大量网络流量。这里的问题是算法太复杂，表示有限域与整数环的混合，但它们彼此之间不太吻合。

我想到了我所知道的其他密码分析攻击。其中之一是“中间相遇”攻击。她似乎是一个有前途的候选人。当攻击使用一部分密钥材料执行第一部分加密，而另一部分进行第二部分加密时，该攻击将应用于分组密码。这适用于zip密码，但是密钥材料远远超过了中间的位数。然后发生在我身上，如果我们使用CRC32的线性度呢：如果我们对最后一个CRC32的两个输出执行XOR操作，那么结果将独立于key2！代替计算密码的中间状态并将其存储在表中，我将计算两个中间状态的XOR并将其存储。

我写了一个不同的会议“中间会议”，并在笔记本电脑上启动了会议。该阶段过去需要几个小时，现在仅需几秒钟即可完成。下一阶段（可能需要一个星期在GPU场上进行）在一个功能强大的CPU上花费了几个小时。我无法充分优化攻击的第三阶段以影响整体速度，但是没有必要完全移动数据：我们只是使用这些卡来计算计算机上每个GPU的候选对象。 Nash编写了以惊人速度运行的GPU代码。

攻击持续了十天，以失败告终。

我的心碎了。我们是否缺少可能的钥匙之一？我们回头查看了他笔记本电脑上的最大进程标识符，发现它比我们预期的多了几位，因此有更多的可能的源种子rand。我还仔细检查了所有代码。也许我们错过了什么？也许CPU上的版本与GPU上的版本有所不同？最终，我发现GPU上的版本在候选列表中仅次于候选列表时找不到正确的密钥。通过对代码进行汇总，我们发现在计算数据结构中的偏移量时，我们将块索引与流索引混淆了。

我们更正了该错误，重新运行了代码，并在一天内找到了正确的密钥。我们的客户非常满意，并给了我们很大的收获，因为他能尽快找到钥匙并为他节省了超出我们最初估计的大量资金。

现在我正在找工作。如果您在技术分析或优化方面遇到有趣的问题，请告诉我。

---