前言
在2014HITB-Exploiting ECDSA Failures in the Bitcoin Blockchain中他所使用提取签名的方法是通过Bloomfilter实现的，作者提到：
- first pass：把签名添加到Bloomfilter里面，作者所使用的是：dablooms，如果过滤器中已经存在了该签名，则把该签名放到一个map中叫做：potentialValues
- second pass：重新遍历signature，如果签名存在于potentialValues中，导出签名以及它的其他信息到map：rMap中
小故事
最近看的这篇PPT，他主要是探讨的在Bitcoin中同一用户使用相同的随机数k会造成私钥的泄漏，进而造成账户金额被盗等重大问题。作者举了几个例子：
- 索尼以前就犯过这样的错误：PlayStation 3 只能运行被索尼的进行ECDSA签名的游戏。如果我想为PlayStation 3开发了一个新的游戏，除非我从索尼获得签名值，否则我及时发布了，也运行不了这个游戏。问题是，索尼签名时用了一个静态的k值而不是随机生成的，这就可以根据相同的k进行破解从而得到私钥，进而任意发布游戏。
- 有人报告了他们的比特币被盗，并发送至地址：https://blockchain.info/address/1HKywxiL4JziqXrzLKhmB6a74ma6kxbSDj 您可以看到该地址当前包含55.82152538被盗硬币。已经注意到，在客户通过重新使用相同的随机数来不正确地签署交易后的几个小时内，所有硬币都被转移了。
新闻链接 - Android漏洞
下面具体展开对源码的剖析
blockchainr
代码整体架构
- main函数
- btcdbSetup函数
- getSignatures函数
- search函数
getSignature
此函数的目的是导出区块中所有的Signature，作者定义了一个结构体，用于存放与签名相关的信息
1 | type rData struct { |
2 | sig *btcec.Signature |
3 | H int64 |
4 | Tx int |
5 | TxIn int |
6 | Data int |
7 | } |
- sig：签名(包含r、s)
- H：交易所在区块的高度
- Tx：区块中的第几笔交易
- TxIn：交易中第几个TxIn
- Data：
该函数的返回值是这个类型：
1 | func getSignatures(maxHeigth int64, log btclog.Logger, db btcdb.Db) chan *rData {} |
具体过程就不说了，它主要就是通过一层层的循环将数据导出的(思想如下)：
1 | for block in chain: |
2 | for tx in block: |
3 | for input in tx: |
4 | ... |
search函数
使用dablooms这个Bloom过滤器，设置了容量、错误率等，都定义了常量
1 | const ( |
2 | tickFreq = 10 |
3 | bloomSize = 100000000 |
4 | bloomRate = 0.005 |
5 | ) |
这里作者设置的容量是100000000，我觉得在2014年这个数据容量应该足够了1filter := dablooms.NewScalingBloom(bloomSize, bloomRate, "blockchainr_bloom.bin")
主要的提取过程前面提到了分为两步代码如下：
1 | if step == 1 { |
2 | b := rd.sig.R.Bytes() |
3 | if filter.Check(b) { |
4 | matches++ |
5 | potentialValues.Add(rd.sig.R.String()) |
6 | } else { |
7 | if !filter.Add(b, 1) { |
8 | log.Warn("Add failed (?)") |
9 | } |
10 | } |
11 | } else if step == 2 { |
12 | if potentialValues.Contains(rd.sig.R.String()) { |
13 | matches++ |
14 | rMap[rd.sig.R.String()] = append(rMap[rd.sig.R.String()], rd) |
15 | } |
Signatures是调用getSignatures获得的，前文有提到过
1 | signatures := getSignatures(maxHeigth, log, db)//获取签名 |
- 第一步，通过循环导出的signatures将签名R赋值给b然后通过过滤器过滤，判断签名是否在过滤器中出现过，如果出现过那么就把它添加到potentialValues中
- 第二步，再一次循环signatures判断R是否存在于第一步生成的集合potentialValues中，如果存在将其详细信息添加到rMap中，键值是签名R，也就是说如果存在重复的R就会添加进去多组相关信息。说一下rMap的类型：
1 | rMap := make(map[string][]*rData) |
key是string类型，value是rData类型的集合，所以它的索引中存储的是签名R，value是一个存储多组R的相关信息的集合，这样的话前面我说的应该也就明白了。最后search函数返回rMap
main函数
首先给出了区块数据的路径以及数据库类型：
1 | var ( |
2 | dataDir = flag.String("datadir", filepath.Join(btcutil.AppDataDir("btcd", false), "data"), "BTCD: Data directory") |
3 | dbType = flag.String("dbtype", "leveldb", "BTCD: Database backend") |
4 | ) |
之后通过btcdbSetup函数设置了btcdb：
1 | log, db, dbCleanup := btcdbSetup(*dataDir, *dbType) |
再调用search函数导出区块中重复签名R以及它们的相关信息
1 | duplicates := search(log, db)//返回值是rMap |
作者新定义一个与导出集合类型一致的map，(value是存储的该签名R相关的信息的一个数组，也就是说存储着多组不同的rData)这段代码非常重要，是作者整个思想的核心，通过循环判断value数组的长度是否大于一，若是则证明签名R是重复的，若不是则签名R不重复。
1 | realDuplicates := make(map[string][]*rData) |
2 | for k, v := range duplicates { |
3 | if len(v) > 1 { |
4 | realDuplicates[k] = v |
5 | } |
6 | } |
最后将上文代码中的realDuplicates导出成文件，至此完成了整个比特币网络中相同签名R及其相关信息的导出。
总结
作者阐述通过一系列的公式验算以及相关的新闻，我们不难发现这种根据相同的签名R来盗取比特币的行为确实存在过，所以我们知道了k的重要性，一定要保证k值的保密性、唯一性，文章后面一部分作者提到了解决方法，在生成随机数k的时候使用RFC 6979，k=SHA256(d + HASH(m))，通过私钥d，和消息m来生成随机数k，这样的话，d保证了其保密性，hash(m)又保证了其唯一性，所以整个公式已经满足了我们的需要。