International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Time-Space Lower Bounds for Finding Collisions in Merkle–Damgård Hash Functions

Authors:
Akshima
Siyao Guo
Qipeng Liu
Download:
DOI: 10.1007/s00145-024-09491-9
Search ePrint
Search Google
Abstract: We revisit the problem of finding B -block-long collisions in Merkle–Damgård Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of S -bit advice about the random oracle and makes T oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for 2≤B≤T 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage Ω~(STB/2n+T2/2n) Ω ~ ( S T B / 2 n + T 2 / 2 n ) where n is the output length of the random oracle. They conjectured that this attack is optimal. However, this so-called STB conjecture was only proved for B≈T B ≈ T and B=2 B = 2 . Very recently, Ghoshal and Komargodski (CRYPTO 2022) confirmed the STB conjecture for all constant values of B and provided an O~(S4TB2/2n+T2/2n) O ~ ( S 4 T B 2 / 2 n + T 2 / 2 n ) bound for all choices of B . In this work, we prove an O~((STB/2n)⋅max{1,ST2/2n}+T2/2n) O ~ ( ( S T B / 2 n ) · max { 1 , S T 2 / 2 n } + T 2 / 2 n ) bound for every 2<B<T 2 < B < T . Our bound confirms the STB conjecture for ST2≤2n S T 2 ≤ 2 n and is optimal up to a factor of S for ST2>2n S T 2 > 2 n (note as T2 T 2 is always at most 2n 2 n , otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for B=O~(1) B = O ~ ( 1 ) and ST2>2n S T 2 > 2 n . We obtain our results by adopting and refining the technique of Chung, Guo, Liu and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques. Along the way, we obtain a considerably simpler and illuminating proof for B=2 B = 2 , recovering the main result of Akshima, Cash, Drucker and Wee.
BibTeX
@article{jofc-2024-33971,
  title={Time-Space Lower Bounds for Finding Collisions in Merkle–Damgård Hash Functions},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={37},
  doi={10.1007/s00145-024-09491-9},
  author={ Akshima and Siyao Guo and Qipeng Liu},
  year=2024
}