›› 2013,Vol. 28 ›› Issue (1): 129-143.doi: 10.1007/s11390-013-1317-5

所属专题： Artificial Intelligence and Pattern Recognition

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

ExtendedMD4的碰撞攻击和RIPEMD的伪原根攻击

Gao-Li Wang (王高丽)   

  • 收稿日期:2012-01-11 修回日期:2012-09-12 出版日期:2013-01-05 发布日期:2013-01-05
  • 基金资助:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61103238, the "Chen Guang" project of Shanghai Municipal Education Commission and Shanghai Education Development Foundation of China under Grant No. 09CG29, and the Fundamental Research Funds for the Central Universities of China.

Collision Attack on the Full Extended MD4 and Pseudo-Preimage Attack on RIPEMD

Gao-Li Wang (王高丽)   

  1. School of Computer Science and Technology, Donghua University, Shanghai 201620, China; State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences Beijing 100093, China
  • Received:2012-01-11 Revised:2012-09-12 Online:2013-01-05 Published:2013-01-05
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61103238, the "Chen Guang" project of Shanghai Municipal Education Commission and Shanghai Education Development Foundation of China under Grant No. 09CG29, and the Fundamental Research Funds for the Central Universities of China.

PDF (PC)

1635

密码学里的Hash函数在现代通信、金融、计算机等许多领域有着极为广泛的应用,是许多密码算法与密码协议安全的基本前提条件.其中一个最重要的应用是在数字签名中,它是保证数字签名方案安全而有效的必要条件.Hash函数的三个安全特性,包括抗碰撞攻击(collisionresistance)、抗原根攻击(preimageresistance)和抗第二原根攻击(secondpreimageresistance),是保密通信系统和密码学上需要重点满足的安全属性.分析Hash函数的安全性,能够为设计出安全的Hash函数提供理论基础和技术支持,因而具有重要的现实应用背景.对于双管道结构Hash函数ExtendedMD4和RIPEMD,本文分别给出了碰撞攻击和伪原根攻击.
王小云教授提出“模差分方法”,用该方法对于MD家族中的MD4,RIPEMD,MD5,HAVAL,SHA-0,SHA-1等一系列国际通用Hash函数进行了碰撞攻击.对于MD家族中的双管道结构(double-branch)Hash函数RIPEMD-128,RIPEMD-160,ExtendedMD4等,在用模差分方法对其进行碰撞攻击时,保证两个管道的碰撞差分路线都成立的充分条件经常互相矛盾,从而导致整个差分路线不可能成立.因此到目前为止,还没有公开的对于完整RIPEMD-128,RIPEMD-160,ExtendedMD4算法的碰撞攻击.本文第三节采用模差分方法对ExtendedMD4算法进行了碰撞攻击,找到了ExtendedMD4算法的碰撞实例.在消息修改过程中采取了更精细的态度,对于两个管道的充分条件,在保证它们不产生矛盾的前提下进行消息修改,从而保证碰撞差分路线的正确性.
随着对于MD5等一系列国际通用Hash函数的碰撞攻击,对Hash函数的原根攻击也取得了很大进展.在中间相遇攻击(meet-in-the-middleattack)的基础上,发展出了对于Hash函数原根攻击的新方法.这些方法对于单管道结构Hash函数很有效,但是由于双管道结构Hash函数RIPEMD的中间状态的长度(2n)是Hash值长度(n)的2倍,直接使用中间相遇攻击的思想对RIPEMD进行原根攻击的计算复杂度是2n,这与穷举攻击相比没有优势.本文第四、五节将现有的对于Hash函数原根攻击的方法加以推广,提出了对完整RIPEMD算法的伪原根攻击的方法,该方法比穷举攻击有效.
本文采用的方法对于分析其它双管道结构Hash函数也会起到借鉴的作用,对于完善Hash函数的分析理论具有重要的意义.

Abstract: The cryptographic hash functions Extended MD4 and RIPEMD are double-branch hash functions, which consist of two parallel branches. Extended MD4 was proposed by Rivest in 1990, and RIPEMD was devised in the framework of the RIPE project (RACE Integrity Primitives Evaluation, 1988~1992). On the basis of differential analysis and meet-in-the- middle attack principle, this paper proposes a collision attack on the full Extended MD4 and a pseudo-preimage attack on the full RIPEMD respectively. The collision attack on Extended MD4 holds with a complexity of 237, and a collision instance is presented. The pseudo-preimage attack on RIPEMD holds with a complexity of 2125,4, which optimizes the complexity order for brute-force attack. The results in this study will also be beneficial to the analysis of other double-branch hash functions such as RIPEMD-160.

[1] Rivest R. The MD4 message digest algorithm. In Proc. the10th Int. Cryptology Conference (CRYPTO), Aug. 1990,pp.303-311.
[2] Rivest R. The MD5 message-digest algorithm. 1992, http://www.ietf.org/rfc/rfc1321.txt.
[3] Zheng Y, Pieprzyk J, Seberry J. HAVAL-A one-way hashingalgorithm with variable length of output. In Proc. Workshopon the Theory and Application of Gyptographic Techniques:Advances in Cryptology (AUSCRYPT), Dec. 1992, pp.81-104.
[4] Bosselaers A, Preneel B (eds.). Integrity Primitives for Se-cure Information Systems, Final Report of RACE IntegrityPrimitives Evalution, Springer-Verlag, 1995.
[5] Dobbertin H, Bosselaers A, Preneel B. RIPEMD-160: Astrengthened version of RIPEMD. In Proc. the 3rd Int.Workshop on Fast Software Encryption, Feb. 1996, pp.71-82.
[6] National Institute of Standards and Technology of USA. Se-cure hash standard. Federal Information Processing Stan-dard Publication, FIPS-180, May 1993, http://www.mavi-1.org/web security/cryptography/applied-crypto/fips180.txt.
[7] National Institute of Standards and Technology of USA. Se-cure hash standard. Federal Information Processing Stan-dards Publication, FIPS-180-1, April 17, 1995, http://www.itl. nist.gov/fipspubs/fip/189-1.htm.
[8] National Institute of Standards and Technology of USA. Se-cure hash standard. Federal Information Processing Stan-dards Publication, FIPS-180-2, August, 26, 2002, http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf.
[9] Vaudenay S. On the need for multipermutations: Crypta-nalysis of MD4 and SAFER. In Proc. the 2nd Int. Workshopon Fast Software Encryption, Dec. 1994, pp.286-297.
[10] den Boer B, Bosselaers A. Collisions for the compression func-tion of MD5. In Proc. Workshop on the Theory and Ap-plication of Cryptographic Techniques (EUROCRYPT), May1993, pp.293-304.
[11] Biham E, Chen R. Near-collisions of SHA-0. In Proc. Int.Cryptology Conf. (CRYPTO), Aug. 2004, pp.290-305.
[12] Biham E, Chen R, Joux A, Carribault P, Lemuet C, JalbyW. Collisions of SHA-0 and reduced SHA-1. In Proc. the24th Int. Conf. Theory and Applications of CryptographicTechniques (EUROCRYPT), May 2005, pp.36-57.
[13] Chabaud F, Joux A. Differential collisions in SHA-0. In Proc.the 18th Int. Cryptology Conf. (CRYPTO), Aug. 1998,pp.56-71.
[14] Dobbertin H. The first two rounds of MD4 are not one-way.In Proc. the 5th Int. Workshop on Fast Software Encryption,Mar. 1998, pp.284-292.
[15] Dobbertin H. Cryptanalysis of MD4. In Proc. the 3rd Int.Workshop on Fast Software Encryption, Feb. 1996, pp.53-69.
[16] Dobbertin H. Cryptanalysis of MD5 compress. In Proc. Int.Conf. Theory and Application of Cryptology and InformationSecurity (Rump Session), May 1996, http://www.iacr.org/conferences/ec96/ec96rump.html.
[17] Dobbertin H. RIPEMD with two round compress function isnot collision-free. Journal of Cryptology, 1997, 10(1): 51-70.
[18] Joux A. Collisions for SHA-0. In Proc. of CRYPTO 2004(Rump Session), Aug. 2004, http://www.iacr.org/confere-nces/ crypto2004/rump.html.
[19] Mendel F, Rechberger C, Rijmen V. Update on SHA-1. InProc. CRYPTO 2007 (Rump Session), Aug. 2007, http://rump2007.cr.yp.to.
[20] Rompay B, Biryukov A, Preneel B, Vandewalle J. Crypta-nalysis of 3-pass HAVAL. In Proc. the 9th Int. Conf. The-ory and Application of Cryptology and Information Security(ASIACRYPT), Nov. 30-Dec. 4, 2003, pp.228-245.
[21] Wang X Y, Feng D G, Lai X J, Yu H B. Collisions for hashfunctions MD4, MD5, HAVAL-128 and RIPEMD. In Proc.CRYPTO 2004 Rump Session, Aug. 2004, http://www.iacr.org/conferences/crypto2004/rump.html.
[22] Wang X Y, Lai X J, Feng D G, Chen H, Yu X Y. Crypta-nalysis of the hash functions MD4 and RIPEMD. In Proc. the24th Int. Conf. Theory and Applications of CryptographicTechniques (EUROCRYPT), May 2005, pp.1-18.
[23] Wang G L, Wang M Q. Cryptanalysis of reduced RIPEMD-128. Journal of Software, 2008, 19(9): 2442-2448.
[24] Wang X Y, Yu H B. How to break MD5 and other hashfunctions. In Proc. the 24th Int. Conf. Theory and Appli-cations of Cryptographic Techniques (EUROCRYPT), May2005, pp.19-35.
[25] Wang X Y, Yu H B, Yin L. Efficient collision search attacks onSHA-0. In Proc. the 25th Int. Cryptology Conf. (CRYPTO),Aug. 2005, pp.1-16.
[26] Wang X Y, Yin Y L, Yu H B. Finding collisions on the fullSHA-1. In Proc. the 25th Int. Cryptology Conf. (CRYPTO),Aug. 2005, pp.17-36.
[27] Wang X Y, Feng D G, Yu X Y. An attack on hash functionHAVAL-128. Science in China Ser. F: Information Sciences,2005, 48(5): 545-556.
[28] Yu H B, Wang X Y, Yun A, Park S. Cryptanalysis of the fullHAVAL with 4 and 5 passes. In Proc. the 13th Int. Workshopon Fast Software Encryption, Mar. 2006, pp.89-110.
[29] Yu H B,Wang X Y. Cryptanalysis of the compression functionof SIMD. In Proc. the 16th Australasian Conf. InformationSecurity and Privacy, Jul. 2011, pp.157-171.
[30] Yu H B, Chen J Z, Jia K T, Wang X Y. Near-collision at-tack on the step-reduced compression function of Skein-256.IACR Cryptology ePrint Archive, Report 2011/148, 2011,http://eprint.iacr.org/.
[31] Biham E, Shamir A. Differential cryptanalysis of DES-likecryptosystems. Journal of Cryptology, 1991, 4(1): 3-72.
[32] Yu H B, Wang G L, Zhang G Y, Wang X Y. The second-preimage attack on MD4. In Proc. the 4th Int. Conf. Cryp-tology and Network Security (CRYPTO), Dec. 2005, pp.1-12.
[33] De Canniμere C, Rechberger C. Finding SHA-1 characteris-tics: General results and applications. In Proc. the 12th Int.Conf. Theory and Application of Cryptology and InformationSecurity (ASIACRYPT), Dec. 2006, pp.1-20.
[34] De Canniμere C, Mendel F, Rechberger C. Collisions for 70-Step SHA-1: On the full cost of collision search. In Proc. the14th Int. Workshop. Selected Area in Cryptolography, Aug.2007, pp.56-73.
[35] Knudsen L R, Mathiassen J E. Preimage and collision attackson MD2. In Proc. the 12th Int. Conf. Fast Software Encryp-tion, Feb. 2005, pp.255-267.
[36] Muller F. The MD2 Hash function is not one-way. In Proc.the 10th Int. Conf. Theory and Application of Cryptologyand Information Security (ASIACRYPT), Dec. 2004, pp.214-229.
[37] Aoki K, Sasaki Y. Preimage attacks on one-block MD4, 63-step MD5 and more. In Proc. the 15th Int. Workshop. Se-lected Area in Cryptolography, Aug. 2008, pp.103-119.
[38] De D, Kumarasubramanian A, Venkatesan R. Inversion at-tacks on secure Hash functions using SAT solvers. In Proc.the 10th Int. Conf. Theory and Applications of SatisfiabilityTesting, May 2007, pp.377-382.
[39] Guo J, Ling S, Rechberger C, Wang H. Advanced meet-in-the-middle preimage attacks: First results on full Tiger, andimproved results on MD4 and SHA-2. In Proc. the 16th Int. Conf. Theory and Application of Cryptology and InformationSecurity (ASIACRYPT), Dec. 2010, pp.56-75.
[40] Leurent G. MD4 is not one-way. In Proc. the 15th Int. Conf.Fast Software Encryption, Feb. 2008, pp.412-428.
[41] Zhong J M, Lai X J. Improved preimage attack on one-blockMD4. Journal of Systems and Software, 2012, 85(4): 981-994.
[42] Sasaki Y, Aoki K. Finding preimages in full MD5 faster thanexhaustive search. In Proc. the 28th Int. Conf. Theory andApplications of Gryptolographic Techniques (EUROCRYPT),Apr. 2009, pp.134-152.
[43] Sasaki Y, Aoki K. Preimage attacks on 3, 4, and 5-passHAVAL. In Proc. the 14th Int. Conf. Theory and Applica-tion of Cryptology and Information Security (ASIACRYPT),Dec. 2008, pp.253-271.
[44] Sasaki Y, Aoki K. Meet-in-the-middle preimage attacks ondouble-branch hash functions: Application to RIPEMD andothers. In Proc. the 14th Australasian Conf. InformationSecurity and Privacy, Jul. 2009, pp.214-231.
[45] Wang G L, Wang S H. Preimage attack on Hash functionRIPEMD. In Proc. the 5th Int. Conf. Information SecurityPractice and Experience, Apr. 2009, pp.274-284.
[46] Ohtahara C, Sasaki Y, Shimoyama T. Preimage attackson step-reduced RIPEMD-128 and RIPEMD-160. In Proc.the 6th Int. Conf. Information Security and Cryptology(INSCRYPT), Oct. 2010, pp.169-186.
[47] Aoki K, Sasaki Y. Meet-in-the-middle preimage attacksagainst reduced SHA-0 and SHA-1. In Proc. the 29th Int.Cryptology Conf. (CRYPTO), Aug. 2009, pp.70-89.
[48] Aoki K, Guo J, Matusiewicz K, Sasaki Y, Wang L. Preimagesfor step reduced SHA-2. In Proc. the 15th Int. Conf. The-ory and Application of Cryptology and Information Security(ASIACRYPT), Dec. 2009, pp.578-597.
[49] Mendel F, Pramstaller N, Rechberger C. A (Second) preimageattack on the GOST Hash function. In Proc. the 15th Int.Conf. Fast Software Encryption, Feb. 2008, pp.224-234.
[50] Khovratovich D, Rechberger C, Savelieva A. Bicliques forpreimages: Attacks on Skein-512 and the SHA-2 family. InProc. the 19th Int. Conf. Fast Software Encryption, Mar.2012, pp.244-263.
[51] Sasaki Y. Meet-in-the-middle preimage attacks on AES hash-ing modes and an application to Whirlpool. In Proc. the18thInt. Conf. Fast Software Encryption, Feb. 2011, pp.378-396.
[52] Wu S, Feng D G, Wu W L, Guo J, Dong L, Zou J. (Pseudo)preimage attack on reduced-round Grstl hash function andothers. In Proc. the 19th Int. Conf. Fast Software Encryp-tion, Mar. 2012, pp.127-145.
[53] Aoki K, Sasaki Y. Preimage attacks on one-block MD4, 63-step MD5 and more. In Proc. the 15th Int. Workshop. Se-lected Area in Cryptology, Aug. 2008, pp.103-119.
[54] Diffie W, Hellman M E. Exhaustive cryptanalysis of the NBSdata encryption standard. Computer, 1977, 10(6): 74-84.
[55] Li J, Isobe T, Shibutani K. Converting meet-in-the-middlepreimage attack into pseudo collision attack: Application toSHA-2. In Proc. the 19th Int. Conf. Fast Software Encryp-tion, Mar. 2012, pp.264-286.
[56] Wang L, Sasaki Y, Komatsubara W, Ohta K,Sakiyama K. (Second) preimage attacks on step-reducedRIPEMD/RIPEMD-128 with a new local-collision approach.In Proc. the 11th Int. Conf. Topics in Cryptology, Feb.2011, pp.197-212.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] 金兰; 杨元元;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[5] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[8] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[9] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[10] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：