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.

On the Security of Hash Functions Employing Blockcipher Postprocessing

Published

Author(s)

Dong H. Chang, Mridul Nandi, Moti Yung

Abstract

Analyzing desired generic properties of hash functions is an important current area in cryptography. For example, in Eurocrypt 2009, Dodis, Ristenpart and Shrimpton introduced the elegant notion of "Preimage Awareness" (PrA) of a hash function H^P , and they showed that a PrA hash function followed by an output transformation modeled to be a FIL (fixed input length) random oracle is PRO (pseudorandom oracle) i.e. indifferentiable from a VIL (variable input length) random oracle. We observe that for recent practices in designing hash function (e.g. SHA-3 candidates) most output transformations are based on permutation(s) or blockcipher(s), which are not PRO. Thus, a natural question is how the notion of PrA can be employed directly with these types of more prevalent output transformations? We consider the Davies-Meyer's type output transformation OT(x) := E(x)⊕ x where E is an ideal permutation. We prove that OT(HP (·)) is PRO if H^P is PrA, preimage resistant and computable message aware (a related but not redundant notion, needed in the analysis that we introduce in the paper). The similar result is also obtained for 12 PGV output transformations. We also observe that some popular double block length output transformations can not be employed as output transformation.
Proceedings Title
FSE 2011
Volume
6733
Conference Dates
February 13-16, 2011
Conference Location
Lyngby, -1

Keywords

Computable Message Awareness, preimage awareness (PRA), pseudorandom oracle (PRO), pseudorandom permutation (PRP)

Citation

Chang, D. , Nandi, M. and Yung, M. (2011), On the Security of Hash Functions Employing Blockcipher Postprocessing, FSE 2011, Lyngby, -1, [online], https://doi.org/10.1007/978-3-642-21702-9_9 (Accessed August 1, 2021)
Created July 14, 2011, Updated November 10, 2018