区块链未来的安全铠甲:抗量子密码技术

pow'er北京峰会

分享嘉宾

韦云川,北京理工大学博士、加州大学戴维斯分校访问学者、IEEE会员、中国计算机学会CCF会员。现任BitAsset Labs首席科学家。在区块链技术、无线通信安全、抗量子密码技术等领域有广泛研究和积累。曾荣获中国航天科技集团一院技术改进奖一等奖。学术论文曾被顶级国际会议 IEEE INFOCOM 录用并作专题报告,研究成果发表于IEEE Trans. Mobile Computing、Computer Networks等顶级期刊,获得10余项发明专利授权。

分享环节

1. 前言

目前区块链的应用领域已经十分广泛,2018年由工业和信息化部主编的《2018年中国区块链产业白皮书》中提到了供应链金融、物联网等22个重点应用领域。当然区块链的应用领域并不仅仅局限在这22个领域,任何高价值数据的管理、流通与共享都可以用区块链。

另外区块链在数据安全、网络安全方面也起到重要的作用。美国国防部正在尝试利用区块链技术创建一个黑客无法入侵的安全信息服务系统,北约也在探索使用区块链技术开发下一代军事系统以实现北约网络防御平台的现代化。我军也在积极探索区块链在军事领域的应用价值。区块链在越来越多的重要场景中被应用,在这些场景中安全性是非常重要的。但是,目前区块链本身存在严重的安全问题。

2018年,是区块链发展最迅猛的一年,全球加密货币总市值一度接近8000亿美金。但层出不穷的漏洞,使2018年成为黑客最为猖獗的一年。安全事件的频发,严重阻碍了区块链的健康发展,不仅给用户带来了不小的损失,还直接导致了许多项目的“终结”。

2. 2018年区块链行业安全问题回顾

*本章节数据和图表引用自bcsec、猎豹区块链安全中心。

2018年,无论是安全事件的数量,还是造成的损失,都呈现指数级上升:

区块链未来的安全铠甲:抗量子密码技术 | 火星号精选

图2-1 安全事件造成的经济损失趋势(万美元)

区块链未来的安全铠甲:抗量子密码技术 | 火星号精选

图2-2 重大安全事件数量统计

3. 区块链面临的安全问题分析

 3.1.密码算法的安全问题

一般来说多数区块链中使用的通用标准密码算法在目前是安全的,但是这些算法从间接和未来看也存在安全隐患。

首先从间接来看,SHA256算法对应的ASIC矿机以及矿池的出现打破了中本聪设想的“一CPU一票”的理念,使得全网节点减少,权力日趋集中,51%攻击难度变小,对应的区块链系统受到安全性威胁。

其次从未来发展看,2018年3月6日Google宣布制造了72量子比特的量子计算机“Bristlecone”。随着量子计算的兴起,实用的密码体制都存在安全威胁。根据对传统密码算法和量子计算算法的研究,量子计算对现有密码体制的威胁如下表所示:

加密算法类型作用安全基础安全性威胁
AES对称密码加密——攻击难度减半
SHA256哈希函数数据指纹——-攻击难度减半
RSA非对称密码签名、密钥生成大整数分解可被完全破解
ECDSA、ECDH非对称密码签名、密钥交换椭圆曲线离散对数可被完全破解
DSA非对称密码签名、密钥交换离散对数可被完全破解

 另外,虽然哈希算法在设计时考虑了抗碰撞,SHA256等算法在现在也是相对安全的,但是也存在对哈希算法的碰撞攻击和针对Merkle-Damgard散列函数(在区块链中被广泛使用的SHA-256也是此类算法)的长度扩展攻击,这些攻击方式有可能会对哈希算法造成威胁。

而对于新型密码,由于其没有经过足够的时间检验和充分的攻防考验,其在实际应用中更容易成为短板。比如NehaNarula和她的团队在麻省理工学院媒体实验室的数字货币计划中发现IOTA哈希算法中的致命漏洞,使得IOTA团队紧急更换算法。

区块链中的算法曾经出现过随机数漏洞。对于区块链而言,随机算法十分重要,使用密码学安全的随机数(甚至是真随机)来生成私钥。对于大额资产来说,甚至应考虑冷存储的方式来离线、断网的保管私钥。但即便这样还不够,因为签名也需要安全,签名交易时同样需要随机数,该随机数的品质决定了私钥的安全。但是,不同的币种在实现各自随机算法的过程不同,有的采用了浏览器服务器端随机数函数Math.Random,有的采用键盘输入或者鼠标点击生成对应函数,有的采用了单词语句的方式等,进而导致随机数算法漏洞,发生被攻击事件。

由于区块链大量应用了各种密码学技术,属于算法高度密集工程,在实现上较容易出现问题。例如,NSA对RSA算法事先埋入后门漏洞,使其能够轻松破解别人的加密信息。一旦爆发这种级别的漏洞,区块链的基础都将不再安全,后果极其可怕。另外,根据理论分析,如果在签名过程中两次使用同一个随机数,就能推导出私钥。

 3.2.协议的安全问题

 协议安全在网络层表现为P2P协议设计安全,利用网络协议漏洞可以进行日蚀攻击和路由攻击。黑客利用一个节点的出度受限可以用日蚀攻击将节点从主网中隔离,出度越多、节点随机化链接程度越高,黑客的攻击难度就越大。网络协议的好坏通常决定了信息流转的能力,由于P2P网络结构不同,以太坊就远比比特币更容易受到日蚀攻击的影响。

协议安全在共识层表现为共识协议安全。首先共识协议本身存在安全问题,由于不同共识协议容错能力不同,PoW存在51%算力攻击,PoS存在51%币天攻击,而DPoS和DAG还存在着中心化风险。

3.3.软件实现的安全问题

实现安全风险包括:系统实现代码漏洞带来的安全风险;智能合约语言自身与合约设计,以及智能合约代码都可能存在漏洞,带来一定的安全风险;系统实现的业务设计缺陷导致的安全风险。具体包括如下27类:

(1)以太坊编程语言Solidity漏洞;

(2)以太坊短地址漏洞;

(3)交易顺序依赖性;

(4)时间戳依赖性;

(5)可重入性攻击;

(6)The DAO漏洞;

(7)Parity多重签名钱包合约漏洞;

(8)Parity多重签名钱包提款漏洞;

(9)太阳风暴;

(10)智能合约fallback函数;

(11)智能合约递归函数(recursive);

(12)调用深度限制(call depth);

(13)以太坊浏览器Mist;

(14)区块链节点漏洞;

(15)日食攻击(eclipse attack);

(16)Geth客户端DoS攻击漏洞;

(17)浪子合约漏洞;

(18)自杀合约漏洞;

(19)贪婪合约漏洞;

(20)遗嘱合约漏洞;

(21)挖矿中心化;

(22)冷热存储误用;

(23)BEC智能合约batch Transfer函数漏洞;

(24)智能合约proxy transfer函数整数溢出漏洞;

(25)Equihash漏洞;

(26)系统实现代码漏洞;

(27)系统业务设计缺陷。

3.4.用户使用的安全问题

区块链使用过程中,私钥的生产、存储、保管等带来的安全风险。区块链上的信息具有不可篡改性,其前提是私钥是安全的。但是私钥的保护存在一系列的安全风险,如私钥托管容易造成监守自盗以及黑客盗取;区块链钱包的口令存在被恢复的危险;私钥一旦丢失,便无法对账户的资产做任何操作;私钥一旦被黑客拿到,就能转移数字货币。

目前,普遍采用的私钥存储方案是由区块链系统中每个用户自行将私钥加密后保管在用户设备上,但无法抵抗攻击者在获取用户设备后对其使用的离线字典攻击,因此区块链面临私钥被窃取的风险。私钥一旦丢失即无法找回,用户将无法对账户资产做任何操作,导致资产被盗。

 

3.5.传统网络安全问题

区块链系统本身还面临着病毒、木马等恶意程序的威胁,大规模DDoS攻击、DNS污染、路由广播劫持等传统网络安全风险。具体地,攻击者为了窃取数字货币可以采用BGP路由广播劫持方法。另外,区块链系统被攻击者作为攻击目标,通过发起DDoS攻击导致区块链系统暂时无法提供服务。

 

4.  密码技术发展历史

4.1.古典密码

从古代到19世纪末的手工密码阶段。这个时期由于生产力水平低下,密码形式还处于比较低级的阶段,比如象形文字就可以看作是一种原始的密写术。我们称这个时期的密码体制为“古典密码体制(classicalcryptography)”。古典密码体制主要有两大类,移位密码(transpositioncipher)和替换密码(substitutioncipher)。它们都可以利用“手工作业”进行加解密处理,与此对应的密码分析也基本上是“手工作业”。

举例:比如A部落给B部落传递一个信息M,为了不让敌方部落获悉信息。A部落先用一块布缠绕在一根特定尺寸的木头上,然后写上打算传递的信息。写完解开布,送去给B部落,并让可靠的信使告诉B部落木头的尺寸。B部落用相应尺寸的木头,把写了秘密的布缠绕上去,即可解读正确的信息。敌方部落截获了这块布,因为不知道用什么尺寸的木头进行缠绕,就难以破译信息。

区块链未来的安全铠甲:抗量子密码技术 | 火星号精选

从现代密码的视角:部落间传递的信息M为明文,木头尺寸为密钥,写上信息的布为密文。 

古典密码编码方法归根结底主要有两种,即置换和代换。把明文中的字母重新排列,字母本身不变,但其位置改变了,这样编成的密码称为置换密码。最简单的置换密码是把明文中的字母顺序倒过来,然后截成固定长度的字母组作为密文。代换密码则是将明文中的字符替代成其他字符。

一些经典的古典密码,例如凯撒密码被用于高卢战争,采用将英文字母向前推移K位,以此字母替代明文。

在欧洲的法国外交官维吉尼亚,对贝拉索密码采用自身密钥体制,即以一个共同约定的字母作为起始密钥,以之对第一个密文脱密,得到第一个明文,以第一个明文为密钥对第二个密文脱密,此类类推,不会重复使用密钥,被后世称为维吉尼亚密码。

4.2.(近代密码)机械密码

从20世纪初到20世纪50年代末的机械密码阶段,这个时期的密码技术使用的是“机械计算部件”。在这半个世纪里,由于莫尔斯(SamuelF.B.Morse)发明了电报,利用电磁波进行通信己成为一个必然的趋势。为了适应电报通信,密码设计者设计出了一些采用复杂的机械和电动设备来进行信息加解密处理的方法。我们称这个时期的密码体制为“近代密码体制”。近代密码体制己被证明是不安全的,但是要想破译它们往往需要很大的计算量。

Enigma转轮机代表了机械密码发展的一个顶峰,但是在第二次世界大战中服役的Enigma却被完全破译。

区块链未来的安全铠甲:抗量子密码技术 | 火星号精选

典型代表:Enigm轮转机

4.3.(现代密码)电子密码

 从1949年开始的电子密码阶段。自从1949年香农(ClaudeE.Shannon)发表了划时代论文《保密体制的通信理论》之后,随着电子技术的发展,电子密码走上了历史舞台,催生了“现代密码体制”。特别是20世纪70年代中期,美国联邦数据加密标准密码算法(DataEncryptionStandard,DES)的公开,以及公共密钥(publickey)思想的提出,极大地促进了现代密码学的蓬勃发展。但是,广泛使用的“电子密码”的安全性大多没有得到完备性证明。

里程碑:

1949年香农(Claude Shannon)《保密系统的通信理论》,为近代密码学建立了理论基础。

1976年Diffie和Hellman发表的文章“密码学的新动向”一文掀起了密码学上的一场革命。

1978年,R.L.Rivest,A.Shamir和L. Adleman实现了RSA公钥密码体制。

1969年,哥伦比亚大学的StephenWiesner首次提出“共轭编码”(Conjugate coding)的概念。

1984年,H. Bennett和G. Brassard在次思想启发下,提出量子理论BB84协议,从此量子密码理论宣告诞生。其安全性在于:1、可以发现窃听行为;2、可以抗击无限能力计算行为。

1985年,Miller和Koblitz首次将有限域上的椭圆曲线用到了公钥密码系统中,其安全性是基于椭圆曲线上的离散对数问题。

1989年R. Mathews, D. Wheeler,L. M. Pecora和Carroll等人首次把混沌理论使用到序列密码及保密通信理论,为序列密码研究开辟了新途径。

2000年,欧盟启动了新欧洲数据加密、数字签名、数据完整性计划NESSIE,究适应于21世纪信息安全发展全面需求的序列密码、分组密码、公开密钥密码、hash函数以及随机噪声发生器等技术。

5.  量子计算机的威胁

5.1.现代密码学基石

现有的几乎所有的密码都是建立在一种类似单向函数的假设上的,也就是说我们需要寻找一个函数,它的计算复杂度是多项式时间可计算的,而他的反函数的计算复杂度不是多项式时间可计算的,例如RSA算法所基于的大数分解问题,ECC基于的离散对数问题,这些问题的解决难度都是要用“非确定性图灵机”在多项式时间内计算的问题,属于NP问题。而这两个公钥算法利用的则是基于这两个困难问题的单向陷门函数来实现的。而在量子计算条件下,部分NP问题有多项式时间的算法,也就是说这种一边儿是P问题,一边是NP问题的函数不再是单向函数了,即这些密码算法就无法使用了。

 

5.2.对公钥密码体制的影响

在1994年,PeterShor开发了一种用于整数分解的量子算法(Shor算法),该算法在多项式时间内运行,因此能够破坏任何RSA或离散的基于对象的密码系统(包括那些使用椭圆曲线的密码系统)。

对于量子计算机而言,所有广泛使用的公钥密码都是不安全的。

有人说:把RSA的长度从1024加到2048比特甚至更长,不就安全了吗?答案是:对于现有的经典计算机和算法,这样是可以的。但对于量子计算机和算法,这是徒劳的(除非RSA的长度增大到1GB或更长。但这样的话,算法还能用吗?)

 

5.3.对对称密钥体制的影响

Grover算法能够在O(√n)时间内反转函数。该算法会通过根因子降低对称密钥加密的安全性,因此AES-256只能提供128位的安全性。类似地,找到256位散列函数的前映像只需要2^128次。由于将哈希函数或AES的安全性提高两倍并不是非常繁琐,因此,Grover的算法不会对对称加密造成严重威胁,但是会降低安全性。

 

6.  后量子时代的来临

6.1.后量子密码是什么

在2015年,美国国家标准技术研究院(NIST)发布了一份后量子密码报告,对公钥密码算法的换代工作以及后量子子密码算法研究工作产生了极大的推动作用。NIST的后量子密码报告强化了量子计算机出现的预期,同时NIST也开始在全球范围内开展后量子密码算法标准的征集工作。2019年1月30日,NIST启动了第二轮征集工作。

区块链未来的安全铠甲:抗量子密码技术 | 火星号精选

后量子密码,是能够抵抗量子计算机对现有密码算法攻击的]新一代密码算法。所谓“后”,是因为量子计算机的出现,现有的绝大多数公钥密码算法(RSA、Diffie-Hellman、椭圆曲线等)能被足够大和稳定的量子计算机攻破,所以可以抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来,所以被称为“后”量子密码。也有人称之为“抗量子密码”,说的都是一个意思。

 

6.2.后量子密码算法基本要求

①    安全

②    运行速度快

③    通信开销合理

④    更广应用场景

 

6.3.主流后量子密码算法

①    基于编码的密码

基于编码的公钥密码体制利用纠错码对信息进行编码,并添加足够的随机错误信息,使得信息无法被攻击者破译,而接收方通过私钥进行纠错,最终恢复出原始信息。

②    基于格的密码

格密码主要用于构造加密、数字签名、密钥交换,以及众多高级密码学应用,如:属性加密(Attribute-based encryption)、陷门函数(Trapdoorfunctions)、伪随机函(Pseudorandomfunctions)、同态加密(Homomorphic Encryption)等,尽管格子密码系统的优化和安全性证明都需要极其复杂的数学,但基本思想只需要基本的线性代数,后量子性基于格上的一些困难性问题,如最短向量问题(shortest vectorproblem,SVP)、最近向量问题(closest vectorproblem,CVP)、SIS(small integersolutions)问题、LWE(learning with errors)问题,能抗量子计算机攻击。目前以1996年提出的NTRU(NumberTheoryResearchUnit)公钥密码体制最具影响力。

③    多变量密码

MQ密码体制。它的安全性基于有限域上非线性方程求解的困难性,代表方法/算法:HFE(Hidden Field Equations)、Rainbow(Unbalanced Oil and Vinegar(UOV)方法)、HFEv-等。

④    基于哈希算法的签名

哈希签名使用哈希函数的输入作为密钥并输出作为公钥。这些密钥仅适用于一个签名,因为签名本身会显示密钥的一部分。基于散列的签名的极端低效导致区块链使用Merkle树来减少空间消耗(是的,比特币中使用的相同Merkle树)。

不幸的是,用哈希构造KEM或公钥加密方案是不可能的。因此,基于散列的签名不是完整的后量子密码学的解决方案。而且,它们不是空间有效的;一种更有前途的签名方案SPHINCS产生41kb的签名和1kb的公钥/私钥。另一方面,基于散列的方案非常快,因为它们只需要计算散列函数。它们还具有极强的安全性证据,完全基于存在具有抗冲突和抗图像抗性的散列函数的假设。

由于没有任何迹象表明当前广泛使用的哈希函数(如SHA3或BLAKE2)容易受到这些攻击,因此基于哈希的签名是安全的。

⑤    基于超奇异椭圆曲线上的同源问题的密码

在椭圆曲线加密中,我们使用Diffie-Hellman类型协议来获取共享秘密,但是我们不是将组元素提升到某个幂,而是遍历椭圆曲线上的点。在基于同源的密码学中,我们再次使用Diffie-Hellman类型协议,但我们不是通过椭圆曲线上的点遍历,而是通过一系列椭圆曲线本身。

与其他后量子方案相比,基于同源的密码学具有极小的密钥大小,仅使用330个字节用于公钥。不幸的是,在这篇文章中讨论的所有技术中,它们是最慢的,对于密钥生成和共享秘密计算都需要11-13毫秒。然而,他们确实支持完美的前向保密,这不是其他后量子密码系统所拥有的。

⑥    基于辫群(braidgroups)的密码

辫群引起密码学学者兴趣的一个主要原因是其上有许多“难解”的数学问题,这些问题有的可用于构造新的密码体制,现在主要介绍涉及到的3类:(1)扭结共轭搜索问题(2)根搜索问题(3)子群成员判断问题

7.  总结与思考

面对量子计算机的必然到来,区块链行业已经在布局和谋划对策,越来越多的公链项目开始提出抗量子攻击的方案。比如一个由美国UNC大学著名教授发起的公链项目,就提出了非常全面、具体的抗量子解决方案,并得到美国NIST密码专家的高度肯定。我们有理由相信,以这类项目为代表的一批公链项目将会引领区块链行业迈上安全新台阶。