### 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 $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 $\Omega(ST^2/2^n)$, 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 $T$ 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 $B$-block-long collisions achieving advantage $\tilde{\Omega}(STB/2^n)$. We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the $ST^2/2^n$ 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) order of $(S+T)/2^n$, $ST/2^n$ and $ST^2/2^n$ 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2020
Keywords
provable securitysymmetric cryptographytime-memory tradeoffsauxiliary inputhash functionsMerkle Damgårdrandom oracleshort collisions
Contact author(s)
akshima @ uchicago edu
davidcash @ uchicago edu
andy drucker @ gmail com
wee @ di ens fr
History
Short URL
https://ia.cr/2020/770

CC BY

BibTeX

@misc{cryptoeprint:2020/770,
author = {Akshima and David Cash and Andrew Drucker and Hoeteck Wee},
title = {Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions},
howpublished = {Cryptology ePrint Archive, Paper 2020/770},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/770}},
url = {https://eprint.iacr.org/2020/770}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.