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

I'm no expert but I did a bunch of reading around the time the MD5 collisions were found, and have what I think is a semi-intuitive notion of why preimage resistance is much easier than collision resistance. A hash function has an internal state that is altered by its input, and so each of the bits of its output is essentially a very large Boolean expression of all its input bits. A pre-image attack means that you're given the outputs and need to solve for the inputs, while a collision means setting two sets of these equations together and finding a differing set of inputs which will "cancel out" internally and result in the same output. The latter is easier, because you're not constrained by the outputs --- the final hash output can be anything, as long as you find two different inputs that give the same output.

This very interesting article about using "tunnels" to find collisions in MD5 is worth reading: http://eprint.iacr.org/2006/105.pdf




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

Search: