Paper 2007/176

Seven-Property-Preserving Iterated Hashing: ROX

Elena Andreeva, Gregory Neven, Bart Preneel, and Thomas Shrimpton


Nearly all modern hash functions are constructed by iterating a compression function. At FSE'04, Rogaway and Shrimpton [RS04] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study points out that none of them preserves more than three notions from [RSh04]. In particular, only a single iteration preserves Pre, and none preserves Sec, aSec, or aPre. The latter two notions are particularly relevant for practice, because they do not rely on the problematic assumption that practical compression functions be chosen uniformly from a family. In view of this poor state of affairs, even the mere existence of seven-property-preserving iterations seems uncertain. As a second contribution, we propose the new Random-Oracle XOR(ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Cryptographic hash functionsMerkle-Damgardcollision resistancepreimage resistancesecond preimage resistanceprovable security.
Contact author(s)
elena andreeva @ esat kuleuven be
2007-10-30: last of 2 revisions
2007-05-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elena Andreeva and Gregory Neven and Bart Preneel and Thomas Shrimpton},
      title = {Seven-Property-Preserving Iterated Hashing: ROX},
      howpublished = {Cryptology ePrint Archive, Paper 2007/176},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.