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-30 出版日期:2014-09-01
通讯作者: 程宽
作者简介:
程宽(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-30 Published:2014-09-01
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]	佘维马天祥冯海格田钊刘炜. 基于合约调用掩盖下的区块链隐蔽通信方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[3]	项勇, 李艳俊, 黄丁韫, 陈愚, 谢惠琴. 全轮Shadow算法的差分和线性特征分析[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3839-3843.
[4]	赵振皓, 张仕斌, 万武南, 张金全, 秦智. 基于信誉值和强盲签名算法的委托权益证明共识算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3717-3722.
[5]	王伊婷, 万武南, 张仕斌, 张金全, 秦智. 基于SM9算法的可链接环签名方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3709-3716.
[6]	梁静, 万武南, 张仕斌, 张金全, 秦智. 面向主从链的慈善系统溯源存储模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3751-3758.
[7]	刘德渊, 张金全, 张鑫, 万武南, 张仕斌, 秦智. 基于无证书签密的跨链身份认证方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3731-3740.
[8]	张鑫, 张金全, 刘德渊, 万武南, 张仕斌, 秦智. 基于身份代理重加密的跨链身份管理方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3723-3730.
[9]	邓伊琳余发江. 基于LSTM和可分离自注意力机制的伪随机数生成器[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	张润莲王蒿唐瑞锋武小年. 基于均匀流型逼近与投影的高级加密标准算法相关功耗分析方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	刘运东汪学明. 基于穿刺伪随机函数的动态可搜索加密方案[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	张宏扬张淑芬谷铮. 面向个性化与公平性的联邦学习算法fedPF[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	姚梓豪马自强李扬魏良根. 基于冲突的缓存侧信道攻击与驱逐集研究综述[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[14]	晏燕李飞飞吕雅琴冯涛. 安全高效的混洗差分隐私频率估计方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	彭海洋计卫星刘法旺. 基于区块链的自动驾驶仿真测试数据存证模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

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

Improvement on chosen-prefix collisions for MD5 and complexity analysis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics