Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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)

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 March 4, 2024)
Created December 3, 2009, Updated October 12, 2021