# Tag Info

12

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

is $T^{1-1/n}$ Proof: Suppose we have a sample set $M$, with $|M| = m$. We choose a set $N$ with $|N| = n$ among the set $M$, which is $O(m^n)$ (you know $O(m^n)=m\cdot(m-1)\cdot...\cdot(m-n+2)\cdot(m-n+1)$). In particular, we suppose $A_1, A_2, ...., A_n$ make a $n$-collision $H(A_1)=H(A_2) , H(A_2)=H(A_3) , ... , H(A_{n-1})=H(A_n)$ just as you want. ...

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 The expected effort to find$k$distinct collisions on an ideal hash function of output size$n$is about$\sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}}$(for$k << 2^{n/2}$). One way to see this is to look at the probability of the outputs of two distinct inputs colliding, which is$2^{-n}$; if we generate outputs for$\sqrt{2k} \cdot 2^{n/2}$distinct ... 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