Paper 2022/309

On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing

Ashrujit Ghoshal, University of Washington
Ilan Komargodski, Hebrew University of Jerusalem, NTT Research
Abstract

We study the power of preprocessing adversaries in finding bounded-length collisions in the widely used Merkle-Damgård (MD) hashing in the random oracle model. Specifically, we consider adversaries with arbitrary $S$-bit advice about the random oracle and can make at most $T$ queries to it. Our goal is to characterize the advantage of such adversaries in finding a $B$-block collision in an MD hash function constructed using the random oracle with range size $N$ as the compression function (given a random salt). The answer to this question is completely understood for very large values of $B$ (essentially $\Omega(T)$) as well as for $B=1,2$. For $B\approx T$, Coretti et al.~(EUROCRYPT '18) gave matching upper and lower bounds of $\tilde\Theta(ST^2/N)$. Akshima et al.~(CRYPTO '20) observed that the attack of Coretti et al.\ could be adapted to work for any value of $B>1$, giving an attack with advantage $\tilde\Omega(STB/N + T^2/N)$. Unfortunately, they could only prove that this attack is optimal for $B=2$. Their proof involves a compression argument with exhaustive case analysis and, as they claim, a naive attempt to generalize their bound to larger values of B (even for $B=3$) would lead to an explosion in the number of cases needed to be analyzed, making it unmanageable. With the lack of a more general upper bound, they formulated the STB conjecture, stating that the best-possible advantage is $\tilde O(STB/N + T^2/N)$ for any $B>1$. In this work, we confirm the STB conjecture in many new parameter settings. For instance, in one result, we show that the conjecture holds for all constant values of $B$, significantly extending the result of Akshima et al. Further, using combinatorial properties of graphs, we are able to confirm the conjecture even for super constant values of $B$, as long as some restriction is made on $S$. For instance, we confirm the conjecture for all $B \le T^{1/4}$ as long as $S \le T^{1/8}$. Technically, we develop structural characterizations for bounded-length collisions in MD hashing that allow us to give a compression argument in which the number of cases needed to be handled does not explode.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
Time-space tradeoffs AI-ROM Merkle-Damgård short collisions
Contact author(s)
ashrujit @ cs washington edu
ilank @ cs huji ac il
History
2022-06-20: revised
2022-03-07: received
See all versions
Short URL
https://ia.cr/2022/309
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/309,
      author = {Ashrujit Ghoshal and Ilan Komargodski},
      title = {On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/309},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/309}},
      url = {https://eprint.iacr.org/2022/309}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.