比暴力破解更聪明，研究人员提出弱比特币私钥的格子攻击方法

私钥对加密货币的重要性不言而喻。 在这个世界上，人们无时无刻不在试图破解比特币私钥。

最残忍的方式就是穷举比特币私钥暴力碰撞。 LargeBitcoinCollider（LBC）就是这样一个组织，它使用了一个明显的线性暴力搜索算法，而这样的方法在量子计算中还没有实质性的实现。 前性行为可以说是愚蠢的。

宾夕法尼亚大学和加州大学计算机科学与工程学院的博士后研究员 Joachim Breitner 表示，对于泄露的公钥，使用平方根离散对数算法是恢复此类短私钥的更有效方法。 该研究所的副教授 Nadia Heninger 与人合着了一项名为“对加密货币的弱 ECDSA 签名的晶格攻击”的研究。

在这项研究中，我们看到了几种不安全的方式，可以破坏比特币、以太坊和 Ripple 区块链以及 HTTPS 和 SSH 中的私钥。 结果数字并不大。 在实验中，研究人员一共计算出了 300 多个比特币私钥（余额约为 0.00818975 BTC），以及 30.40 个 XRP。 然而，实验告诉我们，如果我们想要正确使用加密货币，其实是一件非常棘手的事情，如果你做的不对，那么你很可能会损失你的资金。

当您使用 ECDSA（椭圆曲线数字签名算法）创建加密签名时，您需要提供一个 256 位的随机数。 每次签名使用不同的nonce是很重要的，否则别人很容易拿走你的签名，用比较简单的数学计算出你的私钥，有了你的私钥，他们就可以花掉你所有的比特币。 事实上，有证据表明有人一直在为这个重复的 nonce 监控区块链，如果检测到，他们会计算出相应的私钥并从中提取资金。

知道这种攻击的人并不多，但这对密码学界来说并不是什么新鲜事，攻击者可以根据使用不同但相似的随机数来计算私钥：例如，如果它们彼此接近（只有低位不同），或者它们恰好相差 2 的大幂（只有高位不同）。 这使用了基于格的强大技术。 本文的主要贡献是将密码学和加密货币联系起来，看看这些漏洞是否真的存在。

事实上，这种漏洞确实存在于加密货币中。 幸运的是，它们并不多，但它们确实存在，而且它们似乎有多个来源。 不幸的是，很难查明这些签名是谁创建的，使用了什么代码，所以我们只能猜测这些错误的原因。 大量受影响的签名与多重签名交易有关，因此我们认为硬件令牌可能对此负责。

虽然我们无法查明导致这些问题的确切实现，但我们仍然可以观察到一些有趣的细节。 当然，最好奇的是：

一组签名是由攻击者创建的，该攻击者清除了密钥泄露的帐户（例如使用弱密码创建的帐户，或以其他方式泄露到 Internet 的私钥）。

因此，看起来很像攻击者设置了一个程序来监控区块链，这将清除受感染的帐户。

（图片来自：pexels.com）

我们需要担心吗？

可能不会。 官方的区块链客户端在这方面做得很好（至少在这部分），他们使用正确的随机数，所以作为用户，你不必太担心。 事实上，自 2016 年以来，比特币客户端使用确定性签名（RFC6979）方案，完全消除了过程中对随机性的需求。

如果你使用的是非标准库，或者你已经编写了自己的加密例程（只有在你有充分理由的情况下才应该这样做），那么你应该确保他们使用 RFC6979（关于这个主题，Bitherwallet 团队2014年发表文章《分钟了解RFC6979》）。 这在嵌入式设备或硬件令牌上更为重要，因为在这些地方很难找到好的随机性来源。

以下是论文的部分译文：

标题：针对加密货币的弱 ECDSA 签名的格子攻击

约阿希姆·布莱特纳 (Joachim Breitner) 和纳迪亚·海宁格 (Nadia Heninger)

隶属关系：DFINITY 基金会，楚格，joachim@dfinity.org

加利福尼亚大学 (UC)，圣地亚哥，nadiah@cs.ucsd.edu

概括。 在本文中，我们对公链和互联网扫描中包含的数字签名进行密码分析攻击，从而计算出数百个比特币私钥，以及数十个以太坊、Ripple、SSH 和 HTTPS 私钥。 钥匙。 ECDSA 签名算法需要为每条消息生成一个秘密随机数。 此随机数必须完全相同地生成，否则攻击者可以使用随机数偏差来计算长期签名密钥。 我们使用基于格的算法解决隐藏数字问题，以有效计算由于多个明显的实现错误而与有偏见的签名随机数一起使用的私有 ECDSA 密钥。

关键词：隐藏数问题，ECDSA（椭圆曲线算法），格（Lattices），比特币，加密货币

一、简介

ECDSA 签名算法的安全性关键依赖于每个用作临时私钥的签名随机数值的正确生成。 众所周知，如果使用 ECDSA 私钥对两条具有相同签名 nonce 的消息进行签名，则长期私钥很容易计算。 [18,7,37,13,11,8]

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

此外比特币破解版，我们还发现大量比特币、以太坊、瑞波币、ssh 和 https 私钥因重复签名而泄露。 我们应用的格攻击是基于求解隐式数问题的算法。 尽管在许多密码学文献中，隐藏数问题是一种基于侧信道攻击 [5、14] 恢复私钥的流行工具，但据我们所知，我们是第一个观察到该技术可以为加密货币签名的人。 使用这种技术，我们计算出大约 300 个比特币私钥，总计 0.00818975 BTC 和 30.40 XRP，保留在原始账户中。

对于椭圆曲线离散对数问题，我们使用的攻击显然比朴素的蛮力攻击或最先进的算法快得多。 使用像 Pollard rho [28] 这样的平方根时间算法是可行的，这样我们就可以对我们找到的少量 64 位或 128 位 nonce 目标进行针对性攻击； 用 30 个签名进行攻击需要的计算资源比我们得到的要多得多。 相比之下，我们的计算在所有区块链上总共花费了 40 年的 CPU 时间（注：CPU 时间反映了 CPU 全速工作时完成该过程所需的时间），并且这些计算是用 Python 实现的。

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

道德准则：如果不实际计算易受攻击地址的私钥，我们无法验证这些漏洞的存在。 对于加密货币，这些密钥允许我们或任何其他攻击者从关联账户中窃取资金。 对于 ssh 或 https，这些密钥将允许我们或任何其他攻击者冒充终端主机。 我们没有，在我们的研究过程中，我们没有移走任何加密货币，也没有主动攻击我们自己。 我们的研究完全是被动的，只需要观察交易或一般网络测量。 然而，鉴于我们发现了一些证据表明其他攻击者已经通过已知漏洞（包括重复随机数和在线发布私钥）清空了相关泄露的加密货币用户帐户。 我们预计一旦该漏洞被恶意利用，相关用户将受到影响。

我们尝试向我们可以识别的少数团队披露这些错误，但在大多数情况下，我们无法向特定的供应商、维护者或用户披露有问题的错误。

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

二、相关工作

隐藏数问题和ECDSA。 隐藏数问题以及我们用来解决它的基于格的算法是由 Boneh 和 Venkatesan 提出的，他们用它来证明计算 Diffie-Hellman [6] 最高有效位的难度。

Howgrave Graham、Smart [19]、Nguyen 和 Shparlinski [26] 应用隐藏数字问题来表明，如果攻击者可以获悉一些当前最重要的签名随机数位，则 DSA 和 ECDSA 签名方案是不安全的。 从那时起，该技术已在实践中应用于侧信道攻击 [5、14]。

重复的 DSA/ECDSA 签名。 由于重复的随机数签名，许多研究工作已经检查了 DSA 和 ECDSA 中的漏洞。 Heninger、Durumeric、Wustrow 和 Halderman [18] 在 2012 年通过从 SSH 握手中搜索重复的 DSA 签名随机数，暴露了 1% 的 SSH 主机密钥。 他们将问题主要追溯到低资源设备上随机数生成的实现错误。

Bos、Halderman、Heninger、Moore、Naehrig 和 Wustrow [7] 在 2013 年记录了比特币区块链中的重复随机数，作为对椭圆曲线密码学应用的更广泛研究的一部分。 Valsorda 在 2014 年研究了重复的比特币随机数 [37]。 Courtois、Emirdag 和 Valsorda [13] 在 2014 年研究了重复的比特币 nonce，并指出它可能对密钥构成威胁。 Castellucci 和 Valsorda 在 2016 年研究了重复随机数和弱密钥变体，以及比特币密钥中存在的重复随机数 [11]。 Brengel 和 Rosow 在 2018 年研究了来自同一密钥签名的重复随机数，并将比特币区块链中不同密钥签名之间的泄漏随机数联系起来 [8]。

加密货币中的密钥生成问题。 2013 年，Android SecureRandom 中的一个主要错误被归咎于许多比特币 Android 钱包用户被盗，原因是错误的随机数生成器生成重复的 ECDSA 签名随机数 [20, 22]。 2015 年比特币破解版，Blockchain.info 的 Android 应用程序被发现生成重复的私钥，因为该应用程序的种子是从 random.org 导出的，并且该网站收到 403 并重定向到他们几个月前的 https URL [35]。

加密货币的密码分析。 大型比特币对撞机（The Large Bitcoin Collider）是一个针对比特币私钥的暴力搜索项目，它使用了一种看似线性的暴力搜索算法[30]，最多搜索 54 位密钥。 对于泄露的公钥，使用平方根离散对数算法 [28, 34] 是恢复此类短私钥的更有效方法，但我们还没有看到任何这样做的尝试。

3. 椭圆曲线数字签名算法（ECDSA）

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

为了对消息哈希 h 进行签名，签名者为每条消息选择一个随机整数 k 模 n，计算

3.1 加密货币中的 ECDSA

比特币 [23]、以太坊 [10] 和 Ripple [33] 都使用椭圆曲线 secp256k1 [9]。

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

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

Ripple地址是将压缩后的公钥通过SHA-256和RIPEMD-160算法反复哈希，并将哈希的各个部分连接起来得到的。

出于本文的分析目的，在上述加密货币中，ECDSA公钥只有在地址签署交易后才会显示。

通过签名，Bitcoin 和 Ripple 以未压缩或压缩格式明确显示 ECDSA 公钥； 而在以太坊中，客户端必须使用密钥恢复从签名本身导出公钥。

ECDSA 签名用于验证交易的发送者。 地址可以是单签名的，对应于单个公钥，也可以是多签名地址，需要 n 个公钥集中至少 k 个公钥的有效签名才能完成交易。 通常用户应该为每笔交易使用一个新地址[2]。

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

3.3 针对 ECDSA 的基本攻击

如果攻击者知道用于生成 ECDSA 签名的每条消息的随机数 k，则长期密钥 d 很容易计算，因为

众所周知，如果两个不同的消息 h1 和 h2 使用相同的密钥使用相同的随机数 k 进行签名，则密钥将被泄露。

设 (r1, s1) 为消息哈希 h1 上生成的签名，(r2, s2) 为消息哈希 h2 上的签名。 我们立即得到 r1 = r2 因为 r1 = r2 = x(kG)。 然后我们可以计算并恢复密钥，如上所述。

4. 针对ECDSA的格子攻击

在随机模n上，签名nonce k也必须完全一致，否则，可以使用解隐数问题的技巧解出密钥d。

具体的攻击解释请看原论文。

后记：对于加密货币持有者来说，最重要的是掌握安全的存储方式和私钥生成方式。 选择一个好的钱包非常重要。 官方钱包虽然“笨重”，但相对来说更安全。