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

技术的突破是推动区块链行业前进的引擎,币安中国区块链研究院与链闻 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

原创文章,作者:币安区块链研究院,如若转载,请注明出处:http://www.lianchaguan.com/archives/33873

发表评论

电子邮件地址不会被公开。 必填项已用*标注