Increasing the Flexibility of the Herding Attack

Chosen-target-forced-prefix (CTFP) preimage resistance is a hash function security property guaranteeing the inability of an attacker to commit to a hash function outcome h without knowing the prefix of the message to be hashed in advance. At EUROCRYPT 2006, Kelsey and Kohno described the herding attack against the Merkle-Damgård design that results in a CTFP-preimage of length about n/3 blocks in approximately n·2 2n/3 compression function calls. Using an additional parameter l, the attack can be sped-up at the cost of exponentially large preimages (the elongated herding attack). In this work, we re-investigate speed vs. message length tradeoffs for the herding attack. Using a third parameter d, we introduce the generalized elongated multidimensional herding attack. The parameters l and d allow for full control over the efficiency of the attack versus the length of the preimages: increasing l results in faster attacks with longer messages, while increasing d results in shorter messages with higher attack complexity. Using advanced methods in graph theory we analyze the complexity of the generalized attack, and we describe several variants for different values of l, d. On the extreme, a CTFP-preimage of 2 n/2 blocks can be found in n·2 n/2 queries. One can find a CTFP-preimage of length about n/8 blocks in n3·2 3n/4 work. © 2011 Elsevier B.V. All rights reserved.status: publishe