Paper 2005/318

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.