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

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 (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.