TY - GEN

T1 - Salvaging merkle-damgard for practical applications

AU - Dodis, Yevgeniy

AU - Ristenpart, Thomas

AU - Shrimpton, Thomas

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - Many cryptographic applications of hash functions are analyzed in the random oracle model. Unfortunately, most concrete hash functions, including the SHA family, use the iterative (strengthened) Merkle-Damgård transform applied to a corresponding compression function. Moreover, it is well known that the resulting "structured" hash function cannot be generically used as a random oracle, even if the compression function is assumed to be ideal. This leaves a large disconnect between theory and practice: although no attack is known for many concrete applications utilizing existing (Merkle-Damgård based) hash functions, there is no security guarantee either, even by idealizing the compression function. Motivated by this question, we initiate a rigorous and modular study of developing new notions of (still idealized) hash functions which would be (a) natural and elegant; (b) sufficient for arguing security of important applications; and (c) provably met by the (strengthened) Merkle- Damgård transform, appli to a "strong enough" compression function. In particular, we develop two such notions satisfying (a)-(c): a preimage aware function ensures that the attacker cannot produce a "useful" output of the function without already "knowing" the corresponding preimage, and a public-use random oracle, which is a random oracle that reveals to attackers messages queried by honest parties.

AB - Many cryptographic applications of hash functions are analyzed in the random oracle model. Unfortunately, most concrete hash functions, including the SHA family, use the iterative (strengthened) Merkle-Damgård transform applied to a corresponding compression function. Moreover, it is well known that the resulting "structured" hash function cannot be generically used as a random oracle, even if the compression function is assumed to be ideal. This leaves a large disconnect between theory and practice: although no attack is known for many concrete applications utilizing existing (Merkle-Damgård based) hash functions, there is no security guarantee either, even by idealizing the compression function. Motivated by this question, we initiate a rigorous and modular study of developing new notions of (still idealized) hash functions which would be (a) natural and elegant; (b) sufficient for arguing security of important applications; and (c) provably met by the (strengthened) Merkle- Damgård transform, appli to a "strong enough" compression function. In particular, we develop two such notions satisfying (a)-(c): a preimage aware function ensures that the attacker cannot produce a "useful" output of the function without already "knowing" the corresponding preimage, and a public-use random oracle, which is a random oracle that reveals to attackers messages queried by honest parties.

UR - http://www.scopus.com/inward/record.url?scp=67650652323&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67650652323&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-01001-9_22

DO - 10.1007/978-3-642-01001-9_22

M3 - Conference contribution

AN - SCOPUS:67650652323

SN - 3642010008

SN - 9783642010002

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 371

EP - 388

BT - Advances in Cryptology - EUROCRYPT 2009 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

T2 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2009

Y2 - 26 April 2009 through 30 April 2009

ER -