改进的多变量哈希函数

计算机科学 ›› 2013, Vol. 40 ›› Issue (6): 45-48.

改进的多变量哈希函数

邹又姣,马文平,冉占军,陈和风

西安电子科技大学ISN国家重点实验室西安710071;西安电子科技大学ISN国家重点实验室西安710071;西安理工大学理学院数学系西安710048;西安电子科技大学ISN国家重点实验室西安710071

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(61003214,2,60773002),高等学校博士学科点专项科研基金(20100203110003),高等学校创新引智计划项目(B08038)资助

Improved Multivariate Hash Function

ZOU You-jiao,MA Wen-ping,RAN Zhan-jun and CHEN He-feng

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对基于MI算法提出的一种多变量哈希函数进行研究,对该算法的安全性进行分析,找到其破解方法,并在此基础上对该算法进行改进。改进算法在保持了原有算法的所有优点的基础上对这种碰撞攻击免疫。还对该改进算法进行了原像攻击、第二原像攻击、差分攻击和代数攻击方面的安全性分析。同时建立数学模型,并通过实验测试了该改进算法的雪崩效应及其稳定性。实验结果表明,该算法满足严格雪崩效应原则,具有理想的、稳定的雪崩效应。

关键词: MQ问题,多变量,哈希函数,雪崩效应

Abstract: A multivariate hash function based on multivariate public key cryptographic algorithm MI was researched and its security was analyzed so that the method to broke the hash function was found．For this reason,the improved hash function was proposed．The improved hash function can keep all advantages of the original hash function．Further more it is immune on the collision．Its preimage attack,second preimage attack,differential attack and algebraic attack were also analyzed in this paper.The avalanche effect and its stability of the improved hash function were tested on the basis of a mathematical model．The experiment data shows the improved hash function meets the strict avalanche criterion and its avalanche effect is perfect and stable.

Key words: MQ problem,Multivariate polynomials,Hash function,Avalanche effect

邹又姣,马文平,冉占军,陈和风. 改进的多变量哈希函数[J]. 计算机科学, 2013, 40(6): 45-48. https://doi.org/

ZOU You-jiao,MA Wen-ping,RAN Zhan-jun and CHEN He-feng. Improved Multivariate Hash Function[J]. Computer Science, 2013, 40(6): 45-48. https://doi.org/

参考文献

[1] Wang Xiao-yun,Yu Hong-bo．How to break MD5and otherhash functions[C]∥Proceedings of EUROCRYPT 2005,LNCS 3494．Berlin:Springer-Verlag,2005:19-35
[2] Wang Xiao-yun,Yao A C,Yao F．Cryptanalysis of SHA-1Hash Function[R]．Cryptographic Hash Workshop,Invited Report．2005
[3] Wang Xiao-yun,Yu Hong-bo,Wang Wei,et al．Cryptanalysis on HMAC/NMAC-MD5and MD5-MAC[C]∥Proceedings of EUROCRYPT 2009．Berlin:Springer-Verlag,2009:121-133
[4] Federal Register．Government Printing Office[J]． 2007,72(212):62212-62220
[5] Gauravaram P,Knudsen L R,Matusiewicz K,et al．groestl_FinalRnd.zip．http://ehash.iaik.tugraz.at /wiki/groestl
[6] Ferguson N,Lucks S,Schneier B,et al．Skein_FinalRnd.zip．http://ehash.iaik.tugraz.at/wiki/Skein
[7] Aumasson J-P,Henzen L,Meier W,et al．Blake_FinalRnd.zip．http://ehash.iaik.tugraz.at/wiki/BLAKE
[8] Yuan Z,Wang W,Jia K T,et al．New birthday attacks on some MACs based on block ciphers[C]∥Proceedings of CRYPTO 2009．Berlin:Springer-Verlag,2009:209-230
[9] 王尚平,任娇霞,张亚玲,等．改进M-D结构的二次多变量hash函数[J]．哈尔滨工业大学学报,2011,32(4):464-470
[10] Ding J T,Yang B Y．Multivariates polynomials for hashing．Cryptology ePrint Archive．http://eprint.iacr.org/2007/137.pdf,2007
[11] 王后珍,张焕国,杨飏．多变元Hash 函数的构造与分析[J]．电子学报,2011,39(1):237-241
[12] Zou You-jiao,Ma Wen-ping,Ran Zhan-jun,et al．A New Multivariate Hash Function With HAIFA Construction[C]∥10th IEEE Int．Conf．on Trust,Security and Privacy in Computing and Communications, TrustCom 2011,8th IEEE Int．Conf．on Embedded Software and Systems,ICESS 2011,6th Int．Conf．on FCST 2011．2011:884-888
[13] Ding J T.Multivariate Public Key Cryptosystems[M]．Berlin:Springer-Verlag,2006:11-190
[14] 王后珍,张焕国,伍前红,等．多变量Hash函数的构造理论和方法[J]．中国科学:信息科学,2010,40(10):1299-1311
[15] Biham E,Dunkelman O．A framework for iterative hash func-tions-HAIFA[C]∥Proceedings of Second NIST Crypto-graphic Hash Workshop.2006
[16] Kelsey J,Schneier B．Second Preimages on n-Bit Hash Functions for Much Less than 2n[C]∥Cryptology,Proceedings of EUROCRYPT 2005,Lecture Notes in Computer Science 3494．Sprin-ger-Verlag,2005:474-490
[17] Adams W W,Loustaunau P．Introduction to Grbner Bases[D]．Graduate Studies in Mathematics,American Mathematical Socie-ty,Providence,R.I.,1994
[18] Courtois N,Klimov A,Patarin J,et al．Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations[C]∥Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)．Lecture Notes in Computer Science．1807,Belgium:Springer,2000:392-407
[19] Ding J,Buchmann J,Mohamed M S,et al．MutantXL[C]∥Proc．Symbolic Computation and Cryptography．Beijing,2008:16-22
[20] Mohamed M S,Mohamed W S,Ding J,et al．MXL2:Solving po-lynomial equations over GF(2) using an improved mutant stra-tegy[C]∥ J．Buchmann,J．Ding,eds.Post-Quantum Cryptography-PQCrypto 2008(Cincinnati,2008).Lect．Notes Comput．Sci．5299.Berlin:Springer,2008:203-215
[21] Mohamed M S E,Cabarcas D,Ding Jin-tai,et al．MXL3:An efficient algorithm for computing Grbner bases of zero-dimensional ideals[C]∥Proceedings of ICISC 2009．Lect．Notes Comput．Sci．5984.Springer,2010:87-100
[22] Webster A,Tavares F,Stafford E．On the design of S-boxes[C]∥Advances in Cryptology-Crypto’85．Lecture Notes in Computer Science 218．New York,NY:Springer-Verlag,1985:523-534

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed