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 .