Tag Info

Hot answers tagged

11

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 ...


10

The hand-waving argument goes thus: when you accumulate $n$ hash outputs, you are actually producing $n^3/6$ triplets, each of them having probability $t^{-2}$ to be a three-way collision (where $t = |T|$, i.e. the size of the output space). So you should expect the first three-way collision to appear when $n^3/6 = t^2$, i.e. $n = 6·t^{2/3}$. For a perfect ...


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

Comparing a brute force attack on DES (with $2^{56}$ operations) to a birthday attack on CMAC (with $2^{64}$ operations) would appear to be an apples-to-Volkswagen comparison; they are assuming two things are similar, when they really aren't. The brute force attack on DES involves obtaining a single plaintext/ciphertext block pair, and then going through ...


5

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 ...


4

Let's first calculate the chance that every value is unique. The chance of two values picked being unique is $H - 1 \over H$ because when picking the second value you only have $H - 1$ unique picks left, with one pick being non-unique. Picking a third number has a chance of $H - 2 \over H$ to be unique, so the total chance of picking 3 unique numbers is ${H ...


4

I am literally quoting the paper here. You should really try to read the paper properly first before asking questions. In the notion of [22] the adversary does not get credit for finding any old collision. The adversary must still find a collision $M, M'$ but now $M$ is not allowed to depend on the key: the adversary must choose it before the key $K$ is ...


2

Here is a slightly different approach: The total number of ways to pick $n$ numbers among $H$ value allowing repetition (and with the order of picking counted in) is $A=H^n$. The number of ways to pick without repetitions is $B=\frac{H!}{(H-n)!}.$ Clearly, the probability you want to compute is $(A-B)/A=1-B/A$. Now, does $B/A$ contains the exponential you ...


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 ...


1

Here's yet another similar way to get this approximation. Consider every pairing of n elements from H, ignoring elements paired with themselves but not requiring that the elements be unique. i.e. $Let\ H_n=\{n\ elements\ chosen\ from\ H\}, P_n=\{(h_i,h_j) | h_i,h_j \in H_n\ and\ i\ne j\}$.Each element can be matched with any other element, so there are ...



Only top voted, non community-wiki answers of a minimum length are eligible