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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (9): 112-114.

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

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

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

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-03-21 发布日期:2011-03-21

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

摘要/Abstract

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

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

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

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

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]	赵太飞，尹航，赵思婷. 抗去同步化的高效RFID双向认证协议[J]. 计算机工程与应用, 2019, 55(12): 90-96.
[2]	王永1，2，陈燕1，赵毅1. 基于分段Logistic映射的并行Hash函数构造算法[J]. 计算机工程与应用, 2018, 54(15): 38-43.
[3]	崔恒山，田袁，邓绍江. 使用双向耦合映像格子改进的并行混沌Hash函数[J]. 计算机工程与应用, 2016, 52(4): 88-93.
[4]	李慧佳，龙敏. 基于混沌映射的HMAC算法设计与分析[J]. 计算机工程与应用, 2015, 51(22): 109-114.
[5]	和斌涛1，刘丽华1，邓方安1，王尚平2. 基于混沌消息扩展的Hash函数[J]. 计算机工程与应用, 2015, 51(14): 78-83.
[6]	李志文，张伟. 一种面向大规模短特征集的字符串匹配技术[J]. 计算机工程与应用, 2014, 50(1): 105-110.
[7]	李婧，李志慧，赖红. 基于Hash函数的无分发者的多秘密共享方案[J]. 计算机工程与应用, 2012, 48(18): 64-65.
[8]	李志敏，徐馨，李存华. 一个新的MD4消息差分[J]. 计算机工程与应用, 2011, 47(32): 94-97.
[9]	陈莉，王唯贤. 改进的可认证邮件传递协议及其安全属性分析[J]. 计算机工程与应用, 2011, 47(21): 112-114.
[10]	任姣霞1，王尚平2，张亚玲1，韩照国1. 链接变量循环的Hash函数结构[J]. 计算机工程与应用, 2011, 47(20): 53-55.
[11]	袁阳^1，2，赵耿^1，2，沈薇^1，2. 数字签名技术中混沌哈希函数的构造与分析[J]. 计算机工程与应用, 2010, 46(9): 92-94.
[12]	张栋^1,2,李梦东²,沈薇^1,2. MD4杂凑函数的近似碰撞[J]. 计算机工程与应用, 2009, 45(4): 89-92.
[13]	杨超,何小海. 一种基于混沌Hash函数的脆弱水印算法[J]. 计算机工程与应用, 2008, 44(17): 74-77.
[14]	李波刘平王张宜. SHA-256输出序列的随机性研究[J]. 计算机工程与应用, 2007, 43(9期): 142-144.
[15]	李晨,王世红. 基于改进混沌Hash函数的一次签名方案[J]. 计算机工程与应用, 2007, 43(35): 133-136.