More Web Proxy on the site http://driver.im/

research-article

Public Access

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

Authors:

Julia LenAuthors Info & Claims

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Pages 891 - 906

https://doi.org/10.1145/3133956.3134087

Published: 30 October 2017 Publication History

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.

Supplemental Material

MP4 File

Download
2641.74 MB

References

[1]

Elena Andreeva, Bart Mennink, and Bart Preneel. 2011. Security Reductions of the Second Round SHA-3 Candidates ISC 2010 (LNCS), Mike Burmester, Gene Tsudik, Spyros S. Magliveras, and Ivana Ilic (Eds.), Vol. Vol. 6531. Springer, Heidelberg, 39--53.

[2]

Elena Andreeva, Gregory Neven, Bart Preneel, and Thomas Shrimpton 2007. Seven-Property-Preserving Iterated Hashing: ROX. ASIACRYPT 2007 (LNCS), Kaoru Kurosawa (Ed.), Vol. Vol. 4833. Springer, Heidelberg, 130--146.

[3]

Elena Andreeva and Martijn Stam 2011. The Symbiosis between Collision and Preimage Resistance 13th IMA International Conference on Cryptography and Coding (LNCS), Liqun Chen (Ed.), Vol. Vol. 7089. Springer, Heidelberg, 152--171.

[4]

Benedikt Auerbach, David Cash, Manuel Fersch, and Eike Kiltz. 2017. Memory-Tight Reductions. In CRYPTO 2017, Part I (LNCS), Jonathan Katz and Hovav Shacham (Eds.), Vol. Vol. 10401. Springer, Heidelberg, 101--132. https://doi.org/10.1007/978-3-319-63688-7_4

[5]

Michael Backes, Gilles Barthe, Matthias Berg, Benjamin Grégoire, César Kunz, Malte Skoruppa, and Santiago Zanella Béguelin. 2012. Verified security of merkle-damgård. In Computer Security Foundations Symposium (CSF), 2012 IEEE 25th. IEEE, 354--368.

[6]

Mihir Bellare. 2006. New Proofs for NMAC and HMAC: Security without Collision-Resistance CRYPTO 2006 (LNCS), Cynthia Dwork (Ed.), Vol. Vol. 4117. Springer, Heidelberg, 602--619.

[7]

Mihir Bellare, Daniel J. Bernstein, and Stefano Tessaro. 2016. Hash-Function Based PRFs: AMAC and Its Multi-User Security EUROCRYPT 2016, Part I (LNCS), Marc Fischlin and Jean-Sébastien Coron (Eds.), Vol. Vol. 9665. Springer, Heidelberg, 566--595. https://doi.org/10.1007/978--3--662--49890--3_22

[8]

Mihir Bellare, Ran Canetti, and Hugo Krawczyk. 1996. Keying Hash Functions for Message Authentication. CRYPTO'96 (LNCS), Neal Koblitz (Ed.), Vol. Vol. 1109. Springer, Heidelberg, 1--15.

[9]

Mihir Bellare, Ran Canetti, and Hugo Krawczyk. 1996. Pseudorandom functions revisited: The cascade construction and its concrete security 37th FOCS. IEEE Computer Society Press, 514--523.

[10]

Mihir Bellare and Thomas Ristenpart 2006. Multi-Property-Preserving Hash Domain Extension and the EMD Transform ASIACRYPT 2006 (LNCS), Xuejia Lai and Kefei Chen (Eds.), Vol. Vol. 4284. Springer, Heidelberg, 299--314.

[11]

Mihir Bellare and Phillip Rogaway 2006. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs EUROCRYPT 2006 (LNCS), Serge Vaudenay (Ed.), Vol. Vol. 4004. Springer, Heidelberg, 409--426.

[12]

John Black, Phillip Rogaway, and Thomas Shrimpton. 2002. Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV CRYPTO 2002 (LNCS), Moti Yung (Ed.), Vol. Vol. 2442. Springer, Heidelberg, 320--335.

[13]

Daniel R. L. Brown. 2002. Generic Groups, Collision Resistance, and ECDSA. Contributions to IEEE P1363a. (Feb. 2002). shownoteUpdated version for "The Exact Security of ECDSA." Available from http://grouper.ieee.org/groups/1363/.

[14]

Ivan Damgård. 1988. Collision Free Hash Functions and Public Key Signature Schemes EUROCRYPT'87 (LNCS), David Chaum and Wyn L. Price (Eds.), Vol. Vol. 304. Springer, Heidelberg, 203--216.

[15]

Ivan Damgård. 1990. A Design Principle for Hash Functions. In CRYPTO'89 (LNCS), Gilles Brassard (Ed.), Vol. Vol. 435. Springer, Heidelberg, 416--427.

[16]

Hans Dobbertin. 1996. Cryptanalysis of MD5 Compress. (1996).

[17]

Yevgeniy Dodis and Prashant Puniya 2008. Getting the Best Out of Existing Hash Functions; or What if We Are Stuck with SHA? In ACNS 08 (LNCS), Steven M. Bellovin, Rosario Gennaro, Angelos D. Keromytis, and Moti Yung (Eds.), Vol. Vol. 5037. Springer, Heidelberg, 156--173.

[18]

Yevgeniy Dodis, Thomas Ristenpart, and Thomas Shrimpton. 2009. Salvaging Merkle-Damgård for Practical Applications EUROCRYPT 2009 (LNCS), Antoine Joux (Ed.), Vol. Vol. 5479. Springer, Heidelberg, 371--388.

[19]

Peter Gavzi, Krzysztof Pietrzak, and Michal Rybár 2014. The Exact PRF-Security of NMAC and HMAC. In CRYPTO 2014, Part I (LNCS), Juan A. Garay and Rosario Gennaro (Eds.), Vol. Vol. 8616. Springer, Heidelberg, 113--130. https://doi.org/10.1007/978-3-662-44371-2_7

[20]

Jonathan Katz and Yehuda Lindell 2014. Introduction to modern cryptography. CRC press.

Digital Library

[21]

G. Laccetti and G. Schmid 2004. On a Probabilistic Approach to the Security Analysis of Cryptographic Hash Functions. Cryptology ePrint Archive, Report 2004/324. (2004). http://eprint.iacr.org/2004/324.

[22]

Alfred J Menezes, Paul C. Van Oorschot, and Scott A Vanstone. 1996. Handbook of applied cryptography. CRC press.

[23]

Ralph C. Merkle. 1990. A Fast Software One-Way Hash Function. Journal of Cryptology, Vol. 3, 1 (1990), 43--58.

Digital Library

[24]

Ralph C. Merkle. 1990. One Way Hash Functions and DES. In CRYPTO'89 (LNCS), Gilles Brassard (Ed.), Vol. Vol. 435. Springer, Heidelberg, 428--446.

[25]

NIST August 2015. FIPS 180--4, Secure Hash Standard. (August 2015).

[26]

Ronald Rivest. 2004. The MD5 message-digest algorithm, 1992. RFC1321, Internet Engineering Task Force (2004).

Digital Library

[27]

Ronald L. Rivest. 1991. The MD4 Message Digest Algorithm. In CRYPTO'90 (LNCS), Alfred J. Menezes and Scott A. Vanstone (Eds.), Vol. Vol. 537. Springer, Heidelberg, 303--311.

[28]

Phillip Rogaway and Thomas Shrimpton 2004. Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance FSE 2004 (LNCS), Bimal K. Roy and Willi Meier (Eds.), Vol. Vol. 3017. Springer, Heidelberg, 371--388.

[29]

Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. 2017. The First Collision for Full SHA-1. In CRYPTO 2017, Part I (LNCS), Jonathan Katz and Hovav Shacham (Eds.), Vol. Vol. 10401. Springer, Heidelberg, 570--596. https://doi.org/10.1007/978-3-319-63688-7_19

[30]

Marc Stevens, Pierre Karpman, and Thomas Peyrin. 2016. Freestart Collision for Full SHA-1. In EUROCRYPT 2016, Part I (LNCS), Marc Fischlin and Jean-Sébastien Coron (Eds.), Vol. Vol. 9665. Springer, Heidelberg, 459--483. https://doi.org/10.1007/978-3-662-49890-3_18

[31]

Douglas R Stinson. 2005. Cryptography: theory and practice. CRC press.

[32]

Douglas R Stinson. 2006. Some observations on the theory of cryptographic hash functions. Designs, Codes and Cryptography Vol. 38, 2 (2006), 259--277.

Digital Library

[33]

Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu. 2004. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. Cryptology ePrint Archive, Report 2004/199. (2004). http://eprint.iacr.org/2004/199.

[34]

Xiaoyun Wang and Hongbo Yu 2005. How to Break MD5 and Other Hash Functions. In EUROCRYPT 2005 (LNCS), Ronald Cramer (Ed.), Vol. Vol. 3494. Springer, Heidelberg, 19--35.

Digital Library

Cited By

Garay JKiayias APanagiotakos G(2020)Blockchains from Non-idealized Hash FunctionsTheory of Cryptography10.1007/978-3-030-64375-1_11(291-321)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64375-1_11
Garay JKiayias APanagiotakos G(2020)Consensus from Signatures of WorkTopics in Cryptology – CT-RSA 202010.1007/978-3-030-40186-3_14(319-344)Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-40186-3_14
Al-Odat ZKhan S(2019)The Sponge Structure Modulation Application to Overcome the Security Breaches for the MD5 and SHA-1 Hash Functions2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC)10.1109/COMPSAC.2019.00119(811-816)Online publication date: Jul-2019
https://doi.org/10.1109/COMPSAC.2019.00119
Show More Cited By

Index Terms

Better Than Advertised: Improved Collision-Resistance Guarantees for MD-Based Hash Functions
1. Security and privacy
  1. Cryptography
    1. Symmetric cryptography and hash functions

Recommendations

A Characterization of Chameleon Hash Functions and New, Efficient Designs

This paper shows that chameleon hash functions and Sigma protocols are equivalent. We provide a transform of any suitable Sigma protocol to a chameleon hash function, and also show that any chameleon hash function is the result of applying our transform ...
The Rebound Attack and Subspace Distinguishers: Application to Whirlpool

We introduce the rebound attack as a variant of differential cryptanalysis on hash functions and apply it to the hash function Whirlpool, standardized by ISO/IEC. We give attacks on reduced variants of the 10-round Whirlpool hash function and ...
Analysis of SHA-512/224 and SHA-512/256
Proceedings, Part II, of the 21st International Conference on Advances in Cryptology --- ASIACRYPT 2015 - Volume 9453

In 2012, NIST standardized SHA-512/224 and SHA-512/256, two truncated variants of SHA-512, in FIPS 180-4. These two hash functions are faster than SHA-224 and SHA-256 on 64-bit platforms, while maintaining the same hash size and claimed security level. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

October 2017

2682 pages

ISBN:9781450349468

DOI:10.1145/3133956

General Chair:
Bhavani Thuraisingham
The University of Texas at Dallas, USA
,
Program Chairs:
David Evans
University of Virginia
,
Tal Malkin
Columbia University
,
Dongyan Xu
Purdue University

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS '17

Sponsor:

SIGSAC

CCS '17: 2017 ACM SIGSAC Conference on Computer and Communications Security

October 30 - November 3, 2017

Texas, Dallas, USA

Acceptance Rates

CCS '17 Paper Acceptance Rate 151 of 836 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)20

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Garay JKiayias APanagiotakos G(2020)Blockchains from Non-idealized Hash FunctionsTheory of Cryptography10.1007/978-3-030-64375-1_11(291-321)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64375-1_11
Garay JKiayias APanagiotakos G(2020)Consensus from Signatures of WorkTopics in Cryptology – CT-RSA 202010.1007/978-3-030-40186-3_14(319-344)Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-40186-3_14
Al-Odat ZKhan S(2019)The Sponge Structure Modulation Application to Overcome the Security Breaches for the MD5 and SHA-1 Hash Functions2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC)10.1109/COMPSAC.2019.00119(811-816)Online publication date: Jul-2019
https://doi.org/10.1109/COMPSAC.2019.00119
Dodis YGrubbs PRistenpart TWoodage J(2018)Fast Message Franking: From Invisible Salamanders to EncryptmentAdvances in Cryptology – CRYPTO 201810.1007/978-3-319-96884-1_6(155-186)Online publication date: 19-Aug-2018
https://dl.acm.org/doi/10.1007/978-3-319-96884-1_6

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten