Paper 2026/2695

Short Collisions Separate Sponge from Merkle-Damgård

Abstract

We study short collisions in salted Merkle-Damg{\aa}rd (MD) and Sponge under the query-bounded preprocessing model introduced by Ghoshal and Tessaro (CRYPTO '23). The adversary makes at most $T_1$ oracle queries before a random salt is revealed and at most $T_2$ queries afterwards, and must output two colliding messages of at most $B$ blocks. Our main result is a separation between the two constructions. Let $N=2^n$, give MD and Sponge matching $n$-bit salts, message blocks, and outputs, and set $T_1=\Theta(N/T_2)$ with $T_2=o(\sqrt N)$. For Sponge, there is an attack that finds a collision with constant probability using only three-block messages. In contrast, every MD adversary restricted to $B=o(T_2)$ blocks succeeds with probability at most \[ O\left(\frac{B}{T_2}+\frac{T_2^2}{N}\right)=o(1). \] Thus, under the same query budgets, three blocks suffice for Sponge, while every MD adversary with $B=o(T_2)$ blocks has success probability $o(1)$. On the MD side, we prove an upper bound for arbitrary block bounds $B$. The proof uses a simple graph argument that distinguishes collisions already present in the preprocessing transcript from those that can actually be reached by a short computation starting from the subsequently sampled salt. This extends query-bounded preprocessing analysis beyond the previously understood one- and two-block cases. On the Sponge side, we give a three-block attack that uses inverse permutation queries to make one precomputed collision useful from many different capacities. We complement the attack with a matching upper bound in a range containing the separation. In this range, allowing longer messages gives no asymptotic improvement: the optimal Sponge preprocessing advantage is already attained with at most three blocks. Overall, our results show that collision length interacts fundamentally differently with preprocessing in the two constructions: under matched parameters and identical query budgets, Sponge admits constant probability three-block collisions, whereas MD does not achieve constant success for any $B=o(T_2)$.