What is a Birthday Attack and How to Prevent It?

A birthday attack belongs to the family of brute force attacks and is based on the probability theorem. It is a cryptographic attack and its success is largely based on the birthday paradox problem. Such attacks are designed to exploit the communication between two parties and largely depend on the commonness found between multiple random attacks and a fixed degree of permutation.

What is the Birthday Paradox Problem?

According to probability theory, Birthday Paradox Problem means that if you have ‘n” number of people in a room there is a possibility that few of them will have their birthdays on the same day. However, an important point to note here is that we are not matching a specific birth date but are looking at any 2 people sharing their birthdays. Let’s understand the concept with the help of an example:

Let’s assume a normal year has 365 days.
Fill the room with 23 people.
So here “A” has 1/365 chance to share your birthday with another 22 people that means your probability is 22/365.
If “A” birthday does not match, “B” will have a probability of 21/365 to have its birthday matching with the remaining people in the room.
Now if “B” also fails to get a match “C” will have a probability of 20/365 and so on.
If you add on all the possibilities of all the people in the room i.e. 22/365+21/365+20/365 and so on, you get a total probability of 50 %.
Likewise to get a probability of 99.9% you need 70 people in the room, and to get 100 % probability you need 366 people.

So, Birthday attacks use probabilistic logic to reduce the complexity in getting a matched collision and find the approximate risk of the existence of a hash collision within a given number. This also means that finding a specific hash collision is more difficult than finding a matching hash collision with the same values.

One of the most common uses of the birthday paradox attack is digital signature susceptibility. Read further to get a basic understanding of the concept.

Digital Signature Susceptibility

A digital signature is one area that is highly susceptible to a birthday attack.

f – cryptographic function.
M-message signed as f(m) using a specific secret key.
So suppose Mark wants to cheat Jack by getting a fraudulent document signed by him.
Mark makes a legitimate document called (m) and a fraudulent one named as (m’)
Here if Mark changes (m) to (m’) at several positions he will be able to create multiple variations of the legitimate document (m).
Similarly, Mark also created several variations of fraudulent documents.
Here Mark can use the hash function to match hash values of f(m)= f(m’).
Now even if Jack signs the legitimate document, Mark can easily replace it with the matching fraudulent document and prove that Jack originally signed the fraudulent document.

To conclude, security experts recommend that we should also use a very strong combination and a long sequence of bit length to prevent brute-force attacks.

Adrian