Welcome to the resource topic for 2020/770
Title:
Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
Authors: Akshima, David Cash, Andrew Drucker, 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.
ePrint: https://eprint.iacr.org/2020/770
Talk: https://www.youtube.com/watch?v=XCU-L2A6dww
Slides: https://iacr.org/submit/files/slides/2020/crypto/crypto2020/319/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .