MD5选择前缀碰撞算法的改进及复杂度分析

doi:10.11772/j.issn.1001-9081.2014.09.2650

计算机应用 ›› 2014, Vol. 34 ›› Issue (9): 2650-2655.DOI: 10.11772/j.issn.1001-9081.2014.09.2650

MD5选择前缀碰撞算法的改进及复杂度分析

程宽¹,韩文报²

1. 信息工程大学,郑州 450001；
2. 数学工程与先进计算国家重点实验室，郑州 450001

收稿日期:2014-02-10 修回日期:2014-03-06 出版日期:2014-09-01 发布日期:2014-09-30
通讯作者: 程宽
作者简介:
程宽(1990-),男,浙江武义人,硕士研究生,主要研究方向:哈希函数;
韩文报(1963-),男,河北广平人,教授,博士生导师,主要研究方向:哈希函数、公钥密码。
基金资助:
国家自然科学基金资助项目

Improvement on chosen-prefix collisions for MD5 and complexity analysis

CHENG Kuan¹,HAN Wenbao²

1. Information Engineering University, Zhengzhou Henan 450001,China
2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou Henan 450001,China

Received:2014-02-10 Revised:2014-03-06 Online:2014-09-01 Published:2014-09-30
Contact: CHENG Kuan

摘要/Abstract

摘要：

针对MD5选择前缀碰撞算法在实际应用时复杂度分布的失衡问题，提出了改进的MD5选择前缀碰撞算法。结合非相邻表示型(NAF)，给出了生日搜索复杂度中概率值在特定条件下的推导方式，建立了平衡参数与生日搜索复杂度之间的关系；并基于上述理论结果，通过引入新的消息差分，改进了选择前缀碰撞所需的生日碰撞形式，得到改进算法。在实际应用所需的参数条件下，改进算法相对MD5算法平均可降低1比特的复杂度。分析结果表明：相对于原MD5算法，改进算法缓和了复杂度分布的失衡现象，降低了算法复杂度，更适用于实际应用。

Abstract:

According to the unbalanced distribution of the complexity of chosen-prefix collisions under the practical requirement, an improved algorithm of chosen-prefix collisions for MD5 was designed. Combined with Non-Adjacent Form (NAF), the probability related to the complexity of birthday search was deduced under certain conditions, and the relation between the balance parameter and the complexity of birthday search was established. Then based on the above results, the improved algorithm was designed through improving the form of birthday collision by introducing new message block differences. Under the practical requirement for parameters, the complexity of the improved algorithm can reduce one bit on average. The results show that, compared with the original MD5, the improved algorithm defuses imbalance of complexity distribution, reduces the complexity, and is more suitable for practical applications.

中图分类号:

TP309

程宽韩文报. MD5选择前缀碰撞算法的改进及复杂度分析[J]. 计算机应用, 2014, 34(9): 2650-2655.

CHENG Kuan HAN Wenbao. Improvement on chosen-prefix collisions for MD5 and complexity analysis[J]. Journal of Computer Applications, 2014, 34(9): 2650-2655.

参考文献

［1］WANG X, FENG D, LAI X, et al.Collisions for Hash functions MD4, MD5, HAVAL-128 and RIPEMD ［EB/OL］.［2013-10-20］. http://eprint.iacr.org/2004/199.pdf.

［2］WANG X, YU H. How to break MD5 and other Hash functions ［C］// EUROCRYPT'05: Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, LNCS 3494. Berlin: Springer-Verlag, 2005: 19-35.

［3］STEVENS M. On collisions for MD5 ［EB/OL］.［2013-10-10］. http://www.win.tue.nl/hashclash/On20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf.

［4］STEVENS M, LENSTRA A K, de WEGER B. Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities ［C］// EUROCRYPT 2007: Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 4515. Berlin: Springer-Verlag, 2007: 1-22.

［5］STEVENS M, SOTIROV A, APPELBAUM J, et al.Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate［C］// CRYPTO 2009: Proceedings of the 29th Annual International Cryptology Conference, LNCS 5677. Berlin: Springer-Verlag, 2009: 55-69.

［6］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.

［7］ZHOU L. Research on key technologies of chosen-prefix collisions for MD5 ［D］. Zhengzhou: Information Engineering University, 2010. (周林.MD5选择前缀碰撞关键技术研究［D］．郑州:信息工程大学,2010.)

［8］STEVENS M. Counter-cryptanalysis［C］// CRYPTO 2013: Proceedings of the 33rd Annual Cryptology Conference, LNCS 8042. Berlin: Springer-Verlag, 2013: 129-146.

［9］RIVEST R L. The MD5 message-digest algorithm［DB/OL］. ［2013-10-10］. http://www.ietf.org/rfc/rfc1321.txt.

［10］HANKERSON D, MENEZES A, VANSTONE S. Guide to elliptic curve cryptography［M］. Berlin: Springer-Verlag, 2004: 132.

［11］WANG X,FEI D. Theory and implement of the elliptic curve public key cryptography［M］. Beijing: Science Press, 2006: 462-463. (王学理,斐定一.椭圆与超椭圆曲线公钥密码的理论与实现［M］.北京：科学出版社,2006:462-463.)

［12］CLARK W, LIANG J. On arithmetic weight for a general radix representation of integers［J］. IEEE Transactions on Information Theory, 1973, 19(6): 823-826.

［13］PAUL C, MICHAEL J. Collision search with cryptanalytic applications［J］. Journal of Cryptology, 1999, 12(1): 1-28.

[1]	孙晓玲李姗姗杨光杨秋格. 基于差分表的Blow-CAST-Fish的密钥恢复攻击[J]. 计算机应用, 0, (): 0-0.
[2]	樊缤李智高健. 基于多尺度知识学习的深度鲁棒水印算法[J]. 计算机应用, 0, (): 0-0.
[3]	郭丽峰王倩丽. 自适应安全的带关键字搜索的外包属性基加密[J]. 计算机应用, 0, (): 0-0.
[4]	沈子懿, 王卫亚, 蒋东华, 荣宪伟. 基于Hopfield混沌神经网络和压缩感知的可视化图像加密算法[J]. 计算机应用, 2021, 41(10): 2893-2899.
[5]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[6]	高健李智樊缤姜传贤. 基于光线投射采样和四元数正交矩的高效三维医学图像鲁棒零水印算法 [J]. 计算机应用, 0, (): 0-0.
[7]	徐丽云, 闫涛, 钱宇华. 基于级联混沌系统的分数域语音加密算法[J]. 计算机应用, 2021, 41(9): 2623-2630.
[8]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[9]	张永斌, 常文欣, 孙连山, 张航. 基于字典的域名生成算法生成域名的检测方法[J]. 计算机应用, 2021, 41(9): 2609-2614.
[10]	葛纪红, 沈韬. 基于区块链的能源数据访问控制方法[J]. 计算机应用, 2021, 41(9): 2615-2622.
[11]	张师鹏, 李永忠, 杜祥通. 基于半监督学习和三支决策的入侵检测模型[J]. 计算机应用, 2021, 41(9): 2602-2608.
[12]	李莉杨鸿飞董秀则. 基于身份多条件代理重加密的文件分级访问控制方案[J]. 计算机应用, 0, (): 0-0.
[13]	郭媛王学文王充姜津霖. 基于动态网络的非线性置乱扩散同步图像加密[J]. 计算机应用, 0, (): 0-0.
[14]	陈葳葳, 曹利, 顾翔. 基于区块链的车联网电子取证模型[J]. 计算机应用, 2021, 41(7): 1989-1995.
[15]	卿欣艺, 陈玉玲, 周正强, 涂园超, 李涛. 基于中国剩余定理的区块链存储扩展模型[J]. 计算机应用, 2021, 41(7): 1977-1982.

MD5选择前缀碰撞算法的改进及复杂度分析

Improvement on chosen-prefix collisions for MD5 and complexity analysis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics