Search for: All records

We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary S-bit auxiliary advice input about the random oracle and T queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage 𝛺(𝑆𝑇2/2𝑛) , where n is the output length, beating the birthday bound by a factor of S. These attacks were shown to be optimal. We observe that the collisions produced are very long, on the order of T blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find shorter collisions. We first exhibit a simple attack for finding B-block-long collisions achieving advantage 𝛺̃ (𝑆𝑇𝐵/2𝑛) . We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the 𝑆𝑇2/2𝑛 bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length 1, length 2, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) on the order of (𝑆+𝑇)/2𝑛 , 𝑆𝑇/2𝑛 and 𝑆𝑇2/2𝑛 advantage. We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.