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

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Inscrypt'14
Keywords
Sliced Biclique cryptanalysishash functionscollision attackgeneralized Feistel networkdouble SP layer
Contact author(s)
mohonag @ iiitd ac in
History
2015-03-13: received
Short URL
https://ia.cr/2015/234
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/234,
      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.