Small-Space Birthday Attacks

We show here a better birthday attack with drastically reduced memory requirements. In fact, it has similar time complexity and success probability as before, but uses only a constant amount of memory.

The attack begins by choosing a uniform value and then computing and for (Note that for all where refers to -fold iteration of

In each step the values and are compared; if they are equal then there is a collision somewhere in the sequence (The values and might not be a collision because they may themselves be equal.)

The algorithm then finds the least value of for which and outputs as a collision.

This attack, described formally and analyzed below, only requires storage of two hash values in each iteration.

How many iterations of the first loop do we expect before Consider the sequence of values where as before. If we model as a random function, then each is uniform and independent of as long as no repeat has yet occurred in this sequence. Thus, we expect a repeat to occur with probability in the first elements of the sequence. When there is a repeat in the first elements, the algorithm finds a repeat in at most iterations of the first loop:

Let be a sequence of values with If with then there is an such that

The sequence repeats with period . That is, for all and it holds that Let be the smallest multiple of that is also greater than or equal to . We have since the sequence of values contains a multiple of . Since and is a multiple of , it follows that .

Thus, if there is a repeated value in the sequence there is some for which

But then in iteration  we have and the algorithm breaks out of the first loop. At that point in the algorithm, we know that The algorithm then sets and and proceeds to find the smallest for which (Note because It outputs as a collision.