基于Merkle哈希树结构的区块链第二原像攻击

doi:10.3969/j.issn.1671-1122.2018.01.006

信息网络安全 ›› 2018, Vol. 18 ›› Issue (1): 38-44.doi: 10.3969/j.issn.1671-1122.2018.01.006

基于Merkle哈希树结构的区块链第二原像攻击

王卯宁(), 段美姣

中央财经大学信息学院,北京100081

收稿日期:2017-10-20 出版日期:2018-01-20 发布日期:2020-05-11
作者简介:
作者简介：王卯宁（1987—）,女,山东,讲师,博士,主要研究方向为密码算法的分析与设计;段美姣（1985—）,女,河北,讲师,博士,主要研究方向为网络安全。
基金资助:
国家自然科学基金重点项目[U1509214];国家自然科学基金青年科学基金[61702570]

The Second-preimage Attack to Blockchain Based on the Structure of Merkle Hash Tree

Maoning WANG(), Meijiao DUAN

Department of Information, Central University of Finance and Economics, Beijing 100081, China

Received:2017-10-20 Online:2018-01-20 Published:2020-05-11

摘要/Abstract

摘要：

区块链是一种新兴的IT技术,具有去中心化、高效、透明等优势,被广泛认为具有颠覆性的应用前景。而应用场景的广泛性和应用层面的底层性决定了区块链的安全性必须得到保障。Hash函数是保证区块链可用性和安全性的重要基础之一。文章从区块链中的Hash函数角度出发,基于密码分析原理,针对区块链的特有结构和工作流程,利用区块链中Merkle树Hash函数叶子节点的Hash值具有相同地位这一性质,构造一类对已存在区块发起的第二原像攻击。理论分析证明此类第二原像攻击的复杂度低于平凡搜索攻击,在此基础上,描述了基于Hellman原理的攻击实例构造算法。结论表明,Merkle树Hash函数本身的数学结构和区块链交易记录的数据格式是影响区块链安全性的重要因素,今后在设计区块链系统时应当考虑此类因素。

关键词: 区块链, Merkle树, 第二原像攻击, Hellman时空平衡原理

Abstract:

Blockchain technology is a kind of emerging information technology model. It is widely regarded as a promising concept because of its advantages such as decentralization, high efficiency, and transparency. The breadth of application scenarios and the underlying layer of application determine that the security of the blockchain must be guaranteed. Hash functions are one of the most important foundations for providing the blockchain’s usability and security. Starting from Hash functions in the blockchain and based on the principle of cryptanalysis, this paper presents a type of second preimage attack on the existing blocks by employing the structure and workflow of the blockchain. Specially, the attack constructed in this paper uses the fact that the Hash values in the leaf nodes of a Merkle tree have the same status. After theoretical analysis of proving that the complexity of such an attack is lower than that of trivial brute-force, the attack’s concrete steps based on Hellman’s time-memory tradeoff principle are also described. The conclusion of the attack shows that both the mathematical structure of the Hash function itself and data format of blockchain transaction records are important to the security of the blockchain. This should be considered in the future when we design blockchain systems.

Key words: blockchain, Merkle tree, second-preimage attack, Hellman’s time-memory tradeoff;

中图分类号:

TP309

王卯宁, 段美姣. 基于Merkle哈希树结构的区块链第二原像攻击[J]. 信息网络安全, 2018, 18(1): 38-44.

Maoning WANG, Meijiao DUAN. The Second-preimage Attack to Blockchain Based on the Structure of Merkle Hash Tree[J]. Netinfo Security, 2018, 18(1): 38-44.

图/表 1

参考文献 27

[1]	NAKAMOTO S. Bitcoin: A Peer-to-peer Electronic Cash System[EB/OL]. ,2008-9-1.
[2]	SWAN M.Blockchain: Blueprint for a New Economy[M]. Sebastopol: O'Reilly Media, Inc., 2015.
[3]	KOSBA A, MILLER A, SHI E, et al. Hawk: The Blockchain Model of Cryptography and Privacy-preserving Smart Contracts[EB/OL]. .
[4]	EYAL I, GENCER A E, SIRER E G, et al. Bitcoin-NG: A Scalable Blockchain Protocol[EB/OL]. .
[5]	SASSON E B, CHIESA A, GARMAN C, et al. Zerocash: Decentralized Anonymous Payments from Bitcoin[EB/OL]. .
[6]	ZHANG Y, WEN J.The IoT Electric Business Model: Using Blockchain Technology for the Internet of Things[J]. Peer-to-peer Networking Application,2017, 10(4): 983-994.
[7]	CHRISTIDIS K, DEVETSIKIOTIS M.Blockchains and Smart Contracts for the Internet of Things[J]. IEEE Access, 2016, 4: 2292-2303.
[8]	bitcoinwiki. Common Vulnerabilities and Exposures[EB/OL].,2017-5-25.
[9]	bitcoinwiki. Weaknesses[EB/OL].,2017-7-4.
[10]	KIAYIAS A, PANAGIOTAKOS G. Speed-security Tradeoff s in Blockchain Protocols[EB/OL]. ,2015-12-1.
[11]	GERVAIS A, KARAME G O, WÜST K, et al. On the Security and Performance of Proof of Work Blockchains[C]//ACM. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, October 24 - 28, 2016,Vienna, Austria. Myers and Shai Halevi. New York, USA: ACM, 2016: 3-16.
[12]	STEVENS M, LENSTRA A K, De Weger B.Chosen-prefix Collisions for MD5 and Applications[J]. International Journal of Applied Cryptography, 2012, 2(4): 322-359.
[13]	STEVENS M, SOTIROV A, APPELBAUM J, et al. Short Chosen-prefix Collisions for MD5 and the Creation of a Rogue CA Certificate[EB/OL]..
[14]	STEVENS M. New Collision Attacks on SHA-1 Based on Optimal Joint Local-collision Analysis[EB/OL]. .
[15]	BHARGAVAN K, LEURENT G. Transcript Collision Attacks: Breaking Authentication in TLS, IKE,SSH[EB/OL].,2016-2-21.
[16]	GIECHASKIEL I, CREMERS C, RASMUSSEN K B. On Bitcoin Security in the Presence of Broken Cryptographic Primitives[EB/OL]. , 2017-8-29.
[17]	bitcoincore.org. Bitcoin Core[EB/OL].,2017-8-18.
[18]	HELLMAN M.A Cryptanalytic Time-memory Trade-off[J]. IEEE Transactions on Information Theory, 1980, 26(4): 401-406.
[19]	QUISQUATER J J, STANDAERT F X.Time-memory Tradeoffs[M]// Henk C.A.v. Tilborg. Encyclopedia of Cryptography and Security. New York:Springer,2005: 614-616.
[20]	BIRYUKOV A, SHAMIR A. Cryptanalytic Time/memory/data Tradeoffs for Stream Ciphers[EB/OL]. .
[21]	BIRYUKOV A, SHAMIR A, WAGNER D. Real Time Cryptanalysis of A5/1 on a PC[EB/OL]. .
[22]	SASAKI Y. Recent Applications of Hellman's Time-memory Tradeoff[EB/OL]. ,2015-9-1.
[23]	OECHSLIN P. Making a Faster Cryptanalytic Time-memory Trade-off[EB/OL]. ,2017-9-15.
[24]	BARKAN E, BIHAM E, SHAMIR A. Rigorous Bounds on Cryptanalytic Time/memory Tradeoffs[EB/OL]. , 2017-9-15.
[25]	QUISQUATER J J, STANDAERT F X, ROUVROY G, et al. A Cryptanalytic Time-memory Tradeoff: First FPGA Implementation [EB/OL].,2017-9-20.
[26]	HONG J, KIM B I.Performance Comparison of Cryptanalytic Time Memory Data Ttradeoff Methods[J]. Bulltin of the Korean Mathematical Society, 2016, 53(5): 1439-1446.
[27]	DINUR I, DUNKELMAN O, KELLER N, et al. Memory-efficient Algorithms for Finding Needles in Haystacks[EB/OL]. ,2017-10-9.

基于Merkle哈希树结构的区块链第二原像攻击

The Second-preimage Attack to Blockchain Based on the Structure of Merkle Hash Tree

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 27

相关文章 15

编辑推荐

Metrics

本文评价

[1]	边玲玉, 张琳琳, 赵楷, 石飞. 基于LightGBM的以太坊恶意账户检测方法[J]. 信息网络安全, 2020, 20(4): 73-80.
[2]	毛志来, 刘亚楠, 孙惠平, 陈钟. 区块链性能扩展与安全研究[J]. 信息网络安全, 2020, 20(3): 56-64.
[3]	郎为民, 张汉, 赵毅丰, 姚晋芳. 一种基于区块链的物联网行为监控和活动管理方案[J]. 信息网络安全, 2020, 20(2): 22-29.
[4]	姚萌萌, 唐黎, 凌永兴, 肖卫东. 基于串空间的安全协议形式化分析研究[J]. 信息网络安全, 2020, 20(2): 30-36.
[5]	周艺华, 吕竹青, 杨宇光, 侍伟敏. 基于区块链技术的数据存证管理系统[J]. 信息网络安全, 2019, 19(8): 8-14.
[6]	路爱同, 赵阔, 杨晶莹, 王峰. 区块链跨链技术研究[J]. 信息网络安全, 2019, 19(8): 83-90.
[7]	郑敏, 王虹, 刘洪, 谭冲. 区块链共识算法研究综述[J]. 信息网络安全, 2019, 19(7): 8-24.
[8]	周元健, 秦冬梅, 刘忆宁, 吕松展. 基于区块链的可信仓单系统设计[J]. 信息网络安全, 2019, 19(6): 84-90.
[9]	王文明, 施重阳, 王英豪, 危德健. 基于区块链技术的交易及其安全性研究[J]. 信息网络安全, 2019, 19(5): 1-9.
[10]	黑一鸣, 刘建伟, 张宗洋, 喻辉. 基于区块链的可公开验证分布式云存储系统[J]. 信息网络安全, 2019, 19(3): 52-60.
[11]	赵国锋, 张明聪, 周继华, 赵涛. 基于纠删码的区块链系统区块文件存储模型的研究与应用[J]. 信息网络安全, 2019, 19(2): 28-35.
[12]	王文明, 王全玉, 王英豪, 任好盼. 面向敏感区域的智能监控与预警数据库研究与设计[J]. 信息网络安全, 2019, 19(12): 1-9.
[13]	田秀霞, 陈希, 田福粮. 基于区块链的社区分布式电能安全交易平台方案[J]. 信息网络安全, 2019, 19(1): 51-58.
[14]	李佩丽, 徐海霞, 马添军, 穆永恒. 区块链技术在网络互助中的应用及用户隐私保护[J]. 信息网络安全, 2018, 18(9): 60-65.
[15]	段琼琼, 项定华, 史红周. 基于区块链的智能物件认证技术方案设计[J]. 信息网络安全, 2018, 18(9): 95-101.