Birthday attack Guide, Meaning , Facts, Information and Description

A birthday attack is a type of cryptographic attack which exploits the mathematics behind the birthday paradox, making use of a space-time tradeoff. Specifically, if a function yields any of n different outputs with equal probability and n is sufficiently large, then after evaluating the function for about 1.2 √n different arguments we expect to have found a pair of different arguments x₁ and x₂ with f(x₁) = f(x₂), known as a collision. If the outputs of the function are distributed unevenly, then a collision can be found even faster (Bellare and Kohno, 2004).

Digital signatures can be susceptible to a birthday attack. A message m is typically signed by first computing f(m), where f is a cryptographic hash function, and then using some secret key to sign f(m). Suppose Bob wants to trick Alice into signing a fraudulent contract. Bob prepares a fair contract m and a fraudulent one m'. He then finds a number of positions where m can be changed without changing the meaning, such as inserting commas, empty lines, spaces etc. By combining these changes, he can create a huge number of variations on m which are all fair contracts. In a similar manner, he also creates a huge number of variations on the fraudulent contract m'. He then applies the hash function to all these variations until he finds a version of the fair contract and a version of the fraudulent contract which have the same hash value, f(m) = f(m' ) . He presents the fair version to Alice for signing. After Alice has signed, Bob takes the signature and attaches it to the fraudulent contract. This signature then "proves" that Alice signed the fraudulent contract.

The birthday attack can also be used to compute discrete logarithms. Suppose x and y are elements of some group and y is a power of x. We want to find the exponent of x that gives y. A birthday attack computes x^r for many randomly chosen integers r and computes yx^-s for many randomly chosen integers s. After a while, a match will be found: x^r = yx^-s which means y = x^r+s.

If the group has n elements, then the naive method of trying out all exponents takes about n/2 steps on average; the birthday attack is considerably faster and takes fewer than 2√n steps on average.

Table of contents

1 See also 2 References 3 External Link

See also

• Meet-in-the-middle attack

References

• Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp401–418

External Link

• "What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.

This is an Article on Birthday attack. Page Contains Information, Facts Details or Explanation Guide About Birthday attack

	Web www.E-paranoids.com