Cryptology ePrint Archive: Report 2012/363

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

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

Abstract: 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.

Category / Keywords: secret-key cryptography / hash functions, indifferentiability, SHA-3

Date: received 27 Jun 2012, last revised 6 Jul 2012

Contact author: jean-rene reinhard at m4x org

Available format(s): PDF | BibTeX Citation

Version: 20120706:153519 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]