Birthday attack

[Ken Brown]

It's not really a paradox, just common sense!

The chance of getting 2 sixes on a pair of normal dice is one in 36. But
the chance that 2 dice will show the same number as each other, whatever
it is, is only 1 in 6

With something like MD5 the numbers are much bigger than that of course.
The chance of manufacturing a file to have the same hash as a particular
file that you want to spoof is very low. But the chance that somewhere
out in the real world there are, or will be, 2 files which happen have
the same checksum is a lot higher. The chance that a vast computing grid
could find or manufacture 2 such files is quite good.

Of course the files would probably be gibberish...  but then we just
have to say they are encrypted with a 1-time pad and we can 
make them say anything we want :-)

I can imagine a court case involving the same kind of explanations to a
jury that DNA evidence sometimes gets bogged down in.

John R T Brazier wrote:
> 
> Nexus said:
> 
> I'm not sure it has been mentioned, but I'm relying to list anyway in case
> anyone else is asking the same.   It's basically a type of brute force
> attack against hash functions that is based on the rather odd mathematical
> paradox in that if you have 23 people in a room, then the probablility of 2
> or more people in the room having the same birthday is greater than a half.
> Using this method, you look for hash collisions ie if you have an n bit hash
> output, rather than 2^n possible inputs you could expect after trying 2^n/2
> possible inputs that you would get some collision.
> Some more details here http://www.rsasecurity.com/rsalabs/faq/2-4-6.html
> 
> I shall defer to the real crypto types for more details as my O level maths
> isn't up to it ;-)
> 
> ----------------
> 
> The original birthday paradox is based on the fact that you are looking at
> matching any two out of a population (you don't care which two). When
> there's one person in a room, there's a probability of 1 of having a birth
> date. When there's two people, there's only 1 pair of birthdays that might
> match (ie A and B). When there's three people, you have three possible
> matches (A and B, A and C, B and C). With four, you have six pairs (AB, AC,
> AD, BC, BD, CD), and so forth.
> 
> The best way to calculate the odds is to work out the probability of two
> birthdays not matching. So the probability of two people not having matching
> birthdays (assuming 365 days/year - let's keep it simple) = 1 * 364/365.
> 
> The probability of 23 people not having matching birthdays = 1 * 364/365 *
> 363/365 ... * 343/365 = 0.4927028 (approx).
> 
> For hashes, you're looking for the same thing: any two to match, so the
> maths will be similar.
> 
> TTFN
> 
> John B
> TTFN
> 
> Prune