Polynonce：新型ECDSA攻击与比特币的泪水

引言

在这篇博客文章中，我们讲述了如何发现一种针对ECDSA的新型攻击方法，并将其应用于实际数据集，包括比特币和以太坊网络。虽然我们未能恢复中本聪的私钥（否则我们正在开派对而不是写这篇博客），但我们发现了有人之前使用不同漏洞攻击脆弱钱包并清空它们的证据。我们涵盖了研究过程、发现以及探索的细节。我们还提供了一篇学术论文详细说明攻击方法，并开源了实现代码，以便使用ECDSA构建软件和产品的组织能够确保系统不存在此漏洞。

新型攻击

Kudelski安全研究团队的部分活动包括研究新漏洞和利用方法。几个月前，在研究ECDSA nonce攻击时，我们团队的一名成员发现了一种更通用的方法，利用nonce之间的复杂关系来恢复签名密钥。对现有文献的回顾证实这确实是一个新颖的见解，因此我们开始深入研究。如果您对攻击涉及的数学和细节感兴趣，这里是论文链接。

简而言之，该攻击基于这样一个事实：您总是可以将不同ECDSA签名中使用的nonce之间的递归关系定义为任意高次的多项式，具有未知系数，模曲线生成点的阶。如果您有一组N个ECDSA签名（针对同一私钥），并且此递归关系的度为D，那么（在某些注意事项下，我们稍后会讨论）您可以使用ECDSA签名方程以私钥和递归未知系数重新编写多项式。我们发现未知系数可以从多项式中消除，该多项式总是将签名者的私钥作为其根之一。因此，如果D较低，并且您有足够多的此类相关签名（N ≥ D+3），那么您可以通过在有限域上找到具有已知系数的多项式的根来执行密钥恢复攻击，这在计算机上是一项简单的任务！要在实践中运行攻击，需要以下条件：至少4个由同一私钥生成的签名、相关的公钥以及与每个签名相关的消息哈希。如果nonce遵守递归关系，我们就能恢复用于生成脆弱签名的私钥。攻击中使用的签名越多，速度越慢，但成功的可能性越大：如果您攻击N个签名，并且它们的N个nonce遵循最多N-3次的递归关系，那么您就可以对ECDSA执行密钥恢复攻击！

我们在特制的签名集上测试了攻击以验证其有效性。您可以在找到概念验证代码。

严重性如何？

简单来说，我们的攻击意味着每次生成ECDSA签名时，签名本身都给出了nonce和私钥之间的关系。如果nonce是真正随机生成的，这应该永远不会成为问题，因为随机选取的多个nonce符合低次多项式递归关系的概率微乎其微。

但有一个问题：nonce通常由伪随机数生成器（PRNG）输出，而不是真正随机的，而PRNG是确定性算法，复杂度相对较低。在最佳情况下，使用的PRNG足够复杂且密码学安全，这意味着其输出之间的任何多项式相关性都将具有天文数字般的高次，您可以安全地认为它与真正随机无法区分。但弱PRNG基本上无处不在。例如，线性同余生成器（LCG）是PRNG实现的典型教科书介绍。LCG对PRNG就像ROT13对加密和“1234”对安全密码一样。尽管如此，由于其简单性和普及性，它们是许多非关键安全应用程序的默认选择，并且完全有可能一个“占位符”LCG实现滑入生产代码而未被更安全的替代。

更令人担忧的是，让我们看看最近对NIST SP 800-22文档的批评。该出版物在附录D中包含一系列“参考随机数生成器”，这些生成器显然不适合密码学用途，包括LCG和其他依赖简单二次或三次递归的弱生成器，如果模曲线生成点阶定义，可能会受到我们的攻击影响。然而，要利用此弱点进行攻击，我们需要一批连续且有序的ECDSA签名（意味着nonce是同一PRNG的连续输出，并且您知道这些签名的生成顺序）。

SP 800-22还包括一系列测试，这些测试显然未能检测到相对容易的密码分析可以证明的简单偏差。因此，NIST决定修订此出版物，但有多少实现仍然遵循旧指南？而且，即使指南被修订，研究人员已经清楚地表明，过去和现在在实际使用中的PRNG往往不遵循最佳实践；例子包括具有公因子的RSA密钥、非均匀生成的素数和密钥、用于比特币交易签名的ECDSA小值nonce和密钥、具有公共前缀的nonce等。因此，总结来说，我们认为有理由预期我们的攻击可能会影响某些实现，但要使攻击生效，我们需要连续且有序的ECDSA签名。我们在哪里可以找到大量这样的签名？

比特币！

比特币区块链基本上是一个大型、公开的ECDSA签名矿。事实上，自2009年比特币创建以来，ECDSA一直被用作默认签名算法。我们知道，原则上，比特币网络中的大多数ECDSA签名都是短暂的，因为生成密钥仅使用一次，但我们也知道这种实践并不总是到位，尤其是对于较旧的交易，而且比特币的优势在于区块遵循时间历史，这对签名生成时间施加了一定程度的顺序（只是近似，因为无法确定同一区块中签名的生成顺序，因为时间戳仅记录区块，而不是每个签名）。

问题在于这些主要是我们的推测，我们不知道所有这些推测的准确性如何。所以，是时候验证了。

我们下载并安装了比特币核心官方客户端，并让其同步整个链。同步过程在快速光纤连接上花费了大约一天时间，总区块链大小约为430 GB，截至2022年9月5日的752,759区块。我们分叉了rusty-blockparser并添加了代码来转储所有P2PKH交易的ECDSA签名和原始签名消息。还有其他类型的比特币交易，例如P2WPKH，但为了简单起见，我们只关注这些。转储所需数据的一个困难是计算正确的原始签名消息。此消息从不包含在交易本身中。比特币客户端需要根据链中存储的信息位重新计算消息。更精确地说，交易中的每个输入都被签名，因此每个交易可能有多个签名。要构建此消息，必须使用先前交易的信息。为确保我们正确构建消息，我们在转储签名时使用构建的消息验证所有签名。如果签名验证失败，我们会立即知道有问题。我们构建正确原始消息的源代码可在此处找到。

此任务非平凡的另一个原因是缺乏关于构建正确消息的适当文档。比特币维基包含一个带有图的页面。点击此图后，会显示预览，下方评论指出该图包含两个错误！感谢详细的StackExchange答案和大量试错，我们获得了正确的消息，并且签名得以验证。

从原始区块链数据正确转储所有签名和原始消息花费了24小时。生成的输出文件大小为271 GB，包含763,020,390个唯一签名。此文件每行包含以下信息：输出地址、ECDSA签名R和S值、公钥、交易ID、原始消息和区块时间戳。我们按公钥对签名进行分组，然后在每个组内按时间戳对签名进行排序，以增加选择连续签名的机会。此时，我们有了一个准备运行攻击的数据集。但首先，以下是关于数据集的一些统计信息。

这些签名由与424,549,744个唯一公钥关联的私钥产生。在这4.24亿公钥中，3.9亿（约92%）仅产生1个签名。有3400万公钥至少有2个签名，1800万至少有3个签名，1200万至少有4个签名，960万至少有5个签名，780万至少有6个签名。有相当数量的公钥拥有超过20万个签名。与最多签名关联的公钥有340万个签名。下图说明了这一点。请注意，y轴使用对数刻度。

攻击是通用的，可以至少使用N=4个签名（线性情况）运行，但也可以使用更多签名运行，例如5个签名用于二次情况，6个签名用于三次情况，甚至更多签名。线性情况也会检测重复的nonce，但更通用，因为它可以利用任何线性递归关系。然而，我们想更进一步，运行二次情况（N=5），因为我们认为它可能会给出更有趣的结果。我们认为执行三次或更高次攻击的成本效益比不值得，因此我们停止在二次情况，意味着5个签名的批次。由于我们有时有超过5个与给定公钥关联的签名，我们决定在按时间戳排序的签名上执行滑动窗口，并在每个大小为N的窗口上运行攻击。

那么，结果如何？

我们在128核VM上运行了N=5的滑动窗口攻击，并在2天19小时内完成。攻击的估计成本约为285美元。我们破解了762个唯一钱包。所有这些钱包余额为零。有趣的是，我们能够破解所有这些钱包，不是因为线性或二次递归，而是因为签名中至少有一个重复的nonce。因此，看起来ECDSA实现使用重复nonce的常见失误是问题的原因。

由于我们到目前为止只使用大小为5的窗口运行攻击，我们可能错过了一些脆弱钱包，这些钱包可能只在公钥恰好有4个签名时被发现。因此，我们重新运行了N=4的攻击，仅针对恰好有4个签名的钱包的签名。我们能够破解11个新的零余额钱包，并且至少有一个重复nonce，从而将破解钱包总数增加到773。

我们怀疑（并且在某些情况下有证据，如我们稍后讨论）所有这些钱包余额为零，因为它们过去由于重复nonce漏洞已经被黑客攻击。我们还估计从这773个钱包中被盗的代币总理论量为484 BTC，按比特币峰值计算价值约3100万美元。

受损的比特币钱包与1idiot

我们的一个问题是，钱去了哪里？谁偷了代币？为了回答这个问题，我们获取了每个破解钱包地址的最新交易列表。我们按时间倒序浏览这些交易。一旦找到实际发送代币的交易，我们假设这是清空被攻击钱包的交易。我们假设一旦钱包被破解并从中窃取代币，受害者之后就不再使用他们的钱包。这可能不完全准确，但我们认为这是一个合理的假设。我们考虑的一个保障是丢弃2022年9月5日之后发生的任何交易，因为这是我们转储链上交易的时间，因此我们的数据集已经那么旧。

查看破解钱包的目标比特币地址列表，我们看到一些地址包含人类可读的单词，可能是比特币虚荣地址。例如，一个地址以“1idiot”开头。这立即引起了我们的注意。以下是按从脆弱钱包发送的比特币总量排序的目标地址列表摘录，以及使用比特币峰值汇率65,000美元/BTC的近似美元等价金额。

我们确定了466个不同的地址或公钥，代币被发送到这些地址。顶级地址显然接收了多达75 BTC，而排名较低的地址有时只接收了几聪。总共，我们计算出144 BTC（或按上述USD/BTC汇率计算的940万美元）被盗，这少于我们之前提到的总理论量484 BTC，这在我们看来是合理的。

在上述前15名中，有2个非地址类型的目标，排名第7和第11。这些是公钥。这意味着资金不是发送到地址，而是发送到公钥（P2PK交易类型）。找出这类交易资金去向更具挑战性，因为我们必须再次索引整个链，看看是否有交易后来重用该输出作为输入。我们尝试的各种公共比特币区块链浏览器未提供该信息，或者似乎不可靠。我们没有进一步跟踪这些公钥。

在同一列表中，我们注意到这些似乎是虚荣地址：

排名 #12: 1idiott6U6jsgYg… 排名 #31: 1eouxuruZ7Qz64Y… 排名 #63: 1KgiftfVXuKffFZY… 排名 #93: 1dust8J4MJjfn6F… 排名 #157: 1HackfRHUGxpDAX…

注意这些比特币地址中出现的单词，如“idiot”、“gift”、“dust”或“Hack”。由于比特币地址通常是匿名的，除非有人能证明他们拥有特定地址，否则没有适当的链分析技术极难确定谁移动了这些资金。尽管如此，我们更深入地调查了这些地址并收集了以下信息。

1idiot

该地址涉及26笔交易。资金在2017年发送到此地址，这似乎表明资金在当时被盗。此地址现在余额为零，并于2018年1月22日将其所有资金发送到另一个名为“1andreas”（1andreas3batLhQ…）的虚荣地址。在撰写本文时，1andreas地址余额为0.036 BTC。请注意，该地址恰好由Andreas Antonopoulos拥有，他显然在2017年底收到了超过100 BTC的未经请求的捐款。这意味着1idiot钱包的未知所有者可能决定捐赠他们从脆弱钱包收集的代币。

从我们识别的脆弱钱包中，1idiot地址总共收到了0.04 BTC。

1eouxuru

该地址涉及17笔交易。资金在2014年发送到此地址。所有资金都发送到1EDLS地址，该地址令人惊讶地在上表中排名第2。资金随后进一步发送到一长串地址，这使得跟踪变得困难。我们认为此地址可能与某个加密货币交易所的地址有关，因为它移动了大量资金。

从我们识别的脆弱钱包中，此地址总共收到了0.01 BTC。

1Kgift

该地址仅涉及2笔交易，发生在2015年。看起来跟随此地址形成的一长串地址导致某个加密货币交易所（3BT57Z3DXs5Tbeaqe31EZLUbc4fDDrYGHm）。这可能表明攻击者在某个时候兑现或将代币进一步发送。

从我们识别的脆弱钱包中，此地址总共收到了0.006 BTC。

1dust

此地址涉及大量交易，准确地说