7
$\begingroup$

From my understanding both types of attack, collision and birthday, are based on the principle of two randomly/pseudo-randomly chosen plaintext to hash to the same value. I don't want to launch any biased supposition, but aren't they the same?

From Collision attack wikipedia article I learned that every cryptographic hash function is inherently vulnerable to collisions using a birthday attack but in the Birthday attack article it is stated that the attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations, thus birthday attack only has this permutation plus?

$\endgroup$
  • 1
    $\begingroup$ The quote from the second Wikipedia page is not very well-written. I'm not sure what it is trying to say. $\endgroup$ – bmm6o Jun 18 '15 at 14:32
  • $\begingroup$ That was my point, I can't tell the difference from available online sources. $\endgroup$ – Rares Sabin Rusu Jun 18 '15 at 15:12
5
$\begingroup$

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 process (as in the birthday problem).

Marc Stevens's Single-block collision for MD5 (2012) is an example of collision attack that is not a birthday attack.

$\endgroup$
  • $\begingroup$ Is it valid to say that because of the "Birthday Problem" a brute force attack on MD5 (which produces a 128 bit hash) would succeed after 2.2 × 10^19 attempts 50% of the time? According to the probability table in en.wikipedia.org/wiki/Birthday_problem $\endgroup$ – HeatfanJohn Jun 22 '15 at 20:31
  • $\begingroup$ @HeatfanJohn: Yes. In crypto we often use the approximation that a birthday attack on a fair hash of $n$ bits succeeds with odds near $1/2$ after $2^{n/2}$ hashes (if we are able to detect any collision that might occur). $2^{64}$ is 19% lower that the more precise estimate that you quote. $\endgroup$ – fgrieu Jun 22 '15 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.