# Are there attacks that break collision resistance but not preimage resistance?

Are there any examples of attacks on hash functions which:

1. break collision resistance and second preimage resistant, or

2. break collision resistance and preimage resistant?

I have looked at Rogaway's paper1, but it seems complicated, hence was wondering if a succinct example exists.

1) Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision-Resistance. Phillip Rogaway and Tom Shrimpton. Fast Software Encryption (FSE) 2004, LNCS vol. 3017, pp. 371–388, Springer, 2004.

Hash functions are usually designed to be both collision and preimage resistant. In practice, due to lower complexity, collision attacks usually come first. For instance, collisions for MD5 were theoretically constructed in 1996, and practically in 2004, whereas the first preimage attack with complexity 2^123 appeared in 2009 and has not been much improved since. MD5 could be considered preimage-resistant, but not collision-resistant at that time.

Attacks that violate collision resistance are usually based on differential cryptanalysis, whereas most of preimage attacks are based on the meet-in-the-middle principle.

It should be easy to construct artificial examples where either of properties is violated. E.g., the function F(x) = 0 for x=0,1, and F(x) = SHA-256(x) elsewhere - has trivial collisions, but most cryptographers would believe in its preimage resistance. In turn G(x) = x for even 256-bit x, and F(x) = SHA-256(x) elsewhere allows preimage recovery with probability 1/2, but it is likely to be as collision resistant as SHA-256 is.

• For an artificial pre-image resistant function with collisions, I would think the zero function is a better choice? Clearly every point leads to a collision, but the output leaks no data about the preimage. Oct 28, 2013 at 15:00
• Well, usually we do not have to recover the actual preimage. For instance, a preimage attack on a password hash table recovers a valid password which may be different from the original. Oct 28, 2013 at 15:04
• Revealing an additional "valid" password tends to have the stupid property of selecting a password with bad bytes. Nov 17, 2013 at 15:57
• The example G is not collision resistant. For example, G('test') happens to be even, so G(G('test')) = G('test').
– otus
Oct 12, 2015 at 9:13

The problem you're likely to encounter is that most real-world hash function attacks will be collision attacks, because collisions can be found with at least $2^{n/2}$ efficiency (or better, if the algorithm has a known weakness.) Preimage attacks don't necessarily have to have such a tidy relationship with the size of the digest, and if they're even slightly less efficient, a practical attacker will simply use a collision attack.

May I suggest an alternate course of action for you? Try creating your own examples using much simpler (non-cryptographically secure) hash functions, such as CRC-16 (or even CRC-8). Toy examples will help you explore and learn "why", yet they will not prevent you from testing problems that require some amount of brute-force.

• Thanks for the reply. so isnt there any straightforward hash function that we could use to show both properties? or its that the construction isnt easy but the property is obvious? Oct 27, 2013 at 20:41