Paper 2009/506

An Investigation of the Enhanced Target Collision Resistance Property for Hash Functions

Mohammad Reza Reyhanitabar and Willy Susilo and Yi Mu

Abstract

We revisit the enhanced target collision resistance (eTCR) property as a newly emerged notion of security for dedicated-key hash functions, which has been put forth by Halevi and Krawczyk at CRYPTO'06, in conjunction with the Randomized Hashing mode to archive this property. Our contribution is twofold. Firstly, we provide a full picture of the relationships between eTCR and each of the seven security properties for a dedicated-key hash function, considered by Rogaway and Shrimpton at FSE'04; namely, collision resistance (CR), the three variants of second-preimage resistance (Sec, aSec, eSec) and the three variants of preimage resistance (Pre, aPre, ePre). The results show that, for an arbitrary dedicated-key hash function, eTCR is not implied by any of these seven properties, and it can only imply three of the properties; namely, eSec (TCR), Sec, Pre. In the second part of the paper, we analyze eTCR preservation capabilities of several domain extension transforms (a.k.a. modes of operation) for hash functions, including (Plain, Strengthened, and Prefix-free) Merkle-Damgård, Randomized Hashing (variant in the dedicated-key hash function setting), Shoup, Enveloped Shoup, XOR Linear Hash (XLH), and Linear Hash (LH) methods. From this analysis it turns out that, with the exception of a nested variant of LH construction, none of the investigated transforms can preserve eTCR property.

Note: Revised to correct some typos and minor technical errors in the previous version.