其中最粗暴的方式，就是通过穷举的方式暴力碰撞比特币私钥，Large Bitcoin Collider(LBC)就是这样的一个组织，其使用了明显线性的暴力搜索算法，而这样的方法，在量子计算没有得到实质性进展前可以说是比较愚蠢的。

而对于已泄露的公钥而言，使用平方根离散对数算法，则是恢复这类短私钥的更为有效的方法，而来自宾夕法尼亚大学的博士后研究员 Joachim Breitner 和来自加利福尼亚大学计算机科学与工程学院的副教授 Nadia Heninger，则联合进行了一项称为《针对密码货币弱 ECDSA 签名的点阵攻击》的研究。

在这项研究中，我们看到比特币、以太坊和瑞波区块链，以及 HTTPS 和 SSH 中的私钥，会有数种不安全的使用方式，因而它们可能会被破解。由此产生的数字并不大，在实验中，研究者共计算出了 300 多个比特币私钥(余额约为 0.00818975 BTC)，以及 30.40 XRP，但实验却告诉我们，想要正确使用密码货币，其实是一件非常棘手的事情，如果你做得不对，那么你很可能会丢失资金。

当你使用 ECDSA(椭圆曲线数字签名算法)创建密码学签名时，你需要提出一个 256 位随机数的 nonce。每一次签名时，使用不同的 nonce 是非常重要的，否则其他人很容易能拿到你的签名，并使用相对简单的数学计算你的私钥，而有了你的私钥，他们就可以花掉你所有的比特币。实际上，有证据表明：一直有人在监视区块链上是否存在这种重复的 nonce，如果检测到，他们就会计算出相应私钥，并从中提取资金。

这种攻击方式知道的人并不多，但对于密码学社区而言，这并不是什么新的东西，攻击者可以根据使用不同，但相似的 nonce 计算私钥：例如，如果它们彼此靠近(只有低位不同)，或者它们的差别正好是 2 的大幂(只有高位不同)。这使用了一种基于点阵(lattices)的强大技术。这篇论文的主要贡献，在于连接了密码学和密码货币，看看这些漏洞是否真实存在。

事实上，密码货币当中的确存在这样的漏洞，好在数量并不是很多，但它们确实存在着，而且显示是有多个来源。不幸的是，我们很难找出是谁做了这些签名，以及用了什么代码，所以我们只能猜测这些错误的原因。大量受影响的签名与多重签名交易有关，因此，我们认为，硬件 token 可能是导致这种情况的原因。

尽管我们无法确定导致这些问题的具体实现，但我们仍然可以观察到一些关于它们的有趣细节。最让人好奇的，当然是这个：

其中一组签名是由一个攻击者创建的，其清空了泄露密钥的账户(例如那些使用弱密码创建的，或以其他方式泄露到互联网上的私钥)。

因此，看起来很像攻击者建立了一个监控区块链的程序，其会清空已泄露的账户。

我们需要担心吗？

大概不需要。官方的区块链客户端在这方面做得很好(至少在这一部分)，它们使用了正确的随机 nonce，所以作为一个用户，你没必要太过担心。事实上，自 2016 年以来，比特币客户端使用了确定性签名(RFC6979)方案，这完全消除了过程中的随机性需求。

如果你使用的是非标准库，或者你自己编写了密码例程(只有当你有非常好的理由时，才应该那么做)，那么你应该确保它们使用了 RFC6979(关于这一话题，比太钱包团队在 2014 年就发过一篇文章《分分钟搞懂 RFC6979》)。这在嵌入式设备或或硬件 token 上更为重要，因为很难找到随机性的好来源。

以下是论文的部分译文：

标题：针对密码货币弱 ECDSA 签名的点阵攻击（Lattice Attacks

作者：Joachim Breitner 和 Nadia Heninger

所在机构 ：DFINITY Foundation, Zug,joachim@dfinity.org 加州大学(UC), San Diego,nadiah@cs.ucsd.edu

摘要。在这篇论文中，我们对包含在公链和互联网扫描的数字签名进行密码分析攻击，由此计算出了数百个比特币私钥，以及数十个以太坊、瑞波币、SSH 以及 HTTPS 私钥。ECDSA 签名算法要求生成每个消息的秘密 nonce。这个 nonce 必须完全一致地生成，否则攻击者可利用 nonce 偏差计算长期签名密钥。我们使用一种基于点阵(lattice-based)的算法来解决隐藏数问题，以有效地计算由于多个明显的实现漏洞，而与有偏差的签名 nonce 一起使用的私有 ECDSA 密钥。

一、简介

ECDSA 签名算法的安全性关键，依赖于正确生成用作临时私钥的每个签名 nonce 值。众所周知，如果使用 ECDSA 私钥签署两个具有相同签名 nonce 的消息，则长期的私钥就很容易去计算。

然而，重复的 nonce 值并不是唯一可使 ECDSA 密钥不安全的偏差类型。实际上，ECDSA 签名 nonce 中的任何不一致性，如果有足够多签名的话，都可以让私钥暴露。在这篇论文中，我们对从比特币、以太坊和 Ripple 区块链以及 ssh 和 https 收集的 ECDSA 签名进行了基于点阵的密码分析攻击，并有效地计算了数百个比特币私钥和少量以太坊和 SSH 私钥。

此外，我们还发现了大量的比特币、以太坊、Ripple、ssh 和 https 私钥因为重复的签名而泄露了。我们应用的点阵攻击，是基于隐数问题的求解算法。虽然隐藏数问题，在很多密码学文献当中，是基于侧通道攻击用于恢复私钥的一种流行工具，但据我们所知，我们是第一个观察到这种技术可适用于密码货币的签名。通过这种技术，我们计算了大约 300 个比特币私钥，共计 0.00818975 BTC，以及 30.40 XRP，这些资金仍然留在原账户当中。

对于椭圆曲线离散对数问题，我们使用的攻击方式，显然要比幼稚的暴力攻击或最先进的算法要快得多。使用像 Pollard rho [28]这样的平方根时间算法是可行的，这样我们可对小部分我们发现的 64 位或 128 位 nonce 目标进行有针对性的攻击;而对比特币区块链中大约 2^30 个签名进行攻击，将需要比我们所获得的多得多的计算资源。相比之下，对于所有区块链，我们的计算总共花费了 40 年的 CPU 时间(注：CPU 时间即反映 CPU 全速工作时完成该进程所花费的时间)，这些计算是用 Python 实现的。

nonce 漏洞分为几个类，而这次研究表明我们发现了几个独立的实现漏洞。当所使用的 nonce 要比我们预期要短时，我们首先使用隐数问题算法来发现长期 ECDSA 签名密钥，并用长度为 64 位、110 位、128 位以及 160 位的 nonce 找到密钥。

道德准则：我们无法验证这些漏洞的存在，除非实际计算易受攻击地址的私钥。对于密码货币，这些密钥可使我们或任何其他攻击者能够盗走关联账户中的资金。对于 ssh 或 https，这些密钥将使我们或任何其他攻击者能够模拟终端主机。我们没有这样做，在我们的研究过程中，我们没有转移走任何密码货币，或主动攻击我们自己。我们的研究完全是被动的，只需要观察交易或通用网络测量。然而，鉴于我们发现一些证据，表明其他攻击者已通过已知漏洞(包括重复的 nonce 以及把私钥在线发布)而清空了相关泄露的密码货币用户账户。我们预计，一旦这个缺陷被恶意者利用，相关用户就会受到影响。

我们试图向少数我们能识别的团队披露这些缺陷，但在大多数情况下，我们无法向特定的供应商、维护人员或用户披露相关漏洞。

对策。我们在本论文中所讨论的所有攻击，都可以通过使用确定性的 ECDSA nonce 生成工具来防止，这已经在默认的比特币和以太坊库中实现了。

二、相关的工作

隐藏数问题和 ECDSA。隐藏数问题，以及我们用来解决它的基于点阵的算法，是由 Boneh 和 Venkatesan 提出的，他们用它来证明计算 Diffie-Hellman 最重要位的困难。

Howgrave Graham、Smart[19]、Nguyen 以及 Shparlinski [26]应用了隐藏数问题，来显示如果攻击者可以学习一些当前最重要的签名 nonce 位，则 DSA 和 ECDSA 签名方案是不安全的。从那时起，这种技术在实践中被应用于侧通道攻击。

重复的 DSA/ECDSA 签名。很多研究工作已检查到 DSA 和 ECDSA 当中由于重复签名 nonce 而存在的漏洞。Heninger、Durumeric、Wustrow 和 Halderman 在 2012 年通过从 SSH handshakes 搜索重复的 DSA 签名 nonce，使得 1%的 SSH 主机密钥被暴露。他们把问题主要追溯到低资源设备上随机数生成的实现漏洞。

Bos, Halderman, Heninger, Moore, Naehrig 和 Wustrow [7] 在 2013 年记录了比特币区块链中重复出现的 nonce，以此作为关于椭圆曲线密码技术应用更广泛研究的一部分。Valsorda 在 2014 年研究了重复的比特币 nonce。Courtois, Emirdag 以及 Valsorda 在 2014 年研究了重复的比特币 nonce，并指出其有可能对密钥产生威胁。Castellucci 和 Valsorda 在 2016 年研究了重复 nonce 以及弱密钥变体，以及比特币密钥当中存在的重复 nonce。Brengel 和 Rosow 在 2018 年研究了来自同一密钥签名中的重复 nonce，并在比特币区块链中不同密钥签名之间链接了泄露的 nonce。

密码货币中的密钥生成问题。在 2013 年，安卓 SecureRandom 的一个主要漏洞，被指责是导致很多比特币安卓钱包用户被盗的原因，这是由错误的随机数生成器生成了重复的 ECDSA 签名 nonce 所致。2015 年，Blockchain.info 的安卓应用，被发现生成了重复的私钥，因为该应用的种子是从 random.org 导出的，而该网站当时出现了 403 问题，并重定向到他们几个月前的 https URL 。

针对密码货币的密码分析。大型比特币对撞机(The Large Bitcoin Collider)是一个针对比特币私钥的暴力搜索项目，其使用了明显线性的暴力搜索算法，并最多搜索到 54 位的密钥。对于已泄露的公钥而言，使用平方根离散对数算法 [28,34]是恢复这类短私钥的更为有效的方法，但目前我们还没有看到有人在做这方面的尝试。

三、椭圆曲线数字签名算法（ECDSA）

椭圆曲线数字签名的公共域参数包括有限域上的椭圆曲线 E，和 E 上 n 阶的基点 G。私有签名密钥是整数 d modulo n，而公共签名验证密钥是点 Q = dG。椭圆曲线公钥可通过提供公共点 Q 的 x 和 y 坐标来表示未压缩形式，也可以通过仅提供 x 坐标和 y 值的单个奇偶校验位来表示为压缩形式。

要对消息哈希 h 进行签名，签名者选择每个消息的随机整数 k modulo n，计算

3.1 密码货币中的 ECDSA

比特币 ,以太坊 和瑞波都是使用的椭圆曲线 secp256k1。

比特币地址是通过使用 sha-256 和 RIPEMD-160 算法反复哈希未压缩或压缩的 ECDSA 公钥，从而生成地址的。

而以太坊地址是未压缩 ECDSA 公钥的 Keccak-256 哈希的最后 20 个字节，其中 Keccak-256 算法是 SHA-3 算法的一个早期版本。以太坊公钥并不明确地随签名一起提供，相反，签名包含一个额外的字节 v，其允许从签名中派生公钥。

瑞波地址是通过 SHA-256 和 RIPEMD-160 算法反复哈希压缩公钥而来的，并连接哈希的各个部分。

为了论文分析目的，在以上这些密码货币当中，只有在地址签名一笔交易之后，才会显示出 ECDSA 公钥。

通过签名，比特币和瑞波会明确显示未压缩或压缩格式的 ECDSA 公钥;而在以太坊中，客户端必须使用密钥恢复从签名本身派生出公钥。

ECDSA 签名用于对一笔交易的发送方进行身份验证。地址可以是单个签名的，其对应于单个公钥，也可以是多签名地址，这些地址需要 n 个公钥集当中至少 k 个公钥的有效签名，这样才能完成一笔交易。通常用户在进行每一笔交易时，应使用新的地址。

签名规范化。ECDSA 签名具有签名(r, s)和 (r, −s) 的属性，其将用相同的公钥进行验证。2015 年 10 月份，比特币在签名过程中引入了一种变化，即在签名中使用 s 和−s mod n 的较小值，以使签名具有唯一性。以太坊和瑞波也进行了这种类型的签名规范化，这会影响到我们的攻击。

3.3 针对 ECDSA 的基本攻击

如果攻击者知道了用于生成一个 ECDSA 签名的每条消息(per-message)的 nonce k，则长期密钥 d 是易于计算的，因为

众所周知，如果使用相同的密钥，将相同的 nonce k 签署两则不同的消息 h1 和 h2，那么这个密钥就会泄露。 设(r1, s1)为消息哈希 h1 上生成的签名，(r2，s2)为消息哈希 h2 上的签名。我们马上得到 r1 = r2，因为 r1 = r2 = x(kG)。然后我们就可以计算，并恢复如上所述的密钥。

四、针对 ECDSA 的点阵攻击

在随机 modulo n 上，签名 nonce k 也必须完全一致地生成，否则，可使用解决隐数问题的技术，来求解密钥 d 。

转自：深圳热线 蜗牛娱乐(www.woniuyulew.com)亚洲最具人气线上娱乐平台

---