Birthday attacks are a class of brute-force techniques used in an attempt to solve a class of cryptographic hash function problems. These methods take advantage of functions which, when supplied with a random input, return one of k equally likely values. By repeatedly evaluating the function for different inputs, the same output is expected to be obtained after about $1.2\sqrt(k)$ evaluations.

A simple approach of finding a collisions in a hash functions is to look for a second preimage:

  1. An initial value $I$ is picked and the hash $H_I$ is calculated.
  2. Further values are picked and their hash is compared to $H_I$.

An attack based on the birthday paradox is more efficient to find a collision: It compares the new hash value of each round with all the hash values that have been calculated earlier.

history | show excerpt | excerpt history