Birthday attack

[Nexus]

----- Original Message -----
From: "Peter Tomlinson" <pwt@iosis.co.uk>
To: <ukcrypto@chiark.greenend.org.uk>
Sent: Thursday, October 10, 2002 10:23 PM
Subject: Re: OT: utility account transfer frauds


> Have I missed something? Could someone explain the 'birthday attack'?
> (privately if I did miss something)

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 ;-)

Cheers,
            JJ