Monday, March 25, 2013

Random thoughts: The Birthday Paradox

The Birthday Paradox can be explained by presenting a scenario:
The Birthday problem - 
Out of the 366 possible birthdays (including Feb 29th), what's the chance of, in a crowd of 23 people, that two would be sharing a birthday? A crude guess: Could it be 10%, 20% or maybe 30%? No, 50%. In fact, with only 57 people in a room, the probability shoots up to 99%.

I'm not here to explain the Math, so if you wanna know more, try visiting: (clean urls btw)

So what?
Putting this 'paradox' into hash, colliding a super unique hash may take lesser time than you've thought! Say 2^32 = 4294967296 possible combinations:
To calculate hypothetical hashes with 20000c/s will require about 59 hours.
Chance of some match with the 'birthday paradox' in mind: JUST 80000 combinations (4s) will give you 50%. Wait a minute, that can't be right?!

The generator's generated results:
Number of pairs3199960000 = (80000 * 79999)/2
Chance of a unique pair100.0000% = 4294967295/4294967296
Chance of 3199960000 unique pairs47.47% = (100.0000%)^3199960000
Chance of some match52.53% = 1 - 47.47%
Actual Match %100.00% = (1/1)

Ok, what's your point?
1. Of course, hashes these days are more than 32 bit. But still, I won't use MD5 as 128-bit digest under this scheme is easier than collide than you thought.
2. You have more chance to working with collision than bruteforce with weak hashes such as MD5 (and before). If system authentication process passwords by hashing them and matching with existing stored hash for verification, there's a chance you can use an alternate password to gain access. Sounds like magic - I KNOW.

* If you found some flaws in my logic or math (if any, lol) expressed above, please do help correct.  

Well, these are just some random thoughts...

Break to protect,