Paper 2020/770

Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions

Akshima, David Cash, Andrew Drucker, and Hoeteck Wee

Abstract

We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary $$-bit auxiliary advice input about the random oracle and $$ queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage $$, where $$ is the output length, beating the birthday bound by a factor of $$. These attacks were shown to be optimal. We observe that the collisions produced are very long, on the order $$ blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding $$-block-long collisions achieving advantage $$. We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the $$ bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length $$, length $$, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) order of $$, $$ and $$ 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.