G.O.S.S.I.P 阅读推荐 2023-12-07 比特币奇事之half-half ECDSA Nonces

备受本编辑部推崇的密码学安全研究女神Nadia Heninger可谓现实世界密码安全问题的“猎手”，在今天介绍的这篇论文The curious case of the half-half Bitcoin ECDSA nonces中，她的研究组再次给大家展示了在我们人类世界中存在的“奇事”——在比特币生态环境中（居然还有）一种草台班子开发的ECDSA签名实现方案，以及如何利用LLL算法对其进行破解。

作者发现，在比特币区块链记录里面，有一小部分ECDSA签名使用了不安全的nonce，会直接导致对应的私钥被攻击者恢复。在介绍细节之前，我们先讲讲背景知识，首先是ECDSA签名方案中的nonce使用问题——即使是密码学教科书都会反复强调，nonce一定不要重用，而和这个相关的著名的安全事件，就是2010年Chaos Communication Congress（27C3）上由fail0verflow披露的Sony PlayStation 3上面的ECDSA（固定）nonce安全漏洞，如果大家对这个事件感兴趣可以去查查当年的资料。

G.O.S.S.I.P在2018年CCS上同样介绍了一个例子，也是涉及DSA nonce重用的（DSA和ECDSA的算法是基本一致的），有兴趣的读者也可以看看我们的论文K-Hunt: Pinpointing Insecure Cryptographic Keys in Execution Traces （https://lijuanru.com/publications/ccs18.pdf 论文电子版）

回到本文，作者发现，尽管比特币规定在ECDSA签名中应该参考RFC 6979：Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)，但是比特币区块链上有很少一部分的ECDSA签名，用了如下的方法来生成所使用的随机数k：

具体来说，就是这个256比特的k，是由待签名交易信息的hash中的高128比特和签名私钥的高128比特拼接起来得到的。只需要一个使用了这种奇怪的half-half拼接得到的nonce参与的签名，攻击者就可以恢复私钥！而且攻击的成本非常之低，在普通的Intel Xeon E5-2699A v4 CPU上也就只需要1个核心1秒钟的算力就可以搞定！

在经典的针对ECDSA重用nonce签名的攻击中，攻击者需要知道k的全部信息，或者需要两个不同的签名（均使用了相同的nonce签出）。今天这篇论文，不管是其发现的问题，还是恢复私钥的技术，都和以前的案例不一样。但是作者使用的核心算法——Lenstra Lenstra Lovász lattice reduction algorithm，也就是许多密码教科书上都会介绍的大名鼎鼎的LLL算法，可能很多密码学背景的读者都知道。假设你不了解这个算法，如果你是年纪比较大的读者（假定我们的读者里面有30+、40+甚至50+、60+的爷爷奶奶），读过上个世纪出版的《十万个为什么》数学分册，可能还记得里面提到过一个“背包问题”和对应的公钥密码算法，而后来这个算法被Adi Shamir（RSA的S）攻破，使用的正是这个LLL算法。此外，对于这种部分私钥信息泄露的问题，Nadia Heninger本人对此颇有研究，读者可以看看 https://eprint.iacr.org/2020/1506 这篇论文Recovering cryptographic keys from partial information, by example，而且本文还参考了Dan Boneh和Ramarathnam Venkatesan在Crypto 1996年发表的文章Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes，在那篇文章中，定义了所谓的hidden number problem，也就是在特定算术运算中，如果知道了某个数的部分（高位，most significant）比特信息，如何求剩余的比特。

我们今天无意介绍密码学知识，上述的一些背景（和八卦）讲完之后，大家如果想要知道如何攻击奇怪的half-half nonce based ECDSA签名，可以去论文中找细节，我们只想讲讲作者的调研结果。作者收集了比特币区块链上21亿个ECDSA签名，然后用了1000个CPU核心，花了18天时间来检查这些签名中有没有可能存在上述问题的签名。最后，他们发现了88230个有问题的签名，对应了873个不同的私钥，涉及7242笔交易，从893个钱包地址转走了总共222个比特币（按照今天也就是2023年12月7日的价格，每个比特币4.3万美元，就是954.6万美元！！！）被转走。

不过你也不要嫉妒Nadia一夜暴富，她只是发明了攻击的技术，而这些比特币早在她完成这项技术之前就被转走了，跟她也没啥关系。实际上，这873个私钥在本文研究工作提出之前就已经被盗（或者说被控制）了，具体的攻击是从2015年情人节那天开始，持续到2022年5月（下图展示了攻击情况，在2020年到2021年攻击者大概是阳了，偃旗息鼓了一段时间）。

作者又对这893个转出比特币的钱包地址（正常情况下应该是公钥经过SHA-256和RIPEMD-160算法迭代得到的值）进行了分析，发现了一些奇怪的现象如下，其中包括了d=1的这种不安全私钥、以及完全不满足ECDSA公钥私钥特性的钱包地址。

作者于是对这些交易进行了分析和推理，猜测这背后可能是有（一个）恶意攻击者引入了有问题的ECDSA签名实现（这种恶意实现其实如果单纯从交易信息上分析是很难发现的，也就是我们常说的引入了密码学后门），作者通过网络搜索和信息统计，追踪交易和相关比特币的去向，最后将攻击聚焦到一个化名为amaclin的神秘人物（亦或是一个神秘组织）身上，作者尝试联系了这位amaclin但是并没有任何回应。

---

https://eprint.iacr.org/2023/841

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2023-12-07 比特币奇事之half-half ECDSA Nonces