**Bounds on Birthday Attack Times**

*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.

**Category / Keywords: **Birthday attack, hash function

**Date: **received 8 Sep 2005

**Contact author: **michael wiener at sympatico ca

**Available format(s): **PDF | BibTeX Citation

**Version: **20050912:121532 (All versions of this report)

**Short URL: **ia.cr/2005/318

[ Cryptology ePrint archive ]