Friday, March 11, 2005
Encryption: Birthday Attacks
To continue on the SHA-1 issue, birthday attacks (or the birthday paradox) are related to this...
A Birthday Attack is exploiting hash collisions by finding another random message which produces the same hash result.
Birthdays and Attacks...
Imagine a number people in a group.There are 365 days in an year and so there can be 365 possible birthdays.How many people do we need in the group to make the probability of finding 2 people having the same birthday exceed 50%? Believe it or not,the answer is 23.That is the birthday paradox.
Take a group of 23 people.There are 23*22/2 possible pairs ,that is 253.
chances of failure that 2 will have the same birthday is (1-1/365)*(1-1/365)*....253 times which is (1-1/365)253 = 0.4995
chances of success =0.5005
(...gotta try this on a bet someday....haha)
A Birthday Attack is exploiting hash collisions by finding another random message which produces the same hash result.
Birthdays and Attacks...
Imagine a number people in a group.There are 365 days in an year and so there can be 365 possible birthdays.How many people do we need in the group to make the probability of finding 2 people having the same birthday exceed 50%? Believe it or not,the answer is 23.That is the birthday paradox.
Take a group of 23 people.There are 23*22/2 possible pairs ,that is 253.
chances of failure that 2 will have the same birthday is (1-1/365)*(1-1/365)*....253 times which is (1-1/365)253 = 0.4995
chances of success =0.5005
(...gotta try this on a bet someday....haha)
# posted by umberto @ 9:56 PM 
gs