Hot answers tagged birthday-attack
8
A collision is between two values. If you take a random pair of values you get a 1/2n chance of having a collision.
With 2n/2 values you have about 2n-1 pairs, so you could expect about 1/2 chance of collision.
(That's just the "intuitive way" of thinking about it; in practice, there are mathematical details.)
7
The short answer is: 2128 operations, no known birthday-like attack.
The long answer: when HMAC was first published, it came with a security proof, tailored for iterated constructions like Merkle-Damgård. In a MD hash function (MD4, MD5 and the whole SHA family are MD hash functions), the data to hash is processed by blocks with a compression function: the ...
4
The method described in the link you cited is based on Floyd's cycle finding algorithm, also known as "the tortoise and the hare" algorithm. This is a general-purpose algorithm for detecting cycles in iterated maps, which I will first describe below.
Specifically, consider the sequence $(x_i)$ defined by $x_i = H(x_{i-1})$ for some map $H$ and some initial ...
2
I think the simple way of looking at it is that it's because the number of pairs between items is roughly proportional to the square of the number of items.
Consider:
2 items-> 1 pair: AB
3 items-> 3 pairs: AB AC BC
4 items-> 6 pairs: AB AC AD BC BD CD
5 items->10 pairs: AB AC AD AE BC BD BE CD CE DE
6 items->15 pairs: AB AC AD AE AF BC BD ...
Only top voted, non community-wiki answers of a minimum length are eligible
