# Difference between collision resistance and target collision resistance

For a hash function, what's the difference between Collision Resistance and Target Collision Resistance?.

I understand the definition of hash function collision resistance, but I don't know about Target Collision Resistance.

-

Pre-image resistant but not 2nd pre-image resistant? describes the relationship between the three basic hash function security notions: Collision Resistance, Second Preimage Resistance and Preimage Resistance.

In short, Collision Resistance implies Second Preimage Resistance (but not vice-versa) - there is a good diagram on page 4 of RogawayShrimpton04 that illustrates the relationships.

The notion of Target Collision Resistance (which was introduced in BellareRogaway97) is a type of Second Preimage Resistance, and is implied by Collision Resistance.

More formally, Target Collision Resistance describes the ability of an adversary to find a second preimage for a fixed message (compared to the more general notion of Second Preimage Resistance, where the adversary to find a second preimage for a randomly chosen message).

These notions actually sound really similar (and probably in practice are) if you think about real world hash functions, but make more sense when you consider the security notions (and proofs of them) use keyed hash functions - in TCR, the adversary tries to find second preimages for a fixed message over multiple experiments with random keys, while in general 2PIR the message and the key are random in every experiment.

-
Exist any didactic book to learn about these notion, hash function, UOWF, etc, ...? –  juaninf Nov 6 '13 at 0:40
Chapter 9 of the handbook of Applied Cryptography, mentioned in @Reids answer above is good, as are the papers in that answer and mine. –  archie Nov 6 '13 at 2:46

While collision resistance can be defined for normal hash functions like SHA1, for target collision resistance you need a so called keyed hash function, that is a hash function that additionally to a message $m$ also takes a key $k$. The simplest way to construct a keyed hash function out of a regular one is to prepend the key in front of the message: $f(k,m)\mapsto h(k||m)$.

Let's begin with the definition of collision resistance: A hash function $h$ is called collision resistant if it computational infeasible to find two messages $m_1$ and $m_2$ such that $h(m_1)=h(m_2)$. One popular use case for collision resistant hash function are signature schemes. If you have a signature primitive $s(k_\text{priv},m_\text{fixed})$ that can sign messages of fixed length you can extend it to a scheme that signs messages of arbitrary length by first hashing the message: $s_\text{arbitr}(k_\text{priv},m)=s(k_\text{priv},h(m))$.

The notion of target collision resistance hash functions (or Universal one-way hash functions as it was previously called by Naor and Young) is a reaction to observing that building collision resistant hash functions is difficult, but that we can still have strong signature schemes with less stringent requirements. The idea is to "salt" the hash of each signature with some randomness so that an attacker does not know the internal state of the hash function when the he or she wants to compute a collision. This salt has to be signed as well as the hash and published alongside the signature.

Specifically take a keyed hash function and for every signature choose a random $r$ and sign like this $s_\text{arbitr}(k_\text{priv},m_\text{fixed},r)=r||s(k_\text{priv},r||f(r,m))$. With the above construction and using MD5 this would be $r||s(k_\text{priv},r||\text{MD5}(r||m))$ and is still secure even though there are collision attacks against MD5. The reason is that an attacker has to either construct a colliding message pair $m_1,m_2$ for an unknown key and thus unknown internal state of the hash function or find a second pre-image for a known key after the signature is published. Both is significantly harder than finding simple collisions.

The definition of target collision formalizes the setting under which we want the keyed hash function to be secure in such a signature scheme: An attacker has to first find a message $m_1$, then a key $k$ is randomly chosen, then the attacker is told $k$ and has to find a second message $m_2$ such that $f(k,m_1)=f(k,m_2)$. If it is computational infeasible to do so for an attacker then the keyed hash function is called target collision resistant.

A good way to construct a keyed hash function out of a hash function using a Merkle-Damgard construction (like MD5, SHA1, SHA2) is RMX, that has some nice reduction proof to a security property of the underlying compression function. There is also a NIST publication that defines that mode in detail.

Note 1: Don't use $f(k,m)\mapsto h(k||m)$ as a construction for message authentication codes (which also use keyed hash functions), as it is insecure for MD5, SHA1 and SHA2. Instead use HMAC.

Note 2: Also, even though MD5 and SHA1 are still secure in some randomized settings, please don't use them anymore and instead choose SHA2 or SHA3.

-