Birthday attack

The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes).

With a birthday attack, it is possible to find a collision of a hash function with

[2] There is a general (though disputed[3]) result that quantum computers can perform birthday attacks, thus breaking collision resistance, in

[5]: 36 As an example, consider the scenario in which a teacher with a class of 30 students (n = 30) asks for everybody's birthday (for simplicity, ignore leap years) to determine whether any two students have the same birthday (corresponding to a hash collision as described further).

A pair of benign and malicious contracts with the same signature is sought.

In this fictional example, suppose that the digital signature of a string is the first byte of its SHA-256 hash.

After the victim accepts the benign contract, the attacker substitutes it with the malicious one and claims the victim signed it, as proven by the digital signature.

The birthday attack can be modelled as a variation of the balls into bins problem, where balls (hash function inputs) are randomly placed into bins (hash function outputs).

The method used to find a collision is simply to evaluate the function

for different input values that may be chosen randomly or pseudorandomly until the same result is found more than once.

is sufficiently large, then we expect to obtain a pair of different arguments

Let n(p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. By inverting this expression above, we find the following approximation and assigning a 0.5 probability of collision we arrive at Let Q(H) be the expected number of values we have to choose before finding the first collision.

If these are all equally probable (the best case), then it would take 'only' approximately 5 billion attempts (5.38×109) to generate a collision using brute force.

[8] This value is called birthday bound[9] and it could be approximated as 2l/2, where l is the number of bits in H.[10] Other examples are as follows: It is easy to see that if the outputs of the function are distributed unevenly, then a collision could be found even faster.

However, determining the balance of a hash function will typically require all possible inputs to be calculated and thus is infeasible for popular hash functions such as the MD and SHA families.

when directly translated into common programming languages as log(1/(1-p)) due to loss of significance.

A good rule of thumb which can be used for mental calculation is the relation which can also be written as or This works well for probabilities less than or equal to 0.5.

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

Suppose Mallory wants to trick Bob into signing a fraudulent contract.

By combining these changes, she can create a huge number of variations on

In a similar manner, Mallory also creates a huge number of variations on the fraudulent contract

She then applies the hash function to all these variations until she finds a version of the fair contract and a version of the fraudulent contract which have the same hash value,

After Bob has signed, Mallory takes the signature and attaches it to the fraudulent contract.

This signature then "proves" that Bob signed the fraudulent contract.

The probabilities differ slightly from the original birthday problem, as Mallory gains nothing by finding two fair or two fraudulent contracts with the same hash.

Mallory's strategy is to generate pairs of one fair and one fraudulent contract.

For a 50% chance of a collision, Mallory would need to generate approximately

hashes, which is twice the number required for a simple collision under the classical birthday problem.

Besides using a larger bit length, the signer (Bob) can protect himself by making some random, inoffensive changes to the document before signing it, and by keeping a copy of the contract he signed in his own possession, so that he can at least demonstrate in court that his signature matches that contract, not just the fraudulent one.

If Bob doesn't have the inoffensively-modified version contract (perhaps only finding their original proposal), Mallory's fraud is perfect.

Comparison of the birthday problem (1) and birthday attack (2):
In (1), collisions are found within one set, in this case, 3 out of 276 pairings of the 24 lunar astronauts.
In (2), collisions are found between two sets, in this case, 1 out of 256 pairings of only the first bytes of SHA-256 hashes of 16 variants each of benign and malicious contracts.