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
-
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},
note = {\url{https://eprint.iacr.org/2018/625}},
url = {https://eprint.iacr.org/2018/625}
}
