最近看了一些加密货币中使用的签名算法,其中IOTA使用的Winternitz一次性签名(WOTS)确实很有趣,这是一种hash签名,虽然几十年前就已经提出来了,不过一直没什么人用,因为生成的签名实在太长了,而且也看不到什么明显的优点,不过近几年因为量子密码的研究以及区块链技术倒是捞了这类签名一把,因为这种基于hash的签名算法被认为是可以抵抗量子计算的,不过这种算法也存在地址不能重用的问题,每次签名都会暴露私钥的一半,下面我们就介绍一下WOTS在IOTA中的应用以及存在的问题

IOTA简介

在这里先简单说一下IOTA,这是个瞄准了物联网市场的项目,有别于传统的区块链项目,IOTA使用的结构是有向无环图(DAG),比如下面就是一个包含了20个块的IOTA结构

在IOTA中这样的结构被称为Tangle,不同于比特币那样的链式结构,这是一个网状的结构,所以也有一些人质疑IOTA这样的技术是否能被称之为区块链

此外IOTA还有几个特点,首先它的交易是免交易费的,也没有什么矿工之类的,在整个网络里每个块就代表一个交易,你自己签署一笔交易后在Tangle中找两个还未得到确认的块(Tips)验证其交易后使自己的交易指向这两个块,然后进行适当的POW计算过程使交易的hash满足要求,所以你可以将用户当成这个系统中的矿工,大家自己开采包含自己交易的块,这个POW过程的难度很小,所以大家基本上几分钟内都可以完成。这种模式也是为了物联网而设计,适用于高并发但数据量较小的系统。

其中IOTA的共识达成的过程也很有意思,包含新的交易如何选择其要指向的交易以及IOTA如何防止双花等等,因为不是本文的重点,在这里就不展开说了,有兴趣的可以看这一系列文章,how IOTA works under the hood

不过需要指出的是因为在IOTA中发送垃圾交易的成本非常低,所以限于网络的规模以及IOTA的技术还不够成熟,目前的IOTA为了防止51%攻击还是要靠一个协调节点(coordinator node)来对网络进行审查,被它的交易确认的块才是主链,现在的IOTA事实上还是一个偏向于中心化的系统,按照其负责人的说法等未来网络规模扩大,节点数量足够多时就会撤销这一协调节点。

另外在IOTA中比较特别的就是它采用的是三进制,因为三进制架构的电路功耗是较低的,IOTA的创始人认为未来将会是三进制电路的世界,不得不说IOTA确实是走在了前列,包括采用三进制以及抗量子的算法。

顺带一提三进制系统可以分为平衡三进制和非平衡三进制这两种,在三进制系统里对应我们二进制系统中的bit的是叫trit,在平衡三进制中可取的三个值为-1(T),0和1,而非平衡系统中则取0,1和2。

在IOTA中我们使用的是平衡三进制,在这个系统里一个字节表示Tryte,其中包含3个trits,也就是说可取的范围是3^3=27,这跟2进制世界里一个byte包含8个bit还是有较大区别,IOTA为Tryte构建了对应的字母系统,由26个英文字母与数字9组成,如下表

下面提到的公私钥以及hash算法等都是基于这样的三进制系统,不得不说就目前而言直接采用三进制还是带来了很多麻烦,毕竟目前的机器还都是2进制的,跑它的算法并木有什么加成,而且软件层面还是得先进行转换,这样就牺牲了一定的效率,只能说IOTA的团队还是比较有想法吧

hash签名

下面我们简单介绍一下hash签名,其实它非常简单,至少其原理是比RSA和ECC等其他公钥密码要简单的多,首先我们从最简单的Lamport一次性签名来认识一下

Lamport One Time Signature (OTS)

首先我们随机生成一对私钥,每个私钥都包含256个随机数,这里每个随机数都取256bit大小,确实私钥是非常长的,如下

然后我们将这一对私钥中每个随机数都进行hash,得到了公钥对

然后我们就可以开始签名了,对于文件M,首先计算得到它的hash值,H(M),这里H(M)也是256bit长的,然后我们检查H(M)的每一个bit,对于第n个bit,当其为0时,我们就取私钥串1的第n个数,当其值为1时,我们就取私钥串2的第n个数,比如当文件M的hash为110...10时,情况就如下

将红色块的数字合并就得到了文件M的签名,至于该签名的验证也非常简单,我们计算出M的hash后依据同样的算法再从公钥对中取值,将公钥中的hash合并后看是否跟签名相同即可

观察上面的签名过程,我们不难发现发布签名后实际上我们将私钥的一半公布出去了,哪怕是这样其实这种算法也是很安全的,因为攻击者并不知道另一半的私钥,除非他能破解该hash函数,从公钥推出私钥

不过如果你再次使用该私钥进行签名的话,那么又会随机暴露一半的私钥,相当于在之前没暴露的一半里再随机显示一半,这样你暴露的私钥就达到了75%,这样就非常危险了,攻击者已经有能力根据这暴露的私钥信息伪造签名了,所以说hash签名的地址一般都是一次性的,重复使用是不可取的,当然,也不是说就不存在地址可重复使用的hash签名技术,比如基于Merkle树的Merkle OTS方案,该方案使用的公钥是一串公钥对的根hash,事实上每次签名使用的依然是不同的私钥,而且该方案的签名长度更长,公钥对较多的话签名长度可能是Lamport方案的几倍,有兴趣的可以看看这篇文章,Hash based signatures

Winternitz One Time Signature (WOTS)

下面我们进入正题,在IOTA中使用的签名方案是WOTS,跟Lamport方案一样,它每次签名也会暴露私钥的一半,不过它的暴露形式却不那么一样,还是比较有趣的

IOTA的私钥与地址

我们先简要了解一下IOTA中的私钥与地址的产生模式,因为每个地址都只使用一次,所以在钱包中每次都会产生一个新的地址来进行交易,一般是使用一个种子来生成这一系列的私钥

IOTA的种子也是遵循三进制的,其使用的字母就是我们前面提到的26个字母加9,长度为81,按照官方推荐的种子生成方法,我们也可以自己产生安全的种子,在linux和mac上可以分别使用下面的命令

>>>cat /dev/urandom |tr -dc A-Z9|head -c${1:-81} //linux
>>>cat /dev/urandom |LC_ALL=C tr -dc 'A-Z9' | fold -w 81 | head -n 1 //Mac

如下

由种子我们可以产生私钥,值得一提的是在IOTA中还包含了三种安全等级,代表了不同的私钥长度

总的私钥长度为2187 * 安全等级 trytes

在官方钱包中默认的安全等级为2,所以一般我们在Tangle中看到的交易都是使用的安全等级为2的地址,在不同的安全等级下给种子加上对应的index即可得到不同的私钥,结构如下

然后我们来看看派生出私钥后如何得到公钥地址

首先将私钥划分成L份,每份都是81 trytes,所以L = 安全等级 * 27

然后我们将每一块都hash 26次,然后再合并得到digest,这是IOTA的说法,然后hash digest两次即可得到地址,也就是公钥,过程如下

IOTA中的WOTS签名

下面我们来看看IOTA中的签名过程

对于消息M,我们首先计算出它的hash H(M),不过这里使用的是IOTA中的基于三进制的hash算法,跟前面使用的hash算法一样,所以它的输出也是三进制的Tryte字母串

此外值得一提的是IOTA一开始使用的Curl哈希算法是存在问题的,后来就换成了目前的Kerl算法,当时也发生了一些纠葛,有兴趣的可以去了解了解

对于要签署的hash值H,首先我们依然是按照前面计算地址的方法将私钥分成L份,然后根据H中第N个Tryte的值来计算第N份的hash次数Ni,计算方式如下

Ni = 13 - TtoD(H[N])

TtoD表示将该Tryte转换为10进制,转换表即为前面那个Tryte的字母表

比如我们随便取一串hash,ABC......

之后的验证过程也很简单

我们将签名划分为L份,然后根据H中第N个Tryte的值来计算第N份的hash次数Nj,计算方式如下

Ni = 13 + TtoD(H[N])

对于上面的签名验证过程如下

当签名值正确时我们验证过后得到的digest就相当于把私钥hash了26次,所以这样与公钥验证就是符合的

看到这里你可能有些奇怪,貌似在这个过程里并没有直接暴露私钥啊,不过严格来说还是会暴露一部分的,当要签名的hash中包含Tryte字符M时,因为其对应的十进制为13,所以在签名时相当于对应位置的私钥并没有hash,这一块的私钥就暴露了,不过这并不是对WOTS的真正威胁所在

在继续之前我们有必要先了解一下IOTA的交易结构

IOTA的bundle结构

之前我们也提到了在IOTA中每个块都是一笔交易,事实上如果按照其他传统的区块链系统的标准来看,这些交易是不完全的,在IOTA中真正的交易其实是bundle

IOTA中的交易模型类似于比特币的UTXO,我们不妨来看看一个bundle的例子

从图中我们可以看出一个bundle类似于比特币,可以有多个VinVout,我们来看看bundle中一个交易的基本结构

{ 
  hash: 'WCWHEXQXTEWYSGGPTITZVJNENDGXVF9KTEJMLSEGQEMOJHJJKFXVRENQWARBFLXOBPMWAUQYRDCTZ9999',
  signatureMessageFragment: 'ASQNBNJCJXJIITXEWFDIXEEROSDITNETRMETJWHLNEVXBXSHJWV......',
  address: 'TDIJAKIZYMBFUHRXXPTOFNMC9UPJQJBPELGMQWJOULAYSNKRPYKTMBZOEITGBMMGI9JMAVDNO9QNGOMFY',
  value: -6062321,
  obsoleteTag: 'MINEIOTADOTCOM9999999999999',
  timestamp: 1526454765,
  currentIndex: 4,
  lastIndex: 6,
  bundle: 'WIIPVFKRGKVEXGEEPQROFWRSDLW9WONYVTCGJDWJREGXPLGVSJAVJSKYHHZDWBX9JUISRTCUVSXWLYCKW',
  trunkTransaction: 'LIWIJSQSZNUWMBWQMNSXZQNPGCCVVUKTRMWFHIUKTSMQZ9GCOCTFXVKXWTFBGYEKVCLJWWIBYOSWZ9999',
  branchTransaction: 'ASIETWSCPXMKGMP9I9QPUNHEETTOFCKKLQAEBEYBONQXOMXUBPDSJGUFEXWTD9AM9HADUESAKIRD99999',
  tag: 'MINEIOTADOTCOM9999999999999',
  attachmentTimestamp: 1526456063898,
  attachmentTimestampLowerBound: 0,
  attachmentTimestampUpperBound: 12,
  nonce: 'RMDY9PXCX9YPTCDUBPDOYDHSPQF'
}

因为签名信息实在太长,所以做了截取,其中value就代表这个交易的输入或是输出,此处表明此交易是这个bundle的输入,而currentIndexlastIndex则分别表示从0开始计数的此交易在该bundle中的序列位置以及该bundle中最后一个交易的序列位置,一般排在前面的都是输出的交易,后面的就是这样的包含签名的输入交易,下面的trunkTransactionbranchTransaction则分别表示被该交易批准的两个第一跟第二个交易,最后的nonce就是POW运算时进行修改的变量,使该交易的hash符合要求,也就是末四位为9,在该三进制系统里其实也就是0

另外还有值得一提的一点是这里的签名的长度都是2187个tryte,你可能会觉得奇怪,因为前面的签名过程里我们可以看到根据选择的私钥的安全等级不同,私钥长度不同,对应的签名长度也不同,只有安全等级为1时产生的签名长度才是2187 tryte,而在钱包默认的安全登记2下,签名的长度应该是2187 * 2 tryte

确实,这也是IOTA中又一比较奇怪的地方,对于这样的情况它是将签名分成两半在两个交易里进行发送的,再上图中其中一个是在input中value为负的一笔交易,另一个则是output中value为0的一笔交易,因为这两部分分别使用不同的hash片段进行验证,所以对签名的验证并没有影响,至于说为何这样设计,因为在IOTA中一笔交易的大小是固定的2673 tryte,里面所有的字段都是定长的,目的是方便解析器的解析,所以便采取了这样的方式,看起来确实是非常奇怪,而且这样的定长交易一定程度上也造成了网络资源的浪费,很多不包含签名的output交易也不得不在签名字段填充满9以满足长度需求

bundle hash

然后我们来看看上面的bundle,IOTA中也正是根据这一项将属于该bundle的交易划分到一起,再按index进行排列,可见IOTA中的交易结构还是比较特别的,这其中其实还有很多问题与细节,不过这里就不展开了,有兴趣的可以自己研究研究

大家应该也注意到这里的bundle值也是一串hash,其实这就是我们签名的对象,它会用每笔交易中的address, value, obsoleteTag,timestamp,currentIndexlastIndex生成hash,也就是bundle hash

不过我们签名及验证时使用的hash并不是直接取这里的bundle hash,而是会先进行一定的变换变成normalized bundle hash,具体过程如下

首先将81 tryte长的bundle hash均分为三部分,即每部分27 tryte,然后对这每部分分别计算其所以tryte转换为10进制后的和,即对于第一部分

sum0=TtoD(H[0][0])+TtoD(H[0][1])+...+TtoD(H[0][26])

得到三部分分别的总和sum后,接下来的目标就是将sum调整为0,当该部分总和大于0时,循环将该部分的第一个tryte减一,直到修改后sum为0,如果第一个tryte已经修改到了最小值,则从第二个tryte继续,一直往后直到sum为0,反之当sum小于0时亦然

修改完成后将这三部分组合即得到了normalized bundle hash,就如你所看到的,这其实是一个对bundlehash进行平衡的过程,这样的话在签名时按照前面的算法相当于平均每个私钥块都hash了13次,不过说正常来说一个完善的hash算法其分布也应该是均匀的,所以这一步目的也是为了修正下偏差,另外就是对签名的一道确认了,事实上这一步也算是降低了碰撞的时间复杂度,毕竟在hash值后面的tryte都相同的情况下为了使sum为0,最前面的tryte哪怕不一样最终得到的normalized bundle hash也是相同的,不过影响确实有限,在这里就忽略了

经过这一过程后我们可以说在经过一次签名后我们的私钥信息是被暴露了50%的,注意这里确实并不是直接暴露了私钥本身

要认识到这一点,我们不妨想一想在这样的WOTS机制下我们该如何伪造签名,我们直接从签名中得到的只有私钥平均hash了13次后的hash值,想要修改bundlehash直接找出对签名中hash的碰撞是不可能的,那么我们只能想办法修改bundlehash的同时也修改签名的值

因为我们知道了在原normalized bundle hash下签名得到的私钥各部分在bundle hash对应tryte 下的hash值,所以在这基础上我们也就可以计算这些hash进一步的hash,也就是说从这一部分hash知道digest部分的中间所有hash我们都是可以计算的,因为平均每块私钥都hash了13次,也就是说我们知道了这些私钥从13到26这些次数的hash值,也就是所有该私钥对应hash的一半,即我们获取了这些私钥信息的50%,这确实跟Lamport签名很不一样

不过修改了这一块的签名后我们就也得将normalized bundlehash的对应位的tryte减去对应的次数,修改部分越多要减去的也就越多,然而这样的话normalized bundlehash也会变得不满足要求,在验证签名时的normalized的过程中计算得到的sum就会跟0差很多,然后进行调整后得到的hash跟签名也就对不上了,除非你能逆向这个hash算法得到该私钥往前的hash值,这就又回到了原点,所以说仅使用一次的情况下该签名方案是安全的,一旦你使用了第二次,通过第二个签名我们就又可以得到随机的50%的hash,结合前面的那部分信息,我们就有可能修改签名与hash的同时又使得normalized bundle hash满足要求,即成功伪造签名

签名方案的漏洞

事实上IOTA的WOTS签名算法在开始也是存在问题的,这起源于去年在reddit上的这篇帖子,有人在重用了他的某个地址后发现存入该地址的钱被盗走,可以在这看到记录

该用户在使用该地址花费了一次后又向该地址转入了一笔钱,结果四个小时后这笔钱被盗走,一开始大家都猜是因为地址的重用,认为该用户在使用了该地址一次后不应该再次向该地址转入资金,不过按照我们前面的分析,仅仅只进行了一次签名的情况下暴露的私钥信息是有限的,除非黑客真的成功找到了一对碰撞,然而这也不应该是仅用四个小时就能完成的活,所以在分析过后发现是IOTA签名过程中存在问题

我们前面有提到当签名的hash中包含tryte字符M也就是十进制的13时,对应的私钥实际上是没有进行hash的,相当于直接在签名中暴露了,不过考虑到M出现的几率也就是1/27,所以这本来也不是什么大问题,但问题出在了IOTA的私钥的产生上

因为IOTA的私钥特别长,所以它的产生事实上也是一个不断hash的过程,利用了海绵函数的结构

图画的不是很好,不过大概是这么个意思,我们发现其实拿到了私钥的第一部分即H[0]后即可使用它迭代得到剩下的部分,生成整个私钥,现在我们再来看看该用户这一地址的第一笔bundle的bundlehash计算得到的normalized bundlehash

可以发现对应的normalized bundlehash第一个Tryte对应的值即为13,这表示该地址第一块的私钥被签名暴露了,通过签名我们可以计算得到该地址的私钥,可以参考这篇分析中的代码,reddit_key_recover.pycalc_private.py

最终得到私钥

这就意味着只要normalized bundlehash的第一个Tryte为M,该地址的私钥就是可以被获取的,算起来满足该条件的bundle也接近4%了,还是非常危险的,所以为了修复这一漏洞,现在签名时在计算normalized bundlehash时如果结果中包含M的话,会将index为0的交易中obsoleteTag字段加一,然后再算一次bundlehash,循环往复直到normalized bundlehash中不包含M为止

闲话

虽然在IOTA中重用地址是非常危险而不可取的,不过在该系统中目前倒也不是没有可重用地址,我们前面提到的协调节点,其使用的签名方案就是可重用地址的Merkle OTS,因为它确实有这样的需求,得去批准大量的交易以稳定网络,代价是更长的签名,目前社区中也在探讨可重用地址机制的可行性

此外有时候IOTA中的一些地址重用行为也是其快照机制导致的,在IOTA中为了节省存储空间,会定期清理Tangle上的交易,将它们清空,只在记录上保留有余额的地址,因为钱包在由其种子派生出的私钥中按index从上往下进行搜索时碰到余额为0的就会停止,所以在每次快照后有必要将index排在前面的余额为空的地址附加到Tangle上,否则就可能会出现地址的重用

参考链接

https://www.jinse.com/bitcoin/249863.html

https://draveness.me/iota-tangle

https://wusyong.gitbooks.io/iota-guidebook/content/

http://blog.lekkertech.net/blog/2018/03/07/iota-signatures/

点击收藏 | 0 关注 | 1
  • 动动手指,沙发就是你的了!
登录 后跟帖