How do herding attacks on hash functions work?

Herding attack is introduced by Kelsey and Kohno in 2005. The attack is applicable to hash commitments. Nostradamus's example from the article is key of the idea. First Nostradamus produces the MD5 (MD is enough) hash of the future prediction of S&P500 before the business year finishes. After Nostradamus publish his message with precise closing prices of the S&P500's companies with some garbage text after it. The message has the same hash the committed hash.

At first, to achieve this, Nostradamus need pre-image attack on MD5, which has still $2^{123.4}$ complexity achieved after this work in 2009 (Finding Preimages in Full MD5 Faster Than Exhaustive Search). Instead of pre-image attack, this work introduces a new required property; Chosen Target Forced Prefix Pre-image resistance.

• In the first step, Nostradamus has a Chosen Target by committing n-bit Hash value, $H$.
• In the challenge step, the challenger provides $P$ to Nostradamus as Forced-Prefix so that the hash $H = Hash(Pmathbin|S) $ where $S$ is the suffix (garbage).

The Herding

The herding attack uses a diamond structure to find the hash. The below figure uses 8 different starting messages, one can consider this all possible outcome of the prediction of the Nostradamus prediction.

Remember that, this attack utilizes the Merkle-Damgard structure of the hash function. MOD constructions divide the hash into the block ( for example 512-bit blocks for MD5) after the appropriate padding. Each block then used in the compression function in order.

In the above figure, the first 512-bit part of each message is hashed. Then the crucial part begins. This is actually internal collision on MD construction. Randomly generating 512-bit block to see that $C(h[0,0], m_i) = C(h[0,0], m_j)$ where the $C$ is the internal compression function. With the generic collision, this has $8 cdot2^{n/2}$ complexity. And as mentioned in the article A diamond structure is essentially a Merkle tree built by brute force.

The committer actually can do better than this instead of a fixed structure for collision finding, one can go dynamically. In the generalized form mapping $2^k$ hash nodes in the diamond structure to $2^{k-1}$ they generate $2^{n/2+1/2-k/2}$ candidate block parts and looks for the collisions altogether. This has $2^{n/2+k/2+2}$

This attack can also be applied to longer messages - elongated Diamond structure.

The complexity of the attack on MD5 with 41 diamond width and 48 suffix length requires $2^{87}$ complexity. On impractically long suffixes the attack on MD5 with 5 diamond width and $2^{55}$ suffix length requires $2^{69}$ complexity.

• Andreeva at al. go beyond this work on Herding, Second Preimage and Trojan Message Attacks beyond Merkle-Damgard, 2009.