Cryptology ePrint Archive: Report 2015/234

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

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

Abstract: 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.

Category / Keywords: secret-key cryptography / Sliced Biclique cryptanalysis, hash functions, collision attack, generalized Feistel network, double SP layer

Original Publication (in the same form): Inscrypt'14

Date: received 12 Mar 2015

Contact author: mohonag at iiitd ac in

Available format(s): PDF | BibTeX Citation

Version: 20150313:114109 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]