Abstract. Understanding what construction strategy has a chance to be a good hash function is extremely important. Nowadays it is getting more importance due to current SHA3 competition which is intended to make a standard for hash functions. In TCC 04, Maurer et al introduced the notion of... See full abstract

Abstract. Understanding what construction strategy has a chance to be a good hash function is extremely important. Nowadays it is getting more importance due to current SHA3 competition which is intended to make a standard for hash functions. In TCC 04, Maurer et al introduced the notion of indifferentiability as a generalization of the concept of the indistinguishability of two systems. Indifferentiability is the appropriate random oracle as well as strong security notion for a hash-design. Since then we know several results providing indifferentiability upper bounds for many hash designs. In this paper, we provide a general framework of this direction of research by providing an indifferentiability bound for a wide class of hash designs GDE (or generalized domain extension) using Maurer s methodology. This is a natural and an intuitive class containing almost all hash designs. As immediate applications of the result, we are able to provide simple and optimal indifferentiability upper bounds for HAIFA mode (many SHA3 candidates such as BLAKE, LANE, SHABAL, Skein, SHAvite-3 etc.), or tree mode with counter (e.g. the mode used inMD6). Moreover, we demonstrate matching attacks for these modes to show that these upper bounds are indeed tight and hence can not be further reduced. In particular, we have shown that n-bit HAIFA hash functions have tight indifferentiability bound \Theta(q\sigma/2^n) where q is the number of queries, \sigma is the total number of blocks in the queries made by the distinguisher. The MD6-mode outputting n-bits has tight \Theta(q^2 log l/2^n) indifferentiability bound where l is the number of blocks in the longest query.
Hide full abstract