Welcome to the resource topic for
**2005/318**

**Title:**

Bounds on Birthday Attack Times

**Authors:**
Michael J. Wiener

**Abstract:**

We analyze a generic birthday attack where distinct inputs to

some function f are selected until two of the inputs map

through f to the same output, meaning that the attack has

succeeded.

We give tight bounds on the probability of attack success

after a given number of inputs are selected as well as

tight bounds on the expected number of inputs that must

be selected for the attack to succeed.

The types of functions considered include random functions

with uniformly random outputs, random functions whose outputs

have some arbitrary (biased) probability distribution,

concrete functions that are balanced (all outputs have the

same number of pre-images), and arbitrary concrete

functions.

In each case the bounds are given in terms of the probability

(1/\beta) that a pair of inputs give the same output,

which is different for each type of function.

The expected number of steps required to complete a

birthday attack in all cases is between

0.7\sqrt{\beta} and 2\sqrt{\beta}.

In some cases tighter bounds than this are given.

Compared to previous work in this area, the analysis here gives

tighter bounds and is more applicable to the most efficient

practical methods used to carry out birthday attacks,

such as a generalization of Pollardâ€™s rho-method and

parallel collision search.

However, significant challenges remain in proving bounds

for these methods.

**ePrint:**
https://eprint.iacr.org/2005/318

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .