International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of CRUSH hash structure

Authors:
Nasour Bagheri
Majid Naderi
Babak Sadeghiyan
Download:
URL: http://eprint.iacr.org/2008/043
Search ePrint
Search Google
Abstract: 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.
BibTeX
@misc{eprint-2008-17720,
  title={Cryptanalysis of CRUSH hash structure},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / CRUSH hash structure, Hash function, Collision, Pre-image, Second pre-image, Multi-collision attack},
  url={http://eprint.iacr.org/2008/043},
  note={ n_bagheri@iust.ac.ir 13901 received 23 Jan 2008},
  author={Nasour Bagheri and Majid Naderi and Babak Sadeghiyan},
  year=2008
}