Introduction to the

Birthday attacks are a matter of probability theory, which means that something that seems very unlikely to happen has a very high probability of happening. 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 question

The birthday problem, also known as the birthday paradox, is described this way.

If n people are chosen at random, what is the probability that two of these n people have the same birthday? If you want the probability to be 100%, you only have to choose 367 people. There are only 366 birthday dates (including February 29).

If you want a 99.9 percent chance, you only need 70 people. You only need 23 people 50% of the time.

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

Sounds amazing, doesn’t it? That’s a lot less than the cardinality in our first image.

Let’s look at a probability graph:

In practice, the probabilistic model of birthday problems can be applied to reduce the complexity of collision attacks, or to evaluate the probability of possible collision attacks in a hash function.

So how do we calculate that?

If P(A) is the probability of having the same birthday, then P(A) = 1 – P(A ‘), where P(A ‘) is the probability of having different birthdays.

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

The probability that we can get 23 different birthdays is approximately 0.492703.

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

Let’s look at another chart to make it more intuitive:

A derivative of the birthday question

The range of the birthday question is within 365 days of the year, meaning there are only 365 possible birthdays.

Let’s extend this 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’s and y’s, so that f(x)=f(y).

At this point, we can say that x and y have collided.

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

To express possible results in bits, we can refer to the following probability table:

Birthday attack application

Birthday attacks are generally used in digital signatures. In general, in order to sign confidential messages, because of encryption limitations, if the message is large, it is not possible to sign all the messages. The message is usually hash computed and then signed.

For example, if someone wants to make a fraudulent contract, they will modify it on the basis of the original contract and try again and again to find a modified contract that has the same hash as the original contract, resulting in the same signature.

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

This article is available at www.flydean.com/birthday-at…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

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