Analysis and improvement of preimage attack on MD-4

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (9): 112-114.

• 网络、通信、安全 • Previous Articles Next Articles

Analysis and improvement of preimage attack on MD-4

YAN Na1，2，LI Mengdong2，CHEN Shaohui1，2

1.School of Communication Engineering，Xidian University，Xi’an 710071，China
2.Department of Information Security，Beijing Electronic Science and Technology Institute，Beijing 100070，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-03-21 Published:2011-03-21

MD-4原象攻击的分析与改进

阎娜1，2，李梦东2，陈少晖1，2

1.西安电子科技大学通信工程学院，西安 710071
2.北京电子科技学院信息安全系，北京 100070

Abstract

Abstract: The preimage attack of MD-4 is discussed.Leurent’s method explores chiefly three properties of MD-4：The absorption properties of boolean function，reversibility of the iterative process and specificity of message expansion.After their pseudo preimage attack a tree-based method is followed to transform pseudo preimage to true preimage.Tree-based method is replaced with random graph method.The complexity of the attack reduces to 298 from 2102.

Key words: Hash function, Message Digest-4（MD-4） algorithm, directed random graph, preimage attack

摘要： 首先分析了Leurent提出的MD-4原象攻击方法，该方法利用MD-4布尔函数的吸收性质，迭代函数的可逆性以及消息扩展方式的特殊性，首先形成伪原象攻击，之后利用基于树的方法将伪原象转变为原象攻击。采用随机图的方法，对其后一部分进行了改进，提高了攻击效率，将复杂度从2102降低到298。

关键词: Hash函数, 消息摘要算法第4版, 有向随机图, 原象攻击

YAN Na1，2，LI Mengdong2，CHEN Shaohui1，2. Analysis and improvement of preimage attack on MD-4[J]. Computer Engineering and Applications, 2011, 47(9): 112-114.

阎娜1，2，李梦东2，陈少晖1，2. MD-4原象攻击的分析与改进[J]. 计算机工程与应用, 2011, 47(9): 112-114.

[1]	ZHAO Taifei, YIN Hang, ZHAO Siting. Anti-Desynchronization and Efficient RFID Mutual Authentication Protocol [J]. Computer Engineering and Applications, 2019, 55(12): 90-96.
[2]	DENG Qingwen, LIN Zhixian, GUO Tailiang. Multi table image hash retrieval method based on principal component [J]. Computer Engineering and Applications, 2018, 54(3): 192-199.
[3]	WANG Yong1，2, CHEN Yan1, ZHAO Yi1. Parallel Hash function construction based on piecewise Logistic map [J]. Computer Engineering and Applications, 2018, 54(15): 38-43.
[4]	LI Juanjuan1, GONG Xiangyang2. Fast cloned tags detection algorithm in large-scale RFID systems [J]. Computer Engineering and Applications, 2017, 53(8): 106-112.
[5]	CUI Hengshan, TIAN Yuan, DENG Shaojiang. Improved parallel chaotic hash function using two-way coupled map lattice [J]. Computer Engineering and Applications, 2016, 52(4): 88-93.
[6]	HUANG Ping, YANG Xiaodong, WANG Caifen. On-line/off-line signature scheme with strong unforgeability [J]. Computer Engineering and Applications, 2016, 52(3): 81-84.
[7]	YU Chunwu, GUO Longfei, ZHANG Jian. HBL: lightweight Hash function [J]. Computer Engineering and Applications, 2016, 52(20): 1-4.
[8]	LI Huijia, LONG Min. Design and analysis of HMAC algorithm based on chaotic maps [J]. Computer Engineering and Applications, 2015, 51(22): 109-114.
[9]	MENG Jinfeng, GAO Zhonghe. Flow sampling measurement algorithm based on dynamic counting bloom filter [J]. Computer Engineering and Applications, 2015, 51(17): 92-95.
[10]	HE Bintao1, LIU Lihua1, DENG Fang’an1, WANG Shangping2. Hash function based on chaotic message expansion [J]. Computer Engineering and Applications, 2015, 51(14): 78-83.
[11]	WEN Yamin1, LI Fengxia2, GONG Zheng3, TANG Shaohua2. Optimized implementation of Quark hash function for lightweight AVR microcontrollers [J]. Computer Engineering and Applications, 2014, 50(23): 104-107.
[12]	LI Zhiwen, ZHANG Wei. String matching technology for large-scale short pattern set [J]. Computer Engineering and Applications, 2014, 50(1): 105-110.
[13]	GAO Shujing. Hash function based on multiple input signature analysis registers [J]. Computer Engineering and Applications, 2013, 49(21): 95-97.
[14]	LI Jing, LI Zhihui, LAI Hong. Multi-secret sharing scheme without dealer based on Hash function [J]. Computer Engineering and Applications, 2012, 48(18): 64-65.
[15]	ZHAO Huanhuan，XU Yong，ZHU Xiaowei. Optimized rekeying program for secure multicast [J]. Computer Engineering and Applications, 2011, 47(34): 98-100.

Analysis and improvement of preimage attack on MD-4

MD-4原象攻击的分析与改进

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics