Birthday attack – Wikipedia

And birthday attack It is a type of cryptographic attack used for the encryption of encryption algorithms; It is so called because it uses the mathematical principles of the birthday paradox in the theory of probability.

The birthday attack can be summarized as follows as follows: given a function f , the aim of the attack is to find 2 numbers

${displaystyle x_{1},x_{2}}$

such that

${displaystyle f(x_{1})=f(x_{2})}$

. This pair of values

${displaystyle x_{1},x_{2}}$

It is called collision. The method used to find a collision is simply to evaluate the function f For different input values ​​that can be chosen randomly or pseudo-casally until the same result is obtained. Due to the birthday paradox, this method can be very efficient: specifically, if a function

${displaystyle f(x)}$

returns the values ​​of its codominum

${displaystyle H}$

with identical probability and the dimension of codominum

${displaystyle H}$

(i.e. the number of possible values) is large enough, after evaluating the function for about

${displaystyle 1.25cdot {sqrt {H}}}$

different topics, there is 50% probability of obtaining a couple of distinct values

${displaystyle x_{1}}$

It is

${displaystyle x_{2}}$

for which it is worth

${displaystyle f(x_{1})=f(x_{2})}$

.

We consider the following experiment. From a set of values

${displaystyle H}$

we choose

${displaystyle n}$

Uniformly random values, thus also allowing them to repeat them. We put

${displaystyle p(n;H)}$

The probability that during the experiment at least one value is chosen more than once. The probability can be approximate to

${displaystyle p(n;H)approx 1-e^{-(n(n-1))/2cdot H}approx 1-e^{-n^{2}/{2cdot H}},}$

Let’s set now

${displaystyle n(p;H)}$

Like the smallest number of values ​​we have chosen, such that the probability that we can expect to find a collision is at least

${displaystyle p}$

. Reversing the expression above, we find the following approximation

${displaystyle n(p;H)approx {sqrt {2cdot Hcdot ln left({1 over 1-p}right)}},}$

and assigning the probability of finding a collision at 0.5 we arrive at

${displaystyle n(0.5;H)approx 1.1774{sqrt {H}}}$

.

We put

${displaystyle Q(H)}$

Like the expected number of values ​​that we must choose before finding the first collision. The number can be approximate from

${displaystyle Q(H)approx {pi over 2}{sqrt {H}}.}$

As an example, if a 64 -bit hash is used, there are approximately 1.8 × 10 ¹⁹ different results. If they are all equally likely (in the best of cases), then “only” 5.1 × 10 will be needed ⁹ attempts to generate a collision using brute force. This value is called birthday constraint and for codes of n bit can be calculated as

${displaystyle 2^{n/2}}$

^[first] .
Other examples are as follows:

Bit	Possible results (H)	Desired probability of the random collision (P)
		ten −18	ten −15	ten −12	ten −9	ten −6	0.1%	first%	25%	50%	75%
32	4.3 × 10 9	2	2	2	2.9	93	2.9 × 10 3	9.3 × 10 3	5.0 × 10 4	7.7 × 10 4	1.1 × 10 5
sixty four	1.8 × 10 19	6.1	1.9 × 10 2	6.1 × 10 3	1.9 × 10 5	6.1 × 10 6	1.9 × 10 8	6.1 × 10 8	3.3 × 10 9	5.1 × 10 9	7.2 × 10 9
128	3.4 × 10 38	2.6 × 10 ten	8.2 × 10 11	2.6 × 10 13	8.2 × 10 14	2.6 × 10 16	8.3 × 10 17	2.6 × 10 18	1.4 × 10 19	2.2 × 10 19	3.1 × 10 19
256	1.2 × 10 77	4.8 × 10 29	1.5 × 10 thirty first	4.8 × 10 32	1.5 × 10 34	4.8 × 10 35	1.5 × 10 37	4.8 × 10 37	2.6 × 10 38	4.0 × 10 38	5.7 × 10 38
384	3.9 × 10 115	8.9 × 10 48	2.8 × 10 50	8.9 × 10 51	2.8 × 10 53	8.9 × 10 54	2.8 × 10 56	8.9 × 10 56	4.8 × 10 57	7.4 × 10 57	1.0 × 10 58
512	1.3 × 10 154	1.6 × 10 68	5.2 × 10 69	1.6 × 10 71	5.2 × 10 72	1.6 × 10 74	5.2 × 10 75	1.6 × 10 76	8.8 × 10 76	1.4 × 10 77	1.9 × 10 77

The table shows the number of hash n(p) necessary to obtain the specified successful probability, assuming that all hash are equally possible. As a comparison, the incorrect bit rate that is incorrectly correct to a hard disk varies from 10 ⁻¹⁸ a 10 ⁻¹⁵ [first] . In theory, the MD5, with its 128 -bit long hash, should fall within this interval of up to 820 billion of documents, even if its possible outputs are much more.

It is easy to see that if the function outputs are distributed in an unequal way, then a collision can be found much faster. The notion of balance of a hash function quantifies the resistance of the function to the birthday attacks and allows to estimate the vulnerability of popular hash such as the MDX and the SHA ( Bellare e Kohno, 2004 ).

Digital signatures can be vulnerable to a birthday attack. A message

${displaystyle m}$

It is generally signed first by calculating

${displaystyle f(m)}$

, Where

${displaystyle f}$

It is a cryptographic function of hash, and then using some secret key to sign

${displaystyle f(m)}$

. Suppose that Oscar wants to cheat Bob by inducing him to sign a fraudulent contract. Oscar prepares a contract

${displaystyle m}$

correct and one

${displaystyle m’}$

fraudulent. Oscar then finds a number of points in the contract for which

${displaystyle m}$

It can be modified without changing its meaning, for example by inserting quotes, empty lines, one or two spaces after a sentence, replacing synonyms etc. By combining these changes, Oscar can create a considerable number of variants of

${displaystyle m}$

that all correct contracts are in practice. Similarly, it also creates a large number of variants of the fraudulent contract

${displaystyle m’}$

. In the end, Oscar applies the hash function to all these variants until he finds a variant of the correct contract and a variant of the fraudulent one that have the same value as hash, that is

${displaystyle f(m)=f(m’)}$

. At this point, Oscar presents Bob the correct version for the signature. After Bob signed him, Oscar signs and attacks him to the fraudulent contract. Now the signing “Test” that Bob has signed the fraudulent contract.

This way of operating differs slightly from the original birthday paradox as Oscar does not earn anything from obtaining two correct contracts or two fraudulent contracts with the same hash. Oscar’s optimal strategy is to generate couples consisting of a correct and fraudulent contract. Oscar compares every couple just generated with all the others, that is, it compares the hash of the correct copy with the hash of all the previous fraudulent copies, and the new fraudulent contract with the hash of all the previous correct contracts (without worrying about comparing the hash of the fraudulent contract generated with all the hash of the previous fraudulent contracts nor the hash of the correct contract generated with all the hash of the previous correct contracts). The equations of the birthday paradox apply with n which assumes the value of the number of couples (the number of hash that Oscar must generate is 2n ).

To avoid this attack, the length of the output of a hash function used in a digital signature scheme must be large enough so that the birthday attack becomes computationally not feasible: in general, we are in the order of double the number of bits needed to prevent a classic brute force attack.

The Rho di Pollard algorithm is an example of algorithm that uses a birthday attack for the calculation of discreet logarithms.