Paper 2012/363

A Unified Indifferentiability Proof for Permutation- or Block Cipher-Based Hash Functions

Anne Canteaut, Thomas Fuhr, María Naya-Plasencia, Pascal Paillier, Jean-René Reinhard, and Marion Videau


In the recent years, several hash constructions have been introduced that aim at achieving enhanced security margins by strengthening the Merkle-Damgård mode. However, their security analysis have been conducted independently and using a variety of proof methodologies. This paper unifies these results by proposing a unique indifferentiability proof that considers a broadened form of the general compression function introduced by Stam at FSE09. This general definition enables us to capture in a realistic model most of the features of the mode of operation ({\em e.g.}, message encoding, blank rounds, message insertion,...) within the pre-processing and post-processing functions. Furthermore, it relies on an inner primitive which can be instantiated either by an ideal block cipher, or by an ideal permutation. Then, most existing hash functions can be seen as the Chop-MD construction applied to some compression function which fits the broadened Stam model. Our result then gives the tightest known indifferentiability bounds for several general modes of operations, including Chop-MD, Haifa or sponges. Moreover, we show that it applies in a quite automatic way, by providing the security bounds for 7 out of the 14 second round SHA-3 candidates, which are in some cases improved over previously known ones.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
hash functionsindifferentiabilitySHA-3
Contact author(s)
jean-rene reinhard @ m4x org
2012-07-06: revised
2012-06-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anne Canteaut and Thomas Fuhr and María Naya-Plasencia and Pascal Paillier and Jean-René Reinhard and Marion Videau},
      title = {A Unified Indifferentiability Proof for Permutation- or Block Cipher-Based Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/363},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.