作者：Sylvain Pelissier 编译：Cointime.com 237

公共区块链在其ECDSA签名方面存在长期的攻击历史。由于所有交易都是公开可见的，这为密码学攻击提供了一个完美的实验场。最近发布了一种名为“半比特币ECDSA随机数的好奇案例”的格攻击，并对比特币进行了实验。作为热爱半比和半比奶酪火锅的瑞士团队，我们必须调查这种攻击。我们发现我们先前的攻击，“多项式随机数”，也适用于这种生成ECDSA随机数的方式。我们在本文中解释了如何操作，并展示了我们与论文所得结果的对比。

先前的攻击

为了签署一条消息，ECDSA使用一个称为随机数（nonce）的值。随机数必须是随机生成的，并且对于每个要签名的消息都必须是唯一的。对于比特币和以太坊的secp256k1曲线，典型的随机数值如下：

ECDSA存在一个众所周知且广为研究的常见陷阱，即随机数（nonce）重用。顾名思义，如果一个随机数在不同的签名中被重复使用，那么私钥可以从这些签名中恢复出来；显然，首先应用于区块链的攻击就是随机数重用攻击。只要两条不同的消息使用相同的随机数进行了签名，私钥就会泄露。通常通过按照RFC 6979生成确定性随机数来解决这个问题。

然而，ECDSA随机数非常关键，即使在它们的生成过程中有偏差也会导致私钥被恢复。因此，后来在公共区块链上应用了更巧妙的基于格的攻击。这些攻击可以恢复比预期长度更短的随机数，长度分别为64、110、128和160位。例如，像下面这样生成的随机数容易受到基于格的攻击的影响：

随机数越小，用于攻击的格的维度就越小，成功攻击所需的签名数量也越少。根据《偏差随机数》论文，两个128位随机数和一个3维格给出了75%的成功概率（私钥恢复）。当使用三个170位随机数和一个4维格时，我们可以获得95%的成功概率，以此类推。攻击的变体还适用于发现具有共享前缀和后缀的随机数。例如，像下面这样生成的随机数同样容易受到前述攻击和常见后缀构造的影响：

Polynonce

攻击ECDSA的另一种方式是假设随机数之间存在代数关系。我们团队提出了Polynonce攻击，它假设未知系数a_i间存在一个多项式关系，形式如下：

k_{n+1} = a_1 k_n + a_0

或者

k_{n+1} = a_2 k_n^2 + a_1 k_n + a_0

然后，Polynonce攻击能够以100%的成功概率通过代数方法恢复私钥，但线性情况下需要4个签名，二次情况下需要5个签名，以此类推。该攻击主要依赖于解多项式方程，因此与基于格的攻击相比非常快速。有关更多详细信息，该攻击将在即将举行的DEFCON会议上进行介绍。

单个签名

所有先前的攻击都需要至少两个来自同一私钥的不同签名。然而，像Ledger这样的钱包会使用单个私钥签署交易，然后更换私钥。这可以解释为什么现在很多比特币公共地址只使用一次。下面是一个以对数刻度绘制的比特币转账数据图（截至2022年9月5日，区块752759）限定为P2PKH交易：

这显示了92％用于P2PKH交易的公钥仅使用一次。此功能主要是为了保护隐私，但间接地也保护了免受先前攻击的影响。对于以太坊而言，情况有些不同。我们分析了1759432087个签名，来自151429561个唯一密钥，并制作了线性刻度图：

这是相当不同的情况：42%的公钥仅用于单个签名，22%用于两个签名，13%用于三个签名，以此类推。因此，似乎隐私保护方法在以太坊上的应用较少或不适用。

半半随机数

最近出现了一种新的攻击方法，当随机数使用消息哈希的上半部分与私钥的上半部分连接时，会产生一些问题。换句话说，随机数k可以表示为：

k = h_{msb} || d_{msb}

这种攻击的创新之处在于，它允许从单个签名中恢复出私钥d。类似于先前的基于格的攻击，将随机数k的表达式注入到ECDSA公式中，并重新排列以形成一个隐藏数字问题的实例。然后使用BKZ算法解决该实例。这项技术非常强大，因为只需要一个签名，就能对仅使用一次的私钥发出的交易进行攻击。经过优化的攻击版本能够在0.48秒内以99.99%的成功率恢复私钥。这相当强大，但作者花费了49个CPU年的时间在比特币区块链上运行该攻击。

对半半随机数应用Polynonce

在阅读关于半半攻击的内容时，我们发现Polynonce也可以用于恢复使用半半随机数的私钥。对于一个ECDSA签名(r, s)，一个消息哈希h和一个私钥d，我们有以下与随机数相关的关系：

k = s^{-1}(h + rd) mod q

如果我们有两个使用先前的半半公式生成的随机数k_0和k_1，它们的差值为：

k_0 - k_1 = s_0^{-1}h_0 - s_1^{-1}h_1 + (s_0^{-1}h_0 - s_1^{-1}h_1)d = h_{0,msb} - h_{1,msb}

我们发现了d的一个线性方程，其中所有其他值已知。这提供了一种非常快速解决方程和恢复私钥d的方法。然而，使用Polynonce需要两个随机数和来自同一私钥的两个签名。相比之前的攻击，我们失去了一个巨大的优势。尽管如此，由于这种攻击变体非常快速，可以首先对具有多个签名的公钥使用它，然后再对剩余的签名使用基于格的攻击。

由于我们方程中的随机数差值仅取决于h_{0,msb} - h_{1,msb}，这使我们能够恢复使用公式k_i = h_{i,msb} || c（其中c是一个（秘密）常量）生成的所有随机数。这更加通用，但对于比特币来说稍微有些复杂。从ECDSA签名(r, s)出发，相同消息的不同签名(r, -s)也是有效的。由于比特币拒绝具有最大s值的签名以避免伪造签名，这意味着我们必须同时计算-k和k。因此，在我们的攻击中，我们必须猜测每个随机数的符号。

这种构造应该也被先前对共享后缀进行格攻击的研究所发现，但成功率只有75%。

结果

我们对比特币区块链转储文件进行了分析，该文件是我们之前分析中使用的（截至2022年9月5日的第752,759个区块）。我们分析了至少具有2个签名的3400万个公钥。在一台16核心、2.7 GHz时钟的AMD处理器上，耗时10分23秒。

我们成功找到并恢复了110个唯一的私钥。例如，地址

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

的交易

f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981

和

f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8

使用半半方法生成随机数。我们的脚本能够恢复该地址的私钥：

如果我们重新计算此类交易的随机数，我们将得到：

我们清楚地看到随机数的最低有效一半等于私钥的最高有效一半。然而，如上所述，我们能够恢复其他有趣的案例；对于同一个地址，我们发现了两个随机数：

在这种情况下，私钥并没有涉及，因为我们实际上是找到了另一个未知的常数。我们还能够证实先前的发现，一些使用这种随机数的密钥是小密钥：d = {1, 2, 4, 7, 11, 24, 75, 77, 87, 128, 144, 549, 897}。因此，这些密钥可以通过穷举法轻松恢复，类似于网站https://privatekeys.pw上所做的工作。我们没有找到余额非零的账户，我们认为这些账户被机器人监控，并在余额变动时被清空。

由于这种攻击非常快速，我们还对半半随机数生成的其他变体运行了相同的攻击：k = h_{lsb} || d_{msb}、k = d_{msb} || h_{msb}和k = d_{msb} || h_{lsb}，但我们没有发现额外的结果。

我们还对之前攻击期间收集的以太坊数据集运行了相同的攻击。该攻击在同一台机器上耗时49分11秒。这次攻击没有恢复任何私钥。

过去各种创造性的随机数生成构造方法非常有趣，我们想知道是否还存在其他奇特的构造方法。尽管这些新攻击没有恢复新的私钥，并不意味着先前的交易中没有使用其他弱随机数生成算法，也不意味着可以通过类似的方法进行恢复。如果发现此类问题，保护资金的最佳方式是将其转移到之前未用于交易的新地址，并将存在漏洞的地址保持空置。我们的攻击脚本和我们获得的结果可在Polynonce攻击的Github存储库上找到。