Birthday attack

[Andrew Cormack]

If you want an intuitive (though slightly inaccurate) analogy, think of
facing a dark drawer full of loose socks. It should be obvious that
it'll take you fewer digs into the drawer if you are trying to find "any
pair of matching socks" rather than "the pair of socks my mother-in-law
gave me last Christmas". The mathematical oddity, which I still don't
find obvious despite a three-year degree in the stuff, is that it's so
many fewer.

Andrew

--------------------
Andrew Cormack
Chief Security Advisor 
UKERNA, Atlas Centre, Chilton, Didcot, Ox11 0QS, UK

Phone: +44 (0)1235 822302
Fax: +44 (0)1235 822399

> -----Original Message-----
> From: ukcrypto-admin@chiark.greenend.org.uk 
> [mailto:ukcrypto-admin@chiark.greenend.org.uk] On Behalf Of 
> John R T Brazier
> Sent: 11 October 2002 08:10
> To: ukcrypto@chiark.greenend.org.uk
> Subject: RE: Birthday attack
> 
> 
> 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
> 
> 
>