Better Than Advertised: Improved Collision-Resistance Guarantees for MD-Based Hash Functions

Mihir Bellare; Joseph Jaeger; Julia Len

Paper 2018/625

Better Than Advertised: Improved Collision-Resistance Guarantees for MD-Based Hash Functions

Mihir Bellare, Joseph Jaeger, and Julia Len

Abstract

The MD transform that underlies the MD and SHA families iterates a compression function $h$ to get a hash function $H$ . The question we ask is, what property X of $h$ guarantees collision resistance (CR) of $H$ ? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Major revision. ACM CCS 2017
DOI: 10.1145/3133956.3134087
Keywords: hash functions MD transform SHA collision resistance
Contact author(s): jlen2734 @ gmail com
History: 2018-06-22: received
Short URL: https://ia.cr/2018/625
License: CC BY

BibTeX

@misc{cryptoeprint:2018/625,
      author = {Mihir Bellare and Joseph Jaeger and Julia Len},
      title = {Better Than Advertised: Improved Collision-Resistance Guarantees for {MD}-Based Hash Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/625},
      year = {2018},
      doi = {10.1145/3133956.3134087},
      url = {https://eprint.iacr.org/2018/625}
}