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 $\mathsf{h}$ to get a hash function $\mathsf{H}$. The question we ask is, what property X of $\mathsf{h}$ guarantees collision resistance (CR) of $\mathsf{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 functionsMD transformSHAcollision resistance
Contact author(s)
jlen2734 @ gmail com
History
2018-06-22: received
Short URL
https://ia.cr/2018/625
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.