On the complexity of the herding attack and some related attacks on hash functions

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

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


In this article, we analyze the complexity of the construction of the 2 k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183-200, 2006). 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 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 √k times more than the amount previously stated in literature. 2. The time complexity is n times the message complexity, where n is the size of hash value. Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183-200, 2006) and the second preimage attack (Andreeva et al., LNCS, Vol 4965, pp 270-288, 2008) 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 Andreeva et al. (LNCS, Vol 5867, pp 393-414, 2009), by giving a more detailed analysis of the attack.

Original languageEnglish (US)
Pages (from-to)171-193
Number of pages23
JournalDesigns, Codes, and Cryptography
Issue number1-2
StatePublished - Jul 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • Diamond structure
  • Hash function
  • Herding attack


Dive into the research topics of 'On the complexity of the herding attack and some related attacks on hash functions'. Together they form a unique fingerprint.

Cite this