International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Complexity of the Herding Attack and Some Related Attacks on Hash Functions

Authors:
D.R. Stinson
J. Upadhyay
Download:
URL: http://eprint.iacr.org/2010/030
Search ePrint
Search Google
Abstract: In this paper, we analyze the complexity of the construction of the 2^k-diamond structure proposed by Kelsey and Kohno. We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory, which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following: 1. The message complexity for the construction of a diamond structure is \sqrt{k} times more than what was previously stated in literature. 2. The time complexity is n times the message complexity, where n is the size of hash value. Due to above two results, the complexity of the herding attack and the second preimage attack on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on "hash twice'' is n times the claimed complexity, by giving a more detailed analysis of the attack.
BibTeX
@misc{eprint-2010-22931,
  title={On the  Complexity of the Herding Attack and Some Related Attacks on Hash Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / hash functions},
  url={http://eprint.iacr.org/2010/030},
  note={the paper will be submitted to a journal douglas.stinson@yahoo.ca 14629 received 20 Jan 2010},
  author={D.R. Stinson and J. Upadhyay},
  year=2010
}