Paper 2010/030

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

Simon R. Blackburn, Douglas R. Stinson, and Jalaj Upadhyay


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 (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the {\it message complexity} (i.e., the number of hash computations required to build the required structure). We also analyze the {\it 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: \begin{enumerate} \item The message complexity for the construction of a diamond structure is $\sqrt{k}$ times more than the amount previously stated in literature. \item The time complexity is $n$ times the message complexity, where $n$ is the size of hash value. \end{enumerate} Due to the above two results, the herding attack~\cite{KK06} and the second preimage attack~\cite{ABFHKSZ08} 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 complexity claimed by~\cite{ABDK09}, by giving a more detailed analysis of the attack.

Available format(s)
Publication info
Published elsewhere. the paper will be submitted to a journal
hash functions
Contact author(s)
douglas stinson @ yahoo ca
2010-09-01: last of 2 revisions
2010-01-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Simon R.  Blackburn and Douglas R.  Stinson and Jalaj Upadhyay},
      title = {On the  Complexity of the Herding Attack and Some Related Attacks on Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2010/030},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.