Birthday attacks basics

Birthday attack is an attack on hashing algorithms, if you don’t remember what hashing is, you can click here to review.

Birthday attack is basically a brute forcing of one way hash based off the birthday paradox.  The birthday paradox states that in order for there to be 50% chance that someone in a given room shares your birthday, you need 253 people in a room.  If however, you are looking for a greater than 50% chance that any two people in the room have the same birthday, you only need 23 people.

This is only possible because the matches are based on pairs.  If you choose a specific person, then you would need a full 253 people.  Basically, it only takes 23 people to form 253 pairs when cross-matched with each other.

We all know that hashing isn’t perfect and collisions can occur.  This is a big concern of cryptographic algorithms.  This can’t be avoided, because there will be passwords out there that are similar to that of your own.

Well you are probably thinking that hashing outputs will be less likely than the same birth dates, because hashing algorithms create random codes, which makes it much harder to produce collisions.  For example, MD5 always outputs a has of 128bits (3.4*10^38 possible hashes) and 94 characters are accepted by MD5 with length up to 20 (2.9*10^39).  This would make the time to compute all the password hashes would be around 1.4*(10^25) years, and to store them, trillions of petabye drives.

However, this is when the birthday paradox kicks in, making it easier to crack hashing outputs.  Let’s see how this works using the math example: n!/((n^k)(k-n)!)=p.  Now, we have 5.98*10^19 for a 99% chance of collision.  This is something a decent computer nowadays can crack in just a month.

Remember, this is the chance of finding a collision, not finding a specific collision with a specific hash.  But once collisions are found, you can easily uncover how the algorithm generates that hash collisions.

Leave a Reply

Your email address will not be published. Required fields are marked *