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.

Metadata
Available format(s)
PDF
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
2020-06-24: received
Short URL
https://ia.cr/2020/770
License
Creative Commons Attribution
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},
      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.