Introduction to the

The birthday attack is actually a probability theory problem, which means that something that seems very difficult to happen is actually very likely to happen. This difference between subjective and actual probability makes random attacks more likely to succeed, and such attacks are called birthday attacks.

The origin of the birthday problem

The birthday problem is also known as the birthday paradox, and it goes like this.

If n people are chosen at random, what is the probability that two of those n people have the same birthday. If you want the probability to be 100%, you just have to pick 367 people. Because there are only 366 birthday dates (including February 29).

Only 70 people would be needed to have a 99.9 percent chance. It’s only 23 people, 50% of the time.

For today’s kindergarteners, there are almost 30 students in a class, so there is a greater than 50% chance that two of them will have the same birthday.

Sounds amazing, doesn’t it? Whether the cardinality in our first image is much less.

Let’s look at a probability graph:

In practical applications, the probability model of the birthday problem can be applied to reduce the complexity of collision attacks or to evaluate the probability of collision attacks occurring in a hash function.

How do we calculate that?

If P(A) is the probability of having the same birthday, then P(A) = 1-p (A<super> ‘</super>), where P(A<super>’ </super>) is the probability of having different birthdays.

The probability of one person having different birthdays is 365/365, and the probability of two people having different birthdays is 365/365 * 364/365, and so on.

The probability that 23 people have different birthdays is about 0.492703.

That means there’s a greater than 50% chance that two out of 23 people have the same birthday.

Let’s take a look at another table for a more visual description:

The derivation of the birthday question

The value range of the birthday question is within 365 days of the year, which means that there are only 365 possible birthdays.

To extend the problem to the general case, suppose we have a function f whose output range is H, then our attack is to find two different x, y, and make f(x)=f(y).

At that point, we could say that x and y collide.

According to the formula of probability theory, if we want to achieve a 50% chance, then the number of attempts needed is:

If the possible results are expressed in bits, we can refer to the following probability table:

The application of birthday attacks

Birthday attacks are commonly used in digital signatures. In general, in order to sign confidential messages, because of encryption restrictions, if the message is large and it is not possible to sign all the messages, it is common to calculate the hash value of the message and then sign the hash value.

For example, if someone wants to make a fraudulent contract, he or she will modify the original contract and constantly try to find a modified contract, so that the hash of the contract is the same as that of the previous contract, so that the signature of the two contracts is the same.

How to defend against such attacks? According to our formula for the birthday attack, of course, the output length of the hash function used by the signature scheme is chosen to be large enough to make the birthday attack computationally infeasible.

This article has been included in http://www.flydean.com/birthday-attack/

The most popular interpretation, the most profound dry goods, the most concise tutorial, many you do not know the tips to wait for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!