Indifferentiability Characterization of Hash Functions and Optimal Bounds of Popular Domain Extensions

Published

December 4, 2009

Author(s)

Rishiraj Bhattacharya, Avradip Mandal, Mridul Nandi

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 maximum number of blocks in a single query and \sigma is the total number of blocks in all q queries made by the distinguisher.

Proceedings Title

Progress in Cryptology - INDOCRYPT 2009 (Lecture Notes in Computer Science)

Volume

5922

Conference Dates

December 13-16, 2009

Conference Location

New Delhi, IN

Conference Title

10th International Conference on Cryptology in India (INDOCRYPT 2009)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-642-10628-6_14

Local Download

Keywords

indifferentiability, Merkle-Damgaard, HAIFA, tree mode of operations with counter

Citation

Bhattacharya, R. , Mandal, A. and Nandi, M. (2009), Indifferentiability Characterization of Hash Functions and Optimal Bounds of Popular Domain Extensions, Progress in Cryptology - INDOCRYPT 2009 (Lecture Notes in Computer Science) , New Delhi, IN, [online], https://doi.org/10.1007/978-3-642-10628-6_14, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903173 (Accessed May 10, 2024)