On the Security of Iterated Hashing based on Forgery-resistant Compression Functions

Charles Bouillaguet; Orr Dunkelman; Pierre-Alain Fouque; Antoine Joux

Paper 2009/077

On the Security of Iterated Hashing based on Forgery-resistant Compression Functions

Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, and Antoine Joux

Abstract

In this paper we re-examine the security notions suggested for hash functions, with an emphasis on the delicate notion of second preimage resistance. We start by showing that, in the random oracle model, both Merkle-Damgaard and HAIFA achieve second preimage resistance beyond the birthday bound, and actually up to the level of known generic attacks, hence demonstrating the optimality of HAIFA in this respect. We then try to distill a more elementary requirement out of the compression function to get some insight on the properties it should have to guarantee the second preimage resistance of its iteration. We show that if the (keyed) compression function is a secure FIL-MAC then the Merkle-Damgaard mode of iteration (or HAIFA) still maintains the same level of second preimage resistance. We conclude by showing that this ``new'' assumption (or security notion) implies the recently introduced Preimage-Awareness while ensuring all other classical security notions for hash functions.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): charles bouillaguet @ ens fr
History: 2009-02-16: received
Short URL: https://ia.cr/2009/077
License: CC BY

BibTeX

@misc{cryptoeprint:2009/077,
      author = {Charles Bouillaguet and Orr Dunkelman and Pierre-Alain Fouque and Antoine Joux},
      title = {On the Security of Iterated Hashing based on Forgery-resistant Compression Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/077},
      year = {2009},
      url = {https://eprint.iacr.org/2009/077}
}