Hot answers tagged

16

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


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

It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$ rather than $O(2^{n/2})$. See The ...


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


4

When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the safe. Yes, however there's a key difference between physical safes and cryptography. With a physical safe, the attackers must be present on site (if they ...


3

If $f:\{0,1\}^m\rightarrow \{0,1\}^n$ with $n\geq m,$ then of course there are, the set of one-to-one functions, but such a function is not a cryptographic hash function, since it lacks the compression property. If $n<m,$ (or more generally if $|X|>|Y|$ for $f:X\rightarrow Y$), collisions will happen.


3

The citation as now expanded is clearly in the context of key search for a cipher, and grossly wrong, including time estimate to find a DES key with odds 50% with 1 million keys tested per second (that is over 11 centuries where 7.9 minutes is stated). In other contexts, the explanation could be right except for a moderate factor erring straight on the ...


2

$k(k-1)/2$ is usually called a binomial coefficient and written $k \choose 2$. It corresponds to the number of unordered pairs of distinct elements out of $k$ elements. It does indeed correspond to the sum ${k \choose 2} = \sum_{i=1}^{k-1} i$. This is quite intuitive: fixing one element, you have $k-1$ pairs containing this element. Now remove it, consider a ...


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