8
$\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?

Improve this question
$\endgroup$
2
  • 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, 2015 at 14:32
  • $\begingroup$ That was my point, I can't tell the difference from available online sources. $\endgroup$
    – Rares Sabin Rusu
    Jun 18, 2015 at 15:12

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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