eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2015/234

Collision Attack on 4-branch, Type-2 GFN based Hash Functions using Sliced Biclique Cryptanalysis Technique

Megha Agrawal, Donghoon Chang, Mohona Ghosh, and Somitra Kumar Sanadhya


In this work, we apply the sliced biclique cryptanalysis technique to show 8-round collision attack on a hash function H based on 4-branch, Type-2 Generalized Feistel Network (Type-2 GFN). This attack is generic and works on 4-branch, Type-2 GFN with any parameters including the block size, type of round function, the number of S-boxes in each round and the number of SP layers inside the round function. We first construct a 8-round distinguisher on 4-branch, Type-2 GFN and then use this distinguisher to launch 8-round collision attack on compression functions based on Matyas-Meyer-Oseas (MMO) and Miyaguchi-Preneel (MP) modes. The complexity of the attack on 128-bit compression function is 2^56. The attack can be directly translated to collision attack on MP and MMO based hash functions and pseudo-collision attack on Davies-Meyer (DM) based hash functions. When the round function F is instantiated with double SP layer, we show the first 8-round collision attack on 4-branch, Type-2 GFN with double SP layer based compression function. The previous best attack on this structure was a 6-round near collision attack shown by Sasaki at Indocrypt'12. His attack cannot be used to generate full collisions on 6-rounds and hence our result can be regarded the best so far in literature on this structure.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Inscrypt'14
Sliced Biclique cryptanalysishash functionscollision attackgeneralized Feistel networkdouble SP layer
Contact author(s)
mohonag @ iiitd ac in
2015-03-13: received
Short URL
Creative Commons Attribution


      author = {Megha Agrawal and Donghoon Chang and Mohona Ghosh and Somitra Kumar Sanadhya},
      title = {Collision Attack on 4-branch, Type-2 GFN based Hash Functions using Sliced Biclique Cryptanalysis Technique},
      howpublished = {Cryptology ePrint Archive, Paper 2015/234},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/234}},
      url = {https://eprint.iacr.org/2015/234}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.