# Tag Info

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