Birthday attack

[John R T Brazier]

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