《区块链启示录:中本聪文集》49 论盗用比特币的可能性

49 论盗用比特币的可能性

如前所述,比特币系统采用非对称加密,将公钥和私钥作为接收和授权使用比特币的机制。然而,中本聪决定使用公钥的哈希值而非公钥本身作为比特币地址。中本聪这么做有两个原因。一是减小每笔交易的长度,因为哈希值只有160位长。二是简单地提高了安全性,以防比特币所用的非对称加密算法中发现后门或安全缺陷。为了能使用比特币,黑客必须首先从哈希值中推导出公钥,然后从公钥中推导出私钥。关于该主题,《比特币杂志》有一篇优秀的文章。

本帖讨论了拥有大量算力的攻击者可以盗用存储在某个比特币地址的比特币的可能性。由于比特币区块链是公开账本,所以可以查到哪个地址有大量的比特 币余额,攻击者因此可以专门攻击这些地址。

中本聪得出结论:这是相当困难的事,因为这需要暴力破解具有相同哈希值的公钥。这同时显示出与闭源代码相比,开源代码对安全的价值。

现在把讨论的重要部分,包括中本聪本人的完整帖子,重现如下:

盗取比特币

Red发表,2010年7月25日,下午05:08:03

我认为目前的比特币软件有一个相当大的加密漏洞。我不确定现在是否可以利用(我并不是真正的黑客),但很快会显现出它的问题。

该漏洞将导致可以匿名窃取任何比特币地址的比特币。而且并不涉及求解任何保障现有加密系统安全的难题。仅仅是当前软件中“潜在”可纠正的逻辑缺陷 。

我希望比特币成功,所以我不愿意在公共场合上窜下跳,扯着嗓子高喊缺陷 。是否有合适的地方专门讨论此类问题?

回复:盗取比特币

中本聪发表,2010年7月25日,下午05:45:22

最好您私下告诉我,这样可以先修复掉。

我刚给您发了电子邮件,其中有我的电子邮箱地址。(或您在这里私信我。 )

回复:盗取比特币

中本聪发表,2010年7月25日,下午07:06:23

Red,感谢您先私下告诉我!请把它张贴出来以解除每个人的悬念!

他的观点是,给比特币地址付款的交易与哈希函数处于同样的安全水准。为了使比特币地址简短,地址为公钥的哈希值,而非公钥本身。攻击者只需要破解哈希函数,而不是椭圆曲线数字签名算法(ECDSA)。

回复:盗取比特币

Red发表,2010年7月25日,下午07:09:43

谢谢聪,

这是我发给他的。

众所周知,公钥加密系统依赖于很难因式分解大素数的事实。如果分配给支出比特币的公钥结构完整,且在未来转账时需要提供相关的私钥签名,那我就承认比特币加密传输绝对安全。

然而,比特币交易似乎并不是这样运作的(据我的阅读)。交易将比特币支付给一个特别的“比特币地址”。这个地址是公钥的哈希值。

为了验证一笔交易,节点从签名中取得公钥,用以验证实际签名。如果签名有效,则对公钥进行哈希计算,确认哈希值与上一笔交易中分配的比特币地址相同。按照定义,如果两个都对上了,那么交易正常。

潜在的弱点在于将签名的公钥与比特币地址相关联。

公钥与特定哈希值之间存在着多对一的关系。现有一组安全的公/私钥对,其中公钥哈希成比特币地址,似乎很难找到创建这组密钥对的一对素数。

然而,并非必须找到这对素数。

您所需要的是可以代表公钥的任何数,其哈希值与已知比特币地址碰撞。它不必是基于素数的安全密钥对。只需要一次性地将赃款转移到另一个账户。这可能要容易得多。

有些哈希算法比其他种类更难碰撞。我不确定现在使用的哈希算法的强度。 然而如果不需要关心哈希的内容,那么与任何一种哈希发生碰撞都容易得多。

由于公钥的性质,它们看起来像是随机数。据我所知,除非对公钥成功进行因式分解,否则无法知道该公钥是否建立在安全数学之上。因此,客户不会尝试。它们通常只是进行签名验证,并假定公钥是以安全的方式产生的。

注意:下面的分析需要由真正的黑客复核,IANACR。

因此,根据哈希算法的不同,可以使用某种必将出现的哈希碰撞算法,来生成碰撞数据块,用来代表一个公钥。然后通过公/私钥的逆运算,生成关联的(但几乎不安全的)私钥,用来产生有效的签名。

然后用这组不安全且易分解的密钥对生成匹配目标比特币地址的签名交易。 由于交易日志不能验证比特币打算用的完整公钥,只是简单假定就是该交易 。

在区块列表中记录支付对象的完整公钥可以恢复预期的强度。然而,因此也丧失了大约34个字符地址的传输能力。

如果我说得完全不着调,很抱歉浪费了您的时间。

祝好!

Red

回复:盗取比特币

Red发表,2010年7月25日,下午07:22:14

中本聪指出我提出的场景仍然需要破解哈希函数。确实如此,但我很惊讶地发现居然有人在这方面取得了这么大的成功。MD4和MD5就是明显的例子。但是 寻找SHA-1和同系列的SHA-256等算法碰撞的工作还在进行中。

比特币在这部分用了哪种哈希?

他还怀疑,除了生成的密钥对之外,还有其他可以使用的手段。

在这点上,我很自信这只是个简单的数学问题。直到我听到文档“盲签”,才给予了足够的重视。

居然可以拿一个文档与一个随机数相乘。然后让人为这份打乱的文件签名。 最后,用签名除以随机数,结果仍然是原始文档的有效签名。谁会知道这也行!

密钥对只有在基于素数对时才是安全的。如果不是基于素数,运算过程也没有变化。只是密钥更容易因式分解。

我很乐意有密码学高手跳出来证明我是个白痴。这影响了我以前一个项目的一些特性,它们也依赖相同的关联关系。我那时候也没想到这点。

回复:盗取比特币

knightmb发表,2010年7月25日,下午07:34:42

非常好!这是我喜欢开源的另一个原因。

下面是我的理解,如果我错了请纠正。

由于公钥哈希值比公钥本身要小,所以只需要找到匹配哈希的公钥碰撞,当发现哈希的碰撞时,就知道了公/私钥组合。然后,只需要使用已知地址的比特币 ,其他客户端会认为这是一笔有效的转账,因为客户端只关心您的哈希值与受害者的相同,这笔交易就被永久记录了。

当前哈希值的长度是35个字符,共有62种字母数字组合:

大写字母26+小写字母26+数字10=62种字母数字组合

所以会有541 638 008 296 341 754 635 824 011 376 225 346 986 572 413 939 63 4 062 667 808 768种可能的组合。

比起暴力破解公/私钥,我们仍然长路漫漫。请不要杞人忧天了。

回复:盗取比特币

引自:Red, 2010年7月25日,下午07:22:14

中本聪指出,我提出的场景仍然需要破解哈希函数。确实如此,但是我很惊讶地发现居然有人在这方面取得了这么大的成功。MD4和MD5就是明显的例子。 但是寻找SHA-1和同系列的SHA-256等算法碰撞的工作还在进行中。

但他们忘记了“产生碰撞”也需要大量的CPU时间。

如果发现公钥123456生成哈希值ABCD,公钥654321也生成了ABCD。

我还是没有私钥。

但按照您的说法,只需要公钥654321,就可以假装是公钥123456去盗用他的比特币了。

回复:盗取比特币

Red发表,2010年7月25日,下午07:52:23

据我所知,比特币使用了一种160位的哈希算法来生成比特币地址。

SHA-1系列哈希算法是最常用的一种160位的哈希算法。

这里有篇文章声称用2^52次以内的密码操作找到了SHA-1碰撞。优化过的安全哈希则需要2^80次。虽然2^52次很大,但已进入集群和僵尸网络的算力范围。 http://www.ictlex.net/wp-content/iacrhash.pdf

在笔记本电脑上几秒内就能破解MD5哈希。这就是为什么它已退出证书签名领域。

是的,我想说的是“我认为”可以把公钥想象成两个秘密数字以数学方式结合在一起。而私钥则是这两个数保持分开。要确保系统安全,需要那两个秘密数是很大的两个素数。

但是,如果这两个秘密数字是很大的非素数,组合运算仍然有效,只是破译算法要快得多。

我会在谷歌上多搜索些,看是否能证实我的说法。还是希望有人会马上把我驳倒。

回复:盗取比特币

中本聪发表,2010年7月25日,下午08:01:40

引自:knightmb, 2010年7月25日,下午07:44:02

如果我发现公钥123456生成了哈希值ABCD,公钥654321也生成了 ABCD。

我还是没有私钥。

但按照您的说法,只需要公钥654321,就可以假装是公钥123456去盗用他的比特币了。

还是要用公钥654321来签名。在用公钥寻找碰撞时还需要知道它的私钥。 当您要处理一个基于比特币地址的交易时,从中拿出与哈希值匹配的公钥, 然后必须用该密钥来签名。

Red的观点是,找到碰撞后可以很容易快速生成不安全的公钥,破解这些公钥就可以找到对应私钥。

他指出如果要求公钥也必须安全,那就必须耗费大量工作才能找出素数的安全密钥,那会在单独哈希函数之上增加强度。企图暴力破解的人每次就得花更多时间来尝试生成密钥。

回复:盗取比特币

knightmb发表,2010年7月25日,下午08:20:41

引自:中本聪,2010年7月25曰,下午08:01:40

还是要用公钥654321来签名。在用公钥寻找碰撞时还需要知道它的私钥。 当您要处理一个基于比特币地址的交易时,从中拿出与哈希值匹配的公钥, 然后必须用该密钥来签名。

Red的观点是,找到碰撞后可以很容易快速生成不安全的公钥,破解这些公钥就可以找到对应私钥。

他指出如果要求公钥也必须安全,那就必须耗费大量工作才能找出素数的安全密钥,那会在单独哈希函数之上增加强度。企图暴力破解的人每次就得花更多时间来尝试生成密钥。

是的,我认为必须在某处把私钥加进去。这相当于增加了另一项随机性,必须找到与另一个公钥发生碰撞的哈希值,同时私钥也要弱到容易破解。我并没说这不可能,但是这在反向碰撞寻找中引入了两个变量。

基本上,攻击者会构建一个弱私钥的彩虹表,然后必须将其与公开的哈希值比较,希望某人有一个哈希值刚好是这次攻击的一部分。当然这样也并非不可能 ,但即使计算机在10年内快了100倍,那可行性又有多大呢?

编辑:重读了您的帖子,公钥是从私钥生成的,而不是独立的。所以只找到弱公钥是有问题的。

回复:盗取比特币

中本聪发表,2010年7月25日,下午08:48:01

引述

这里有篇文章声称用2^52次以内的密码操作找到了 SHA-1碰撞。优化过的安全哈希则需要2^80次。虽然2^52次很大,但已进入集群和僵尸网络的算力范围。

如果使用生日攻击可以达到2^80次。但是这种场景下不能用生日攻击,所以难度就是全部2^160位。但是,如果要破解100万(2^20)次交易中的任意一个,就能做到部分生日攻击2^160 / 2^20 = 2^140。

比特币地址是使用160位哈希算法的唯一场景。其他都使用SHA-256。它们的计算方法是:

bitcoinaddress=RIPEMD-160(SHA-256 (publickey))

如有错误请指正,但我认为在这种情况下很难对RIPEMD-160采取分析攻击。 分析攻击针对输入尝试的范围或模式做定义,可以极大地提升找到碰撞的机会。 而在这里,我们对RIPEMD-160的输入没有那种控制办法,因为输入是SHA-256算法的输出。如果分析攻击帮助你找到了令RIPEMD-160产生碰撞的输入,那你该怎么办呢?还得让SHA-256输出该值,仍然还要破解SHA-256。

对暴力破解,RIPEMD-160(SHA-256 (x))的强度不高于单独使用RIPEMD-160。但对于分析攻击,似乎必须同时对RIPEMD-160和SHA-256进行破解。如果我搞错了,那么强度就与RIPEMD-160相同,而SHA-256只作为一层密钥加固。

回复:盗取比特币

Red发表,2010年7月25日,下午09:04:01

引自:中本聪,2010年7月25曰,下午08:48:01

bitcoinaddress=RIPEMD-160 (SHA-256 (publickey))

如有错误请指正,但我认为在这种情况下很难对RIPEMD-160采取分析攻击。

我认为您对分析攻击的理解是对的。至少根据我对正在作此分析的数学天才 们的有限理解。

我过去曾经担心以下计算过于简单: bitcoinaddress=RIPEMD-160 ( publickey )

回复:盗取比特币

Red发表,2010年7月25日,下午09:19:11

这是我理解的方式。

给定两个数p和q。对于RSA来说,应该是大素数。

有n=p*q。

公钥有(n,e)两个字段。e称为公钥指数,似乎来自于一组常用值。

复杂之处在于很难将n分解为p和q。因此找出p-1和q-1也就同样困难。

假设,如果n为任意值,而e是一个常用值,那么就会有很多个不同的p、q对可以用。素数越少,就越容易找到p和q,以及p-1和q-1。如果有大量任意数,就会在寻找哈希碰撞值时有很大的灵活性。

(在这点上可能我完全是胡说八道。我对它真的很感兴趣,希望有密码高手了解得比我更清楚些。)

我曾读过,密钥生成算法创建了p和q,它们“非常可能是素数”,但是要确定这点需要耗费很大的工作量。这使我相信非素数不会导致任何明显的错误。不过可能我是错的。

回复:盗取比特币

中本聪发表,2010年7月25日,下午10:27:36

抱歉,实际上用的是ECDSA(椭圆曲线数字签名算法),而不是RSA。我不应该提到“素数”。ECDSA生成密钥对不会花很多时间。

回复:盗取比特币

Red发表,2010年7月26日,下午12:46:04

引自:中本聪,2010年7月25日,下午10:27:36

抱歉,实际上用的是ECDSA(椭圆曲线数字签名算法),而不是RSA。我不应该提到“素数”。ECDSA生成密钥对不会花很多时间。

哪天我要好好学学椭圆曲线算法,今天就算了。在大学时我应该多选一些有限数学的课。书到用时方恨少啊!

顺便赞一下中本聪的比特币创意和实现!

它开启了一个充满可能性的全新世界。我特别喜欢不依赖信任的分布式协议的概念。我认为这是个突破性的概念。

此外,我认为比特币挖矿的想法太精彩了!我怀疑可能没有其他方法可以引导网络了。我不认为现在发币采用了“公平的方式”,但这世界本来就是不公平的 !而且,我真的认为没有任何其他方式会让用户如此之兴奋。

另外,我承认从我之前的假设中找不到盗取比特币的线索。在我看来是双重哈希机制起了作用。干得好!

最后,我仍然想知道,如果使用非素数生成RSA密钥会发生什么。我估计还有其他系统没有使用双重哈希。

回复:盗取比特币

Bitcoiner发表,2010年7月27日,上午02:01:16

很高兴有Red这样的人,一直睁大眼睛关注事态!这组讨论也让我欣赏开源软件,因为这个论坛上有这么多聪明和热情的人,可以验证软件并为它额外增加了一层信任。如果比特币是闭源软件,真不确定会不会这么成功!

回复:盗取比特币

bytemaster发表,2010年7月 28日,下午09:42:17

在我看来,降低任何潜在攻击风险的明显方案是让潜在的“回报”变小。因此,不要在一个地址中存放太多比特币。如果“奖品”的经济价值小于破解它的成本 ,那么没人会费心尝试。此外,我仍然认为最好的办法是尽可能提高破解难度。

回复:盗取比特币

knightmb发表,2010年7月28日,下午 10:45:16

同时需要计算、存储能力和运气,当然是很困难的了。

即便发现了一个碰撞及私钥,那也没什么用,因为还需要从54163800829634 1754635824011376225346986572413939634062667808768种可能的组合中,找到一个在用的用户账号来关联。

再次审视这个问题。我在哈希值中发现了碰撞,并且找到了私钥。现在我希望自己运气好,有人正好在使用那个哈希值。由于可用的哈希账号数量大于这个星球人口的一百万倍,从本质上说,虽然这种攻击很有意思,但大规模实施不可行。

相关文章:

发表回复

您的电子邮箱地址不会被公开。