Paper 2008/043

Cryptanalysis of CRUSH hash structure

Nasour Bagheri, Majid Naderi, and Babak Sadeghiyan


In this paper, we will present a cryptanalysis of CRUSH hash structure. Surprisingly, our attack could find pre-image for any desired length of internal message. Time complexity of this attack is completely negligible. We will show that the time complexity of finding a pre-image of any length is O(1). In this attack, an adversary could freely find a pre-image with the length of his own choice for any given message digits. We can also find second pre-image, collision, multi-collision in the same complexity with our attack. In this paper, we also introduce a stronger variant of the algorithm, and show that an adversary could still be able to produce collisions for this stronger variant of CRUSH hash structure with a time complexity less than a Birthday attack.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
CRUSH hash structureHash functionCollisionPre-imageSecond pre-imageMulti-collision attack
Contact author(s)
n_bagheri @ iust ac ir
2008-01-29: received
Short URL
Creative Commons Attribution


      author = {Nasour Bagheri and Majid Naderi and Babak Sadeghiyan},
      title = {Cryptanalysis of CRUSH hash structure},
      howpublished = {Cryptology ePrint Archive, Paper 2008/043},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.