Hacker News new | past | comments | ask | show | jobs | submit login

Given only the explanation, I think I'd have a hard time figuring out how collision resistance differs from second-preimage resistance. After all, if you generate a collision, you have two inputs (preimages) that hash to the same output (image) so isn't the second input a second pre-image of the first input?

I'm not an expert, but I'll try to explain how I think this works, and invite real experts to step in if I get it wrong.

I think the way this works is that, with collisions, the attacker gets to choose their inputs. They don't care what two inputs they find that generate to the same output, they only care that they do generate to the same output. With a second-preimage attack, one of the inputs is chosen by the hasher.

As it turns out, the ability to choose both your inputs is quite useful! You can view hash functions in reverse: for a given hash function, the inverse hash function is a function which takes the output of the hash function and returns the set of inputs to the hash function. For many hash functions, the inverse hash function IS NOT uniformly difficult to compute partial solutions to: some inverse hashes are much easier to compute than others. So if you can find an output for which the inverse hash is easy to partially compute, you can generate collisions at that point much more easily.

However, in the space of possible hash outputs, the number for which the inverse hash is easier to compute is probably very small, or the possibility of computing the inverse hash would have been noticed by the creators of the hash function. So it's highly improbable that the hasher will have chosen a hash input at a point where the hash input is one where the inverse hash is easy to compute.




Collision attack: Find two different messages with the same hash.

[First] pre-image attack: Given a hash value, find a message with that hash.

Second pre-image attack: Given a message, find a different message with the same hash.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: