Paper 2007/395

Second Preimage Attacks on Dithered Hash Functions

Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, and Sebastien Zimmer

Abstract

The goal of this paper is to analyze the security of dithered variants of the Merkle-Damgard mode of operation that use a third input to indicate the position of a block in the message to be hashed. These modes of operation for hash functions have been proposed to avoid some structural weaknesses of the Merkle-Damgard paradigm, e.g. that second preimages can be constructed in much less than $2^n$ work, as pointed out by Kelsey and Schneier. Among the modes of operation that use such a third input are Rivest's dithered hashing and Biham and Dunkelman's HAIFA proposal. We propose several new second preimage attacks on the Merkle-Damgard mode of operation, which can also attack Rivest's dithered hash with almost the same complexity. When applied to Shoup's UOWHF, these attacks can be shown to be optimal since their complexity matches Shoup's security bound.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Submitted to EUROCRYPT'08
Keywords
CryptanalysisHash FunctionDithering
Contact author(s)
charles bouillaguet @ ens fr
History
2007-10-14: received
Short URL
https://ia.cr/2007/395
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/395,
      author = {Charles Bouillaguet and Pierre-Alain Fouque and Adi Shamir and Sebastien Zimmer},
      title = {Second Preimage Attacks on Dithered Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2007/395},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/395}},
      url = {https://eprint.iacr.org/2007/395}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.