# 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.

-
I tried to copyedit your question, but I realized that I wasn't really sure whether you were asking for attacks that break preimage resistance but not collision resistance, or the other way around. Could you please clarify that? –  Ilmari Karonen Oct 27 '13 at 17:31
i think what you have done is a fair job! thanks :) –  john smith Oct 27 '13 at 20:40
OK, great! I've remade the edits. –  Ilmari Karonen Oct 27 '13 at 23:11
possible duplicate of Pre-image resistant but not 2nd pre-image resistant? –  archie Oct 28 '13 at 19:45

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. –  figlesquidge Oct 28 '13 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. –  Dmitry Khovratovich Oct 28 '13 at 15:04
Revealing an additional "valid" password tends to have the stupid property of selecting a password with bad bytes. –  Joshua Nov 17 '13 at 15:57

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? –  john smith Oct 27 '13 at 20:41