比特币和以太坊的无格半半攻击
公共区块链在ECDSA签名方面有着悠久的攻击历史。由于所有交易都是公开的，这为密码学攻击提供了一个完美的实验场。最近，一种名为“半半比特币ECDSA随机数的奇异案例”的格攻击被发布，并在比特币上进行了实验。作为一个喜欢半半奶酪火锅的瑞士团队，我们必须调查这种攻击。我们发现我们之前的攻击“Polynonce”也适用于这种生成ECDSA随机数的方式。我们在这篇文章中解释了如何操作，并展示了与论文相比我们获得的结果。
之前的攻击
为了对消息进行签名，ECDSA使用一个称为随机数（nonce）的值。随机数必须随机生成，并且对于每个要签名的消息都是唯一的。对于比特币和以太坊的secp256k1曲线，典型的随机数值如下：
|
|
ECDSA有一个众所周知且经过充分研究的常见缺陷，即随机数重用。顾名思义，如果一个随机数被重用于不同的签名，则可以从这些签名中恢复私钥；显然，应用于区块链的第一个攻击是随机数重用攻击。一旦两个不同的消息使用相同的随机数进行签名，私钥就会被泄露。这个问题通常通过遵循RFC 6979生成确定性随机数来解决。
然而，ECDSA随机数非常关键，即使其生成存在偏差也会导致私钥恢复。因此，后来更聪明的攻击被应用于涉及格攻击的公共区块链。这些攻击允许恢复比预期短的随机数，长度分别为64、110、128和160位。例如，像下面这样生成的随机数容易受到格攻击：
|
|
随机数越小，用于攻击的格的维度就越小，成功攻击所需的签名数量也越少。根据“Bias nonce sense”论文，两个具有128位随机数和3维格的签名有75%的成功概率（密钥恢复）。从三个具有170位随机数和4维格的签名中，我们获得95%的成功概率，依此类推。攻击的一个变体也适用于发现具有共享前缀和后缀的随机数。例如，像下面这样生成的随机数也容易受到先前攻击以及常见后缀构造的攻击：
|
|
Polynonce
另一种攻击ECDSA的方法是假设随机数之间存在代数关系。我们的团队通过Polynonce攻击提出了这种方法。它假设连续随机数 ( k_i ) 和 ( k_j ) 之间存在多项式关系，对于未知系数 ( a, b, c, \ldots )，形式为：
[ k_j = a \cdot k_i + b ]
或者
[ k_j = a \cdot k_i^2 + b \cdot k_i + c ]
然后，Polynonce攻击能够以100%的成功概率代数恢复私钥，但在线性情况下需要4个签名，二次情况下需要5个签名，依此类推。该攻击主要依赖于求解多项式方程，因此与格攻击相比非常快。更多细节，该攻击将在即将举行的DEFCON会议上展示。
单签名
所有先前的攻击都至少需要来自同一私钥的两个不同签名。然而，一些钱包如Ledger使用单个私钥对交易进行签名，然后更改它。这可以解释为什么如今许多比特币公共地址只使用一次。以下是比特币（截至2022年9月5日区块752759）的P2PKH交易转储的对数比例图：
这表明，用于P2PKH交易的92%的公钥只使用一次。这一特性主要是为了保护隐私而引入的，但间接地也保护了免受先前的攻击。对于以太坊，情况略有不同。我们分析了来自151429561个唯一密钥的1759432087个签名，并制作了线性比例图：
这相当不同：42%的公钥用于单个签名，22%用于两个签名，13%用于三个签名，依此类推。因此，隐私保护方法的使用在以太坊上似乎部署较少或适用性较低。
半半随机数
最近，一种新的攻击在随机数由消息哈希的上半部分与私钥的上半部分连接生成时呈现结果。这意味着随机数 ( k ) 可以写为：
[ k = \text{msb}{128}(H(m)) | \text{msb}{128}(d) ]
这种攻击的新颖之处在于它允许从单个签名恢复密钥 ( d )。与先前的格攻击类似，( k ) 的表达式可以注入ECDSA公式，重新排列以形成隐藏数问题（Hidden Number Problem）的实例。然后使用BKZ算法解决这个实例。这种技术非常强大，因为单个签名就足够了，并且允许攻击应用于仅使用一次的私钥发出的交易。攻击的优化版本能够在0.48秒内以99.99%的成功率恢复私钥。这非常强大，但作者在比特币区块链上运行攻击花费了49个CPU年。
Polynonce应用于半半随机数
在阅读新的半半攻击时，我们发现Polynonce也可以适用于恢复使用半半随机数的私钥。从ECDSA签名 ( (r, s) )、消息哈希 ( H(m) ) 和私钥 ( d )，我们有以下关于随机数的关系：
[ k = s^{-1}(H(m) + r \cdot d) \mod n ]
如果我们有两个使用先前半半公式生成的随机数 ( k_1 ) 和 ( k_2 )，如果我们取差值，我们得到：
[ k_1 - k_2 = \text{msb}{128}(H(m_1)) - \text{msb}{128}(H(m_2)) ]
我们找到了一个关于 ( d ) 的线性方程，所有其他值已知。它提供了一种非常快速的求解方程和恢复私钥 ( d ) 的方法。然而，使用Polynonce，需要两个随机数，因此需要来自同一私钥的两个签名。我们失去了相对于先前攻击的一个巨大优势。尽管如此，由于这种攻击变体非常快，它可能首先应用于具有多个签名的公钥，然后格攻击可以应用于剩余的签名。
由于我们方程中的随机数差值仅取决于 ( H(m_1) ) 和 ( H(m_2) )，它允许我们恢复所有使用公式 ( k = c | \text{msb}_{128}(d) ) 生成的随机数，其中 ( c ) 是一个（秘密）常数。这稍微更通用，但对比特币来说有一个轻微的复杂情况。从ECDSA签名 ( (r, s) )，不同的签名 ( (r, -s \mod n) ) 对同一消息也有效。由于比特币拒绝具有较大 ( s ) 值的签名以避免签名伪造，这有一个缺点，即我们必须同时使用 ( s ) 和 ( -s \mod n ) 进行计算。因此，在我们的攻击中，我们必须猜测每个随机数的符号。
这种构造也应该被先前的共享后缀格攻击发现，但只有75%的成功机会。
结果
我们在之前分析中使用的比特币区块链转储上运行了分析（截至2022年9月5日区块752759）。我们分析了3400万个至少具有2个签名的公钥。在16核AMD 2.7 GHz时钟的机器上花费了10分23秒。
我们能够找到并恢复110个唯一私钥。例如，地址18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7的交易f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981和f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8使用半半方法生成随机数。我们的脚本能够恢复该地址的私钥：
|
|
如果我们然后重新计算这些交易的随机数，我们得到：
|
|
我们清楚地看到随机数的最低有效半部分等于私钥的最高有效半部分。然而，如上所述，我们能够恢复其他有趣的案例；对于同一地址，我们找到了两个随机数：
|
|
在这种情况下，私钥不涉及，因为我们找到了另一个未知常数。我们还能够确认先前的发现，即一些使用此类随机数的密钥是小密钥：( d < 2^{40} )。因此，密钥通过暴力破解容易恢复，类似于在网站https://privatekeys.pw上所做的。我们没有找到具有非零余额的账户，就像先前的攻击一样，我们认为这些账户被机器人监控，并在余额每次变化时被清空。
由于这种攻击相当快，我们还对其进行了半半随机数生成的变体运行：( k = \text{msb}{128}(d) | \text{lsb}{128}(H(m)) )、( k = \text{lsb}{128}(H(m)) | \text{msb}{128}(d) ) 和 ( k = \text{lsb}{128}(d) | \text{msb}{128}(H(m)) )，但我们没有找到额外的结果。
我们还在先前攻击期间收集的以太坊数据集上运行了相同的攻击。攻击在同一台机器上花费了49分11秒。没有私钥通过这种攻击被恢复。
结论
看到过去随机数生成构造的创造性很有趣，我们想知道野外是否存在任何其他奇异的构造。尽管这些新攻击没有恢复新的私钥，但这并不意味着其他弱随机数生成算法已被用于先前的交易，并且可以通过类似的方法恢复。如果发现此类问题，保护资金的最佳方法是将它们转移到一个以前未用于交易的新地址，并留下易受攻击的地址为空。我们攻击的脚本和我们获得的结果可在Polynonce攻击的Github存储库中找到。
致谢
特别感谢我的同事Marco Macchetti和Nils Amiet，感谢他们的原始攻击、想法以及通过富有成果的讨论为这篇博客文章做出的贡献。