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

admin 2023年12月10日09:22:05评论27 views字数 2602阅读8分40秒阅读模式

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

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

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

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

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 论文电子版)

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

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

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

具体来说,就是这个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万美元!!!)被转走。

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

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

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

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

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

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


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

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

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年12月10日09:22:05
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   G.O.S.S.I.P 阅读推荐 2023-12-07 比特币奇事之half-half ECDSA Nonceshttp://cn-sec.com/archives/2278163.html

发表评论

匿名网友 填写信息