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

Special Issue: Artificial Intelligence and Pattern Recognition

• Information Security • Previous Articles     Next Articles

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

1635

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] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[5] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[8] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[9] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved