Hot answers tagged

14

n is the exponent. So when n is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$). It is required to only search half of the key space on average (if average is the correct term ...


13

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


12

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


9

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


8

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions). The reasoning is the obvious one; there are ...


8

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


5

Collision attacks are attacks where success is obtained when two values obtained by some process are identical. The term is often used in the context of hashes, since collision-resistance is one of their desirable property. Birthday attacks are collision attacks that work by the effect of chance, with the colliding values obtained by some roughly random ...


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


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


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

It is possible to reverse the birthday bound calculation. You can get an easily computable approximation using the expected number of collisions: If you had random $n$-bit salts, after $k$ values you would expect $2^{-n}\binom{k}{2}$ collisions. If the collisions are rare, they are mostly single collisions, so there are approximately $u = ...


4

Yes! I'd recommend at least 64 bits, but that's only because powers of two are convenient and space is cheap. Furthermore, usually a salt of the block size of the hash you're using is usually best, because salting at all will almost always involve an extra block, so why not fill it up given that there will be no performance impact? But once again, yes, ...


4

There are different birthday bounds when we draw independent uniform random integers less then $d$  (for some large $d$, including $d=2^{32}$ of the question) and watch for collision(s): In crypto, we often consider the bound of $\sqrt d$  ($65536$ for $d=2^{32}$) draws, at which there is a fair probability of collision: $p\approx1-1/\sqrt ...


2

The birthday attack, birthday paradox or - probably most accurately - birthday problem does occur for Merkle-trees. This is both the case for the output of the hash algorithms used for the nodes, the in between hash values in the tree as well as the final hash value. What's probably confusing you here is that the birthday attack isn't really a practical ...


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


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


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