Re:The birthday paradox in action: calculating the probabili...
by Xylakant on Wednesday November 07, 2012 @02:55PM
(#4754886)
Actually I was trying to express that the birthday paradox does not apply when you to find a plaintext that evaluates to a known hash, as you'd need to do for password cracking or forging a signed email for example[1]. The birthday paradox only gives you the probability that of a random set of hashes, two are the same. It's "if I generate n random pieces of plaintext, how big is the chance that two of them generate the same hash." Actually it gives you the probability of picking the same element twice from a finite set of elements when you pick n times.
[1] When generating emails more restrictions apply: The colliding plaintexts have to be at least somewhat coherent and probably should express something the attacker wants to express.
Edit: Forgot a negation in a crucial place. Darn.
Re:The birthday paradox in action: calculating the probabili...
by ColinWright on Wednesday November 07, 2012 @03:44PM
(#4755099)
Yes, and that's exactly the point that is addressed in the box I quoted.
You're exactly right, and I believe it's covered. I didn't go into detail about the problems involved in generating a plain text that hashes to a specific hash,such as you mention. I did simply mention that the problem I'm talking about is not that one.
So I don't understand the point dsego was making, because I think my reference is relevant.
At this point I'm no longer sure it really matter.
Re:The birthday paradox in action: calculating the probabili...
by dsego on Wednesday November 07, 2012 @05:47PM
(#4755563)
Sorry, I think I was a bit confused. Now I see that it is the same thing. Sorry for wasting your time :(
Re:The birthday paradox in action: calculating the probabili...
by ColinWright on Wednesday November 07, 2012 @05:56PM
(#4755596)
You haven't wasted my time. You've made me think harder, you've made me reconsider my explanation, and I've helped you become unconfused.
Not a problem, and you're welcome!
The distinguishing characteristics of a cryptographic hash are that it has no internal structure, and it is completely unpredictable based on knowledge of similar source texts. In particular, techniques such as differential analysis don't work.
In that sense, finding a text to map to a hash to give a collision is exactly the same as picking a random number that happens to match. The act of starting with a text and using that to create a hash is identical to the act of choosing a random element of the hash space. If these two things were not identical, then the hash would have some sort of predictability or structure that related it to the source text.
The situation is different if you are using non-cryptographic hashes such as CRCs. Perhaps I should edit the original article to help make that distinction, but I'm not really sure it's worth it.